SI204: Pointer basics & linked lists intro

Pointers to a single struct object

Up til now, we've used pointers to point to arrays of objects, rather than individual objects. It turns out that pointers to individual objects are very important in a wide range of circumstances.

`new` and `delete`

You can allocate a single object of a given type by just leaving the square brackets off the new statement. For example, to create a single point object and a pointer, p, that points to it, we could write:

point* p = new point;

To delete the point that p points to, you use the usual delete statement, except without the square brackets.

delete p;

operator `->`

In order to access a data-member of a struct from a pointer, one can use the -> operator. The pointer goes on the left, the name of the data member goes on the right. For example:


point* ptr = new point;
ptr->x = 0;
ptr->y = 0;

Linked List Intro

One big reason to have a pointer to a single object is "linked lists", which we'll be studying extensively in the next several lessons. Up to this point we've used arrays to store a sequential collection of objects.

Limitations of arrays

Arrays are great, but they have a few limitations that cause us some headaches.

The size of an array is fixed from the moment it is allocated with new, so you always have to know how many objects you want to store ahead of time.
Inserting an element to the front of an array or somewhere in the middle is a big job - first you need extra "room" in the array, and second you need to move everything else in the array back an element, which is a lot of work.

Linked lists are an alternative to arrays that avoids these limitations.

Node of a linked list

A linked list consists of "nodes", each of which contains

a piece of data (in a linked list of ints that data would be an int, in a linked list of strings that data would be a string, etc)
a link (i.e., pointer) to the "next" node in the list.

The following picture shows a linked list storing the numbers 87, 42, 53, 4.

You absolutely have to keep this kind of picture in mind if you want to program with linked lists! The idea here is that you move through the collection starting with a pointer to the first node in the list, which I've marked "LIST" in the picture. From there you simply follow the links (arrows) from one piece of data to the next. The last node in a linked list does not have a link to a "next" node - we usually show its next-field with a slash to indicate that.

Representing a node in C++

To realize this picture in C++ code, we see that we have to manipulate "nodes".

Type: It's natural to make a struct Node.
Data: Let's assume that we want to store ints in our list, then a Node will consist of a int, which we might call "data".
Link: The struct should also have a link to the "next" node. The question is:
What type of object would the link to the "next" node be?
Hopefully you see that what we need is a pointer to the next node in the list, which means we need a pointer to an object of type Node - i.e. we need a member of type Node*.


struct Node {
  int data;
  Node* next;
};

NULL pointer

By convention, the next field of the last element in the list is set to the value NULL (which is just defined to be 0) to indicate that it's not pointing to anything. In particular, consider the following code:


if( 0 == NULL ) 
  cout << "equal" << endl;
else 
  cout << "not equal" << endl;

The program will output equal. We often call NULL a "null pointer".

Manipulating a linked list in your program

Remember that we manipulate an array in our programs by manipulating a pointer variable that points to the array. Similarly, we manipulate a linked list by manipulating a pointer to the first node in the list.

1. Initializing the list

Now, we might have a variable of type Node* called LIST:


Node* LIST = NULL;

Initially LIST points to NULL, which means the list contains no nodes.

2. Data have been added

Suppose that data have been added; we will talk about how to do this soon. The variable LIST then points to the first node in our linked list of integers. Our list might look something like this:

3. Printing out the first integer

We could print out the first integer in our list with the statement

cout << LIST->data;

which says "print the data field of the Node pointed to by LIST". You can simply follow that in the picture, it prints out 87.

4. Printing out the second integer

Now, to print out the second integer in the list, we'd like to say the same thing, except instead of LIST, which points to the first node in the list, we need a pointer to the second node in the list. Then we could write:


cout << (pointer to the second node)->data;

Now, if you look back at the picture, you see that there is a pointer to the second node in the list, it is the next field from the first node in the list, i.e. LIST->next is a pointer to the second node in the list. So, to print out the second node in the list you write:

cout << (LIST->next)->data;   // Drag your mouse and see if the answer matches your guess

Actually you don't need the parentheses, because the -> is left associative.

5. Printing out the third integer

To print out the third element of the list you could write:


cout << LIST->next->next->data;

On the other hand, this way lies madness! It's usually better to simply make a temporary pointer that points to what you want, and move that pointer through the list. For example:


Node* ptr = LIST; // Set ptr to point to first node
ptr = ptr->next;  // Set ptr to point to second node
ptr = ptr->next;  // Set ptr to point to third node
cout << ptr->data;

Adding a Node

Adding a Node to the front of a list is a pretty straightforward thing:

You create a new Node
Set it's data and next fields
set LIST to point to it, since it's supposed to be the new "first node in the list".

The following picture shows it all:

Initially we have:
`Node* temp = new Node;`
`temp->data = 8;`
`temp->next = LIST;`
`LIST = temp;`
At the end we have:

Whenever you want to add a new value val to the front of a linked list LIST, the same sequence of steps will do the job:


Node* temp = new Node;
temp->data = val;
temp->next = LIST;
LIST = temp;

Adding a node to an empty list

Initially we have:
`Node* temp = new Node;`
`temp->data = 3;`
`temp->next = LIST;`
`LIST = temp;`
At the end we have:

Recall: Representing an empty list

Recall that in our programs, we represent an empty list by a null pointer, i.e. with a pointer whose value is NULL.

The same code works!

The sequence of steps we used to add a new element to the front of a list works perfectly well even when the list is empty. In the example below,

LIST is empty.
The exact same sequnce of steps we used above will add the new value 3 to the "front" of the list.

`add2front()` function

At this point, we should have the idea that, since we have a fixed sequence of steps that add a new element to the front of a list, we might want to make a function!

Prototype of `add2front()`

Of course, the function will need to be passed the value val that's supposed to be the data for the new node.
Note that we want to think of this function as modifying the LIST pointer, then the function better take the pointer to the front of the list by reference!

Therefore, the prototype of the function should be as follows:

void add2front(int val, Node*& LIST);         // Drag your mouse for the answer and verify your guess.

Definition of `add2front()`

You can find the actual definition of add2front in Here; it is an example program that reads ints from the user and stores them in a linked list using the add2front function.

Problems

The type of object stored in the data fields of the nodes in a linked list are pretty much irrelevant to the problem of how to manipulate a list. Therefore, we're going to concentrate on basic linked list manipulations, which provide us with a wealth of interesting problems. These typically boil down to functions you'd like to define, like:

add2back
length
print
find
insertafter
insertbefore
max
min

I don't want to post solutions to these right now, since we'll be looking at these in labs.