Implementing getFirst, getLast, removeFirst, and removeLast

Here are the two getters:

@Override
public T getFirst() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  return head.next.value;
}

@Override
public T getLast() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  return tail.prev.value;
}

The remove operations share a helper. It is similar to the unlink from the linked-list chapter’s sentinel list:

private void removeNode(Node<T> target) {
  Node<T> before = target.prev;
  Node<T> after = target.next;
  before.next = after;
  after.prev = before;
}

Here is removeFirst:

@Override
public void removeFirst() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  removeNode(head.next);
}

For the common case, start with three real nodes and unlink the first one, 3:

          ┌─────┐      ┌───┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 3 │ ◀──▶ │ 5 │ ◀──▶ │ 7 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └───┘      └─────┘
             ↑           ↑          ↑
          before      target      after

removeNode links the front sentinel and the node holding 5 directly to each other, so neither of them points to 3 any more:

          ┌─────┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 5 │ ◀──▶ │ 7 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └─────┘
             ↑           ↑          
           before       after
            (target skipped)

When 3 is the only real node, the same two lines link the two sentinels back to each other, leaving an empty deque.

removeLast does the same at the other end:

@Override
public void removeLast() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  removeNode(tail.prev);
}

Again start with three real nodes, but this time unlink the last one, 7:

          ┌─────┐      ┌───┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 3 │ ◀──▶ │ 5 │ ◀──▶ │ 7 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └───┘      └─────┘
                                    ↑          ↑          ↑
                                  before     target      after

removeNode links the node holding 5 and the back sentinel directly to each other, so neither of them points to 7 any more:

          ┌─────┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 3 │ ◀──▶ │ 5 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └─────┘
                                    ↑           ↑          
                                 before       after
                                  (target skipped)

That completes LinkedDeque.