A Tail Pointer

addLast is $O(n)$ because it has to traverse the list to find the last item. If we stored a reference to the last item, a tail pointer, we could attach a new item directly, without any traversal. That would make addLast $O(1)$.

Suppose we already held a tail reference to the last item:

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

Now we can attach a new item directly:

tail.next = new ListItem(value);

Here is the schematic after the attachment:

          ┌───┐     ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ │ 9 │ ──▶ null
          └───┘     └───┘     └───┘     └───┘
                                ▲
                                │
                               tail   (now out of date — the last item is 9)

But now our tail reference is stale, so we need to move it forward to point to the new last item.

tail = tail.next;

Consider how this works with the addLast method. It takes a head and a value, and it returns the new head. If we want to use the tail reference as well, we need to pass it in.

public static ListItem addLast(ListItem head, ListItem tail, int value) {
  // ...
}

With a tail, we are keeping two references to the list, and the caller has to keep both of them correct. If addLast changes the tail, it has to hand that new reference back to the caller. But a Java method can return only one value, so we cannot return both the new head and the new tail.

There are workarounds. We could return a small object holding both references, or a two-element array, or pass in an object the method can write its results into. Notice that each of those does the same thing: it bundles head and tail together. That makes sense, because they describe the same list, and every operation has to leave both of them correct. A method that takes them as two separate arguments has no way to enforce that. We will deal with this in the next chapter.