A Sentinel Node

The special cases at the ends come from the nulls before the first node and after the last. The fix is to put placeholder nodes in those two positions. They hold no list value, but they give every real node a neighbor on each side. A placeholder node like this is called a sentinel (or a dummy node).

We add two of them: one sentinel at the front and one at the back. head points at the front sentinel and tail at the back sentinel; they never move and are never removed. The real values live between the two sentinels.

Here is an empty list with sentinels. The two sentinels point at each other, and there are no real nodes:

          ┌─────┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └─────┘
           front        back
         sentinel     sentinel

Here is the list 3, 5, 7, with the real nodes between the sentinels:

          ┌─────┐      ┌───┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 3 │ ◀──▶ │ 5 │ ◀──▶ │ 7 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └───┘      └─────┘
           front                                         back
         sentinel                                      sentinel

The constructor wires the two sentinels together to make the empty list:

public LinkedList() {
  head = new Node<>(null);  // front sentinel
  tail = new Node<>(null);  // back sentinel
  head.next = tail;
  tail.prev = head;
  size = 0;
}

With sentinels, a real node we want to remove always has a non-null node on each side. So unlink can be simplified to just the two rewiring lines:

private void unlink(Node<T> target) {
  target.prev.next = target.next;
  target.next.prev = target.prev;
  size--;
}

Other operations that change the shape of the list can also be simplified.

We could have built the whole chapter on sentinels from the start. We did not, on purpose. The version without sentinels makes every boundary case visible, so you see where the nulls force a special case and why. It makes up for the cases skipped earlier in this chapter.