Solution: Fields and Constructor

Before we write any operations, we need to decide what fields the list has.

In the version from the chapter, head points at the first real node and tail points at the last real node. In the sentinel version, head and tail point at sentinel nodes instead:

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

Solution

The state is still head, tail, and size, but head and tail now refer to sentinel nodes:

public class LinkedList<T> {

  private Node<T> head;  // front sentinel
  private Node<T> tail;  // back sentinel
  private int size;  // number of real nodes

  private static class Node<T> {
    T value;
    Node<T> next;
    Node<T> prev;

    Node(T value) {
      this.value = value;
    }
  }

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

  public int size() {
    return size;
  }
}

The sentinels hold null, but that null is not a list value. The real values are always between head and tail, and size counts only those real nodes.