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;
}
Warning: Do not use LIST to traverse the list! Create a new pointer.

Mandatory Problem: Search in linked lists

We would like to write a function with the following prototype: 
Node* search(dobule value, Node* L);

Returning a pointer

Using the function

Using the function, we can write a program that provides a "search" feature. 

int main()
{
  Node* L = NULL;

  // read and store numbers 
  double x;
  char c;
  while( cin >> x >> c) // comma-separated
  {
    L = add2front(x,L);

    // ';' means the end of the numbers
    if( c == ';' ) 
      break;
  }

  // process commands
  string comm;
  while(cin >> comm && comm == "search" && cin >> x)
  {
    Node* p = search(x,L);
    if (p != NULL)
      cout << "Found:" << p->data << endl; // *** NOTE HERE ***
    else
      cout << "Not Found!" << endl;
  }

  // delete the list
  deletelist(L);
                                  
  return 0;
}
  Sample run 
~/$ ./ex
34.2, 54.98, 92.0, 83.9;
search 54
Found: 54.98 
search 83
Found: 83.9
search 12
Not Found!
quit

Question: function definition?

Check the solution.

Deleting a list

Step 1: 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 -- now the second node should become the head node. 

Node* deletefront(Node* L)
{
  if (L == NULL)
    return NULL;
  
  Node* second = L->next;   // store the 2nd node to return
  delete L;              // delete the front node
  return second;
}
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!!
  Node* second = L->next;  // SEG FAULT: The front node has been deleted! 
  return second; 
}
Answer:

The function goes through the following steps:

  1. Delete from memory the node that L points to.
  2. return a pointer pointing to the the second node.
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

Step 2: 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); 
}

Adding a Node After a Node

We would like to add a node with value 25, so that the list looks like 
 ... 10, 20, 25, 30, 40 ...
Give the code performing the task.

Hint:

Answer

Other Practice Problem

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