The LinkedDeque Class

Here is the class, with its node, fields, and constructor:

public class LinkedDeque<T> implements Deque<T> {

  private final Node<T> head;  // front sentinel
  private final Node<T> tail;  // back sentinel

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

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

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

  // ... the operations will go here
}

This is the sentinel list from the linked-list chapter. Once the constructor runs, head and tail never point at any other node, so both fields are final.

Here is an empty deque:

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

Here is the deque holding 4, 9, 6:

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

With this representation, a few invariants hold:

• The first real node is head.next, and the last real node is tail.prev.
• The deque is empty exactly when head.next == tail.
• For neighboring nodes, the links agree: if a.next == b, then b.prev == a.

The isEmpty operation checks the second invariant:

@Override
public boolean isEmpty() {
  return head.next == tail;
}