SI204 Class 37: Traversing a linked list

Reading
None.
 
Lecture

One of the most common things we want to do with a linked list is to print the data fields in the list.  From the last class we saw a brute force way of doing it if we know ahead of time how many nodes are in the list.  But if we know the number of nodes, we could have simply used an array rather than a link list.  So what we really want to do is print the data fields of a linked list when we don't know how many nodes are in the list.

Printing a linked list using a while loop

This concept implies that we would want to use a while loop to do the printing.  So suppose we want to print the contents of the following list.

 

 

The thing we need to be especially careful of is to not change the fact that the pointer LIST is pointing to the first node in the list.  If we do then we have nothing pointing to the first node and the list becomes useless.  The easiest way to visualize traversing a list is to use another pointer, say p.  First we will set it to point to the first node in the list and then print the data field of the node it is pointing to.  Then we will "bounce" p down a node and repeat the process.  We will continue this until p is zero which means that it isn't pointing to any node.

If we define a struct Node like:

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

the following pseudo code should accomplish what we want to do.

create another pointer p and set it to point to the first node in the list
while (p is not the null pointer){
     cout << p->data << endl;
     bounce the pointer down a node
}

Since the pointer LIST already points to the first node in the list, once we create the pointer p, we could simply copy the contents of LIST to the pointer p and we would have two pointers pointing to the first node.  That gives us the folowing code and picture.

Node* p = LIST;
while (p is not the null pointer){
     cout << p -> data << endl;
     bounce the pointer down a node
}

   

Since the pointer p contains the address 2468 (If you are wondering where these addresses came from, I just made them up so you could see actual addresses.), it is not the null pointer, so we enter the loop and print the data value 18.  Now we need to bounce the pointer p down a node so it points to the node containing data value 27.  How do we do that?  Simple, we replace the contents of p with the next field of the node it is currently pointing at.  When we do this, our code and picture looks as follows.

Node* p = LIST;
while (p is not the null pointer){
     cout << p -> data << endl;
     p = p -> next;
}

 

Notice that the pointer LIST still points to the first node in the list even though the pointer p is now pointing to the second node in the list.  If we continue in this manner, we will eventually reach the following picture as a result of "bouncing" the pointer p down as node.

 

Since the pointer p contains the address 3D64, the while loop is still true and we print the data value 64.  Then we set p to the value of the next field which is the null pointer.  We then go to the top of the while loop and check to see if the pointer p  is not the null pointer.  Since it is, the while loop terminates and we have printed the contents of all the nodes in the link list.  Better than that - we still have the pointer LIST pointing to the first node of the list so we can use the list to do other things if necessary.  So our final code is

Node* p = LIST;
while (p != 0){
     cout << p -> data << endl;
     p = p -> next;
}

 

Printing a linked list using a for loop

Since we normally do not know how many nodes are in our linked list, so could probably assume that we can't use the for loop to print a linked list. Well it turns out that we really can use the for loop if we are clever with the initialization, termination, and incrementation of the loop.  The first thing we need to think about is the type of the variable that is controlling the loop because up until now it has normally been an int and our code has looked like

   for(int i=....; test ; increment)

Since we don't know how many nodes are in the list, we can't count them, so the variable i can't be an int.  If you think about it, we want to traverse the list by bouncing a pointer down the nodes, stopping at each node long enough to print its data field.  So our control variable needs to be a pointer to a node.  Now for some history.  Years ago, long before you were even a twinkle in your parents' eyes, one of the two most common programming languages was Fortran and the amount of memory in a computer was extremely small in comparison to today's machines.  So to save memory the name for any variable that was to store a numeric type (int or double) was only one letter long.  But Fortran still had to distinguish whether the variable contained an int or a double.  So if it contained an int the variable name had to be i,j,k,l,m, or n.  Because of that, using the variable i to designate the control variable in a for loop is a hangover from Fortran.  So since our control variable is a pointer rather than an int, we are going to name it p.  From all the work we just did with the while loop, we already know that the pointer p has to be initialized so that it points to the first node in the list.

If we again define a struct Node like:

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

our for loop is now

for(Node* p=LIST; test ; increment)

So when do we want to exit of the for loop?  Obviously, we want to exit the loop when p contains the null pointer.  So our code becomes

for(Node* p=LIST; p != 0 ; increment)

Since p is a pointer we actually could add 1 to it, but the resulting address would not be the one we want.  We want "increment" operation to "bounce" p to the next node.  So we do this the same way we did in the while loop and have

for(Node* p=LIST; p != 0 ; p = p -> next)

So what does that leave to be in the body of the for loop?  Just the print statement.  So we can print the data fields of the link list with the following code.

for(Node* p=LIST; p != 0 ; p = p -> next){
    cout << p -> data << endl;
}


 

Printing a linked list using recursion

 

There is a third method that can be used to print the data fields of a linked list - mainly recursion.  It has a definite advantage over the other two because it can print the list from front to back or from back to front.  Both the while loop and the for loop print the list from front to back.

It turns out that a lot of linked list operations are very easily accomplished with recursion. The reason for this is that there is an essentially recursive way of looking at lists. Recall that "a list" in our program is really a pointer to the first node in a linked list. Suppose LIST is a variable of type Node*, and suppose that it points to the list 87, 42, 53, 4 as illustrated in the following picture:

 

So, LIST is an object of type Node* and therefore we say that it is a list. However, by that same argument the next-field of the node with data-value 87 is a list. After all, isn't it also of type Node*? It is the list 42, 53, 4, i.e. everything but the first element of the list that LIST is. So, there is this natural way of looking at a list as consisting of the first node and the list of everything else.

To use recursion we will need to write a function printList and send it the pointer to the first node in the list that we want to print.  Now we only want to print the data field of the node if the pointer we receive is actually pointing to a node (i.e. not the null pointer).  Once we have printed the data field, we simply call the function again but this time we send in the next field of the node as the pointer.  Since all we want to do is print, our function will not return anything. 

So if we again define a struct Node like:

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

our function looks like this.

void printList(Node* p) {
    if (p!=0){
        cout << p ->data << endl;
        printList(p->next);
    }
}

and our call to printList would simply be printList(LIST);

This particular version of printList prints the list from front to back because we print before we call the function printList again.  You can also write printList slightly differently and it will print the list from back to front.


Last modified by LT M. Johnson 11/26/2007 04:19:17 PM