Using a Linked List to Implement a Deque

We start with the linked list implementation, LinkedDeque, as we did for the queue.

Choosing a Doubly Linked List

A queue only needs to add at one end and remove from the other, so a singly linked list with a head and tail pointer is enough. The front is the head, the back is the tail, and both operations are $O(1)$.

A deque must support add and remove at both ends. So removing from the last end should cost the same as removing from the first end. Both should be $O(1)$.

A doubly linked list gives us this. The last node can point backward to the node before it, so removing the last node works the same way as removing the first node.

To make the implementation clean, we will use a pair of sentinel nodes, one at each end, as you saw in the linked-list chapter. This makes the code for adding and removing at either end the same, without any special cases for the empty deque or the one-node deque.

Operations and Complexity

isEmpty(): The deque is empty when there is nothing between the sentinels, that is, when head.next == tail. This is $O(1)$.

getFirst(): Return head.next.value after checking that the deque is not empty. This is $O(1)$.

getLast(): Return tail.prev.value after checking that the deque is not empty. This is $O(1)$.

addFirst(T item): Insert a new node just after the front sentinel, head. This is $O(1)$.

addLast(T item): Insert a new node just before the back sentinel, tail. This is $O(1)$.

removeFirst(): Unlink the first real node, head.next. This is $O(1)$.

removeLast(): Unlink the last real node, tail.prev. This is $O(1)$.

Every operation is $O(1)$ in the worst case. The cost is one extra reference per node, the prev link, plus the two sentinel nodes.