10.1.6. Looping over a Linked List

Loops and linked lists

---

Some algorithms on linked lists are convenient to express as loops. You start with a pointer to a linked list. Each time around the loop you move your pointer to the tail of its current value. The loop typically ends when your pointer is NULL (that is, it is an empty list). For example, here is a definition of length(L) using a loop.

  int length(const List L)
  {
    const List p;
    int count = 0;

    for(p = L; !isEmpty(p); p = tail(p))
    {
       count++;
    }
    return count;
  }

If you look at the list pointed to by p each time this function reaches the top of the for-loop, you can see what it is doing.

The loop ends because p is an empty list.

Sum of a list

---

Suppose sum(L) is intended to return the sum of all of the numbers in linked list L. A scan algorithm will do the job. Here is a plan showing the values of variables p and s for computing sum(L) for L = [2,4,6,8].

At each line, sum(p) is the sum of the numbers that have been looked at (and removed from p). So s must be the answer for the whole list when the loop ends.

Another way to look at this algorithm is through a loop invariant. Notice that, in each line, sum(p) + s = sum(L). The loop stops when p is [ ]. So, when the loop stops, sum([ ]) + s = sum(L). That is, s = sum(L).

Here is a definition of sum in C++.

  int sum(const List L)
  {
    const List p = L;
    int        s = 0;

    while(!isEmpty(p))
    {
      s += head(p);
      p  = tail(p);
    }
    return s;
  }

  int sum(const List L)
  {
    int s = 0;
    for(const List p = L; !isEmpty(p); p = tail(p))
    {
      s += head(p);
    }
    return s;
  }

Reversing a list

---

Let's define function reverse(L), which returns the reversal of list L. For example, reverse([2,4,6,8]) = [8,6,4,2]. Think of the list as a deck of cards. To reverse the deck, start with it in your hand. Remove a card from the top of the deck and place it in a stack of cards on a table. Keep doing that until there are no more cards in your hand. The deck on the table is the reversed deck. Showing the process just before moving each card gives the following table

  List reverse(const List L)
  {
    const List hand  = L;
    List       table = emptyList;

    while(!isEmpty(hand))
    {
      table = cons(head(hand), table);
      hand  = tail(hand);
    }
    return table;
  }

Exercises

---

1. Using a loop, write a C++ definition of function smallest(L), which returns the smallest number in nonempty list L. Answer

2. Using a loop, write a C++ definition of function firstEven(L), which returns the first even number in list L. If L does not contain an even number, then firstEven(L) should return −1. Answer