Algo lab/linked lists

Source [1]

Lists are everywhere. Comments directly replying the same status can be kept in a list. A list of monsters around you (within a particular radius) in a game is a list. When you have a collection of objects, the simplest way to deal with them is to put them in a list.

What can you do with a list?

Below is an example of a list of top Women's World Cup goal scorers.

Marta
Birgit Prinz
Somying Jaiyen
Abby Wambach
Michelle Akers
Sun Wen
Bettina Wiegmann
Ann Kristin Aarones
Heidi Mohr

It seems that there is a mistake. Somying Jaiyen should not be in the list. So let's remove it. This is the result

Marta
Birgit Prinz
Abby Wambach
Michelle Akers
Sun Wen
Bettina Wiegmann
Ann Kristin Aarones
Heidi Mohr

Now, suppose that in year 2019 another player, Mary Playgood has just scored 12 goals. With this many goals, she has to be inserted into the list after Akers. The list becomes:

Marta
Birgit Prinz
Abby Wambach
Michelle Akers
Mary Playgood
Sun Wen
Bettina Wiegmann
Ann Kristin Aarones
Heidi Mohr

You have just heard the name Orathai Srimanee, who is a famous Thai player. You may want to check if she is in the list. To do so, you have to look at every entry in the list, and find out that she is not in the list. You want to know how many additional goals she has to score to be in the list. With the current information on the list, you cannot answer the question. You look up wikipedia and update the list with goal information.

Marta, 15
Birgit Prinz, 14
Abby Wambach, 14
Michelle Akers, 12
Mary Playgood, 12
Sun Wen, 11
Bettina Wiegmann, 11
Ann Kristin Aarones, 10
Heidi Mohr, 10

You look at the last entry and see that Heidi Mohr scored 10 goals. So Orathai Srimanee needs to score 8 more goals to have a chance to be in the list.

You can see that there is a lot of operations you can do with a list. And also, note that an entry in a list can keep fair amount of information.

This chapter discuss how we can implement a list and also an abstract data type for a list.

We can use the most common data structure, arrays, to deal with lists. Arrays are good for keeping collections of data. However, array manipulations are usually inefficient. Since every element in an array is stored contiguously, insertion and deletion of array elements usually take linear time. In this chapter, we shall look at a commonly used abstract data type for linear collection called a list. You can implement a list using an array, but the another common implementation is a linked list, which allows efficient manipulation of list items.

A list of colored balls

Let's start with a concrete problem. Consider a rather popular casual game called Zuma. In this game, there is a list of enemy colored balls lining up to reach a secret gate. You want to prevent that by shooting another set of colored balls to the list. Because consecutive three balls of the same color explode, you can potentially destroy all the enemy balls.

We will look at the simpler version of the game, where we can shoot the balls, but the balls remain in the list. In this tasks, there are n enemy colored balls and you want to shoot m colored balls. To be precise, the enemy balls are referred to as ball 1 to ball n, and the balls you will shoot are referred to as ball n+1 to ball n+m. For each of your i-th ball, for 1≤i≤m you shoot into the list, it will land right after ball p[i]. (Note that i here is not referring to the ball numbers, as your i-th ball is numbered n+i.) You want to know the final list of balls.

Related task: Zooma 1

One can deal with this task by just simulating the system and output the final result. Starting with a list of n numbers from 1 to n. We iterate the array p[i] and insert ball number n+1 into the sequence right after p[i]. To do so, we need to look up where p[i] is in the sequence and insert i+n right after it.

Array implementation

The easiest way to implement lists is to use arrays For this Zooma1 problem, we have to maintain a list of ball numbers. We can do so by having a large enough array and a size counter.

const int MAX_N = 2000100;

int balls[MAX_N];
int ball_count = 0;

To solve zooma1, we need the following list operations:

• insert_end(int lst[], int& s, int val) - add an integer to the end of the list
• find(int lst[], int s, int target) - find a target location in the list
• insert(int lst[], int& s, int val, int loc) - add an integer to a particular location on the list

With these functions, we can implement the main function for solving zooma1 as follows.

main()
{
  int n,m;
  int d,p;
  
  cin >> n >> m;
  for(int i=0; i<n; i++) {
    cin >> c[i];
    insert_end(balls, ball_count, i+1);
  }
  for(int i=0; i<m; i++) {
    cin >> d >> p;

    int idx = find(balls, ball_count, p);
    insert(balls, ball_count, i+n+1, idx+1);
  }

  for(int i=0; i<ball_count; i++) {
    cout << balls[i] << endl;
  }
}

Running time

First assume that m=O(n). The implementation of find and insert may take O(n) time in a list with n integers. Thus, the total running time is O(n²).

We will learn a new data structure that can speed up the solution to run in time O(n+m).

Implementations: linked lists

typedef

In C++, you can simply declare a new type based on known types using typedef.

typedef int valueType;

valueType x = 10;

We will declare new valueType so that our linked list code works fairly well with any types. We will eventually use template to make generic linked list.

struct

struct ListNode
{
  valueType val;
  ListNode* next;

  ListNode(valueType val, ListNode* next=0)
    : val(val), next(next) {}
};