Implementing LinkedDeque

Here is the Deque interface:

public interface Deque<T> {
  void addFirst(T item);  // throws IllegalArgumentException if item is null
  void addLast(T item);   // throws IllegalArgumentException if item is null
  void removeFirst();     // throws NoSuchElementException if the deque is empty
  void removeLast();      // throws NoSuchElementException if the deque is empty
  T getFirst();           // throws NoSuchElementException if the deque is empty
  T getLast();            // throws NoSuchElementException if the deque is empty
  boolean isEmpty();
}

LinkedDeque<T> implements the Deque<T> interface with a doubly linked list. There is a sentinel node at each end, and the real nodes are between them:

import java.util.NoSuchElementException;

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 go here
}

Solution

removeLast. Unlinking the tail node means making the node before it the new tail, and a singly linked list can only reach that node by traversing from the head, which is $O (n)$ . With a prev link in each node, the node before the tail is one step away.

Solution

The first real node is head.next and the last real node is tail.prev. The deque is empty exactly when head.next == tail, that is, when the two sentinels point at each other.

Solution

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

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

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

Solution

public void addFirst(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  Node<T> node = new Node<>(item);
  node.prev = head;
  node.next = head.next;
  head.next.prev = node;
  head.next = node;
}

public void addLast(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  Node<T> node = new Node<>(item);
  node.prev = tail.prev;
  node.next = tail;
  tail.prev.next = node;
  tail.prev = node;
}

Solution

public void removeFirst() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  Node<T> target = head.next;
  head.next = target.next;
  target.next.prev = head;
}

public void removeLast() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  Node<T> target = tail.prev;
  tail.prev = target.prev;
  target.prev.next = tail;
}

Solution

The sentinels are always there. A new node is always spliced between two existing nodes, and a real node always has a node on each side, so removing it links those two nodes to each other, even when the deque is empty or holds one item. Removing the only real node links the two sentinels back to each other, which is the empty deque.

Solution

All seven are $O (1)$ in the worst case. Each operation reads or changes only the two sentinels and at most two nodes next to them, with no traversal.