Linked Implementation of Queue
A singly linked list can be used to implement the Queue ADT efficiently as long as it has a tail pointer (as well as the head pointer). The tail pointer is a reference variable pointing to the other end (opposite of head) of the queue.
Exercise Think about how to implement a queue using a singly linked list such that the core operations are constant time.
| Operation | How? | Time |
|---|---|---|
enqueue | $O(1)$ | |
dequeue | $O(1)$ | |
front | $O(1)$ | |
empty | $O(1)$ |
Solution
The front of the queue would be the HEAD node of the singly linked list. The back of the queue would be the TAIL node of the singly linked list. Every time we want to enqueue an additional value to the queue, we would create a new node and set it as the new TAIL node. Then when we want to dequeue a value from the front of the queue, we set the HEAD to the current HEAD node's .next. As such, the HEAD node will always be at the front of the queue, and calling front would return the value of the HEAD node.
| Operation | How? | Time |
|---|---|---|
enqueue | prepend the list and update the tail | $O(1)$ |
dequeue | delete from front: head = head.next | $O(1)$ |
front | return head.data | $O(1)$ |
empty | check if head is null | $O(1)$ |