Using a Linked List to Implement a Queue

We will implement the Queue interface using a linked list (LinkedQueue) and an array (ArrayQueue). We start with the linked list this time, because it is the easier of the two. As before, we will design before we code: pick the representation, then work through the operations and their costs.

Assigning the Front and the Back

A linked list has two ends, the head and the tail. The queue also has two ends, the front and the back. We need to decide which end of the list is the front and which is the back. As we saw for the stack, adding and removing at the head are both $O(1)$, and adding at the tail is $O(1)$ with a tail pointer. Removing at the tail is $O(n)$ in a singly linked list, because unlinking the tail requires the node before it, and reaching that node means traversing from the head.

Let’s consider the front of the queue is the head of the list. We can then keep it a singly linked list with a tail pointer and implement all operations in $O(1)$. We will go with this approach.

If we chose the front of the queue to be the tail of the list, then we need a doubly linked list to keep all operations in $O(1)$.

Operations and Complexity

isEmpty(), front(), and dequeue(): These work as isEmpty, top, and pop do in LinkedStack, and each is $O(1)$. There is one detail to watch in dequeue: if the removed node was the only node, the tail pointer still points at it and must be cleared too.

enqueue(T item): Create a new node, link it after the tail, and make it the new tail. With the tail pointer, this is $O(1)$. There is a detail here too: if the queue is empty, there is no tail to link after, and the new node becomes both the head and the tail.

Every operation is $O(1)$ in the worst case.