Topics Covered

Traversing a list

Suppose LIST is a variable of type Node* in our program, and suppose that it points to the list 87, 42, 53, 4 as illustrated in the following picture:

We'll start things off, however, by looking at the simplest of programs:
Read and store ints in a linked list, then print the values stored in a list.

Traversing a list

Printing a list, and indeed most things you do with a linked list, involves traversing a list — which means visiting each node in the list, in order. Doing this iteratively (as opposed to recursively, which we'll see in a later lecture) means using a temporary pointer that points to the first node originally, then moves to point to the second node in the list, then moves to point to the third, and so on. 

Node* p = LIST;
while(????)
{
   cout << p->data << " "; // do whatever you have to do while traversing the list
   p = p->next;            // move to the next node 
}
The last line of the while-loop body, p = p->next; is what moves us from one node to the next.

Test condition in the while loop

The only real difficulty is going to be this:
How do we know when we're done? What do we replace the ???? with?
To address this question, consider the following scenario:
  1. Loop continued, and finally the last iteration has come. That is, p points to the last node (i.e., the node containing 4).
  2. Now, the expression p = p->next is executed, which implies that the value of p becomes NULL. Recall the "slash" in the node means that the value of next field is NULL.
  3. Right before the next iteration starts, the program checks the test condition of the loop, and the condition should be evaluated to be false, since the loop must exit at this moment.
  4. It turns out that the test condition (p != NULL) satisfies our requirements (if you are not convinced, walk the printing code snippet below using the above linked list example, slowly and node by node, and convince yourself).
So, the actual code looks like: 

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

Traversing an empty list

Note this code works even when the list is empty (i.e., when LIST is NULL).

In general this way of writing functions for manipulating linked lists is pretty good.

Traversing a list using a for loop

Note that you can write the while-loop for printing nice and compactly as a for loop: 

for(Node* T = L; T != NULL; T = T->next)
  cout << T->data << ' ';

cout << endl;
I really prefer writing it this way, because it makes the traversal code (the for(Node* T = L; T != NULL; T = T->next)) totally boiler-plate: that stays the same for any kind of list you ever make, and really no matter what you're doing for the traversal.

Example code

Now let's look at the concrete example of traversing the list in order to print out its values. 

#include <iostream>
using namespace std;

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

Node* add2front(int val, Node* L);


int main()
{
  // Create list
  Node* L = NULL;
  int x;
  while(cin >> x && x > 0 )
    L = add2front(x,L);

  // Print list
  for(Node* T = L; T != NULL; T = T->next)
    cout << T->data << ' ';

  cout << endl;
  return 0;
}


Node* add2front(int val, Node* L)
{
  Node* T = new Node{val, L};
  return T;
}

Computing the length

Here's a typical example of a linked list problem: Write a function that determines the length of a linked list. We know that our function's prototype should look like this: 
int length(Node*);
It returns an int because, of course, the length of a list is an integer. It takes a pointer to a Node, because we manipulate lists by manipulating pointers, just like with arrays. The process we use to determine the length is straightforward too: move through the list from front to back one node at a time, keeping track of how many you visit in the process.
Using a while loop Using a foor loop 

int length(Node* L)
{
  Node* curr = L;
  int count = 0;

  while(curr != NULL)
  {
     count++;
     curr = curr->next;
  }

  return count;
}


int length(Node* L)
{
  int count = 0;
  for(Node* curr = L; curr != NULL; curr = curr->next)
     count++;

  return count;
}
Convince yourself that our length implementation does work for the empty list!

Search in linked lists

Pointers not values

Recall that, earlier in the semester, we discussed that where arrays are concerned, it's "indices not values". With linked lists we have something similar: pointers not values.

Function prototype

As with arrays, when this becomes really important is search. Suppose we want to write a "search" function for linked lists? What should we return if the search is successful? What should we return if a search is unsuccessful? In both cases, the best thing to do is to return a pointer. Thus, the search prototype will be (in this example for lists with data of type double): 
Node* search(dobule value, Node* L);

Using match()

Recall that it's best to have a function bool match(double a, double b); — where the types of the arguments a and b match the type of the data in the Node — that takes care of determining whether the data in an individual Node matches the value being searched for.

Example

As an exercise, check Ex0.cpp and see if you can provide a definition for the "search" function. If you've done it properly, the program should run like this: 
~/$ ./prog
34.2, 54.98, 92.0, 83.9;
search 54.98
Found!
search 54.88
Not Found!
search 12
Not Found!
quit
Check the solution.

Deleting a list

Deleting the front node

Let's start with a function that deletes the front node of a given list: 

Node* deletefront(Node* L)
Note that once the front node is deleted, the function should return the modified list. 

Node* deletefront(Node* L)
{
  if (L == NULL)
    return NULL;
  
  Node* ret = L->next;   // store the 2nd node to return
  delete L;              // delete the front node
  return ret;
}
Q: What's wrong with the following simpler (even seemingly more elegant) function? 

Node* flawed(Node* L)
{
  if (L == NULL)
    return;
  
  delete L;        // delete the front node!!
  return L->next;  // return pointer to the the 2nd node
}
Answer:

The function goes through the following steps:

  1. Delete from memory the node that L points to.
  2. return L->next.
The problematic step is 
step 2
because
Evaluating L->next needs to access the node that L points to, but that node has already been deleted in step 1

Deleting the entire list -- Keep deleting the front node

Now we can write a function that deletes the entire list. The idea is to keep deleting the front node until the list L becomes empty. 

void deletelist(Node* L)
{
  while (L != NULL)
    L = deletefront(L); 
}

Mandatory Practice Problem

  1. Construct a reverse copy of a list of double's. Check out my solution.

Other Practice Problem

  1. Find the maximum value in a list of double's. Check out my solution.