Following the Chain

Recall how I created the list of {3, 5, 7} using the ListItem class. Here is the code again:

ListItem list = new ListItem(3);
list.next = new ListItem(5);
list.next.next = new ListItem(7);

I simply named the first item list (rather than item1), and then I used the next field to link each item to the one after it. A more common convention is to name the first item head, since it is the head of the list. So we can rewrite the code like this:

ListItem head = new ListItem(3);
head.next = new ListItem(5);
head.next.next = new ListItem(7);

Let’s break down the last statement:

  1. head.next refers to the second item in the list (the item with value 5).
  2. head.next.next refers to the next field of the second item, which is null at this point.
  3. We create a new ListItem with value 7 and assign it to head.next.next, which means we are setting the next field of the second item to point to the new item with value 7.

Let’s trace what a few more statements do to a linked list, starting each time from the same list:

          ┌───┐     ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 8 │ ──▶ │ 7 │ ──▶ │ 5 │ ──▶ │ 9 │ ──▶ null
          └───┘     └───┘     └───┘     └───┘

head = head.next; moves the head of the list to the second item. The new linked list looks like this:

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

We effectively removed the first item.

Now start from head → 8 → 7 → 5 → 9 → null again and this time run head.next = head.next.next;. This skips the second item and links the first item directly to the third item. The new linked list looks like this:

          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 8 │ ──▶ │ 5 │ ──▶ │ 9 │ ──▶ null
          └───┘     └───┘     └───┘

We effectively removed the second item.

Once again start from head → 8 → 7 → 5 → 9 → null and this time run head.next.next.next.next = head;. This sets the next field of the last item (the item with value 9) to point back to the head of the list (the item with value 8). The new linked list looks like this:

          ┌───┐     ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 8 │ ──▶ │ 7 │ ──▶ │ 5 │ ──▶ │ 9 │ ──┐
          └───┘     └───┘     └───┘     └───┘   │
            ▲                                   │
            └───────────────────────────────────┘

We effectively created a circular linked list.