Solution: Adding with Sentinels

Now let’s add a value to the end of the list.

With sentinels, there is always a node after the last real node: the back sentinel. So appending means inserting a new node right before tail.

Solution

It helps to write a small private helper for the actual rewiring:

private Node<T> insertBetween(T value, Node<T> before, Node<T> after) {
  Node<T> node = new Node<>(value);
  node.prev = before;
  node.next = after;
  before.next = node;
  after.prev = node;
  size++;
  return node;
}

Then add is just:

public void add(T value) {
  insertBetween(value, tail.prev, tail);
}

Here is a list with two real values before the call:

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

After add(7), the new node is between the old last real node and the back sentinel:

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

Why does this handle the empty list? In an empty list, tail.prev is head. So the call becomes:

insertBetween(value, head, tail);

An empty list is just the two sentinels pointing at each other:

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

After add(7), the first real node goes between them:

          ┌─────┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 7 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └─────┘
                         ▲
                         │
                     new node
           front                   back
         sentinel                sentinel

No if (head == null) case, because head and tail are never null.