Traversing a List

Now that we can build a linked list, let’s do something with it. A very common operation is to visit every item in the list, one by one. We call this traversing the list.

public static void printAll(ListItem head) {
  // TODO
}

We only get at our linked list through its first item, the head. We cannot write head[i] to access the item at position i as if it were an array. Instead, we have to follow the next references, starting from the head, until we reach the end.

Here is the linked list we will work with:

         ┌───┐     ┌───┐     ┌───┐
head ──▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
         └───┘     └───┘     └───┘

To print every value, we need a way to keep track of which item we are at as we traverse the list. We will use a reference variable for that. Let’s call it current. We start by pointing current at the head of the list:

ListItem current = head;

         current
            │
            ▼
          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
          └───┘     └───┘     └───┘

Now we print the value of the item that current points to (current.value), and then we move current to the next item in the list (current.next):

System.out.println(current.value);  // prints 3
current = current.next;

                   current
                      │
                      ▼
          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
          └───┘     └───┘     └───┘

We keep doing this, print and then move to the next item, until current reaches the end of the list. How do we know we have reached the end? Recall that the last item’s next is null. So once we move past the last item, current itself becomes null. There are no more items to print, so we stop.

                                      current
                                         │
                                         ▼
          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
          └───┘     └───┘     └───┘

We can write this as a while loop:

public static void printAll(ListItem head) {
  ListItem current = head;
  while (current != null) {
    System.out.println(current.value);
    current = current.next;
  }
}

That is the traversal pattern. You will see this same loop again and again in this chapter. What changes is what we do inside the body, or where we stop.

What happens if we call printAll with a null head? Nothing is printed. The method starts by setting current to head, which is null. The loop condition current != null is false right away, so the loop body never executes and the method returns without printing anything.