Implement a queue by a singly linked list \(L\). The operations ENQUEUE and DEQUEUE should still take \(O(1)\) time.

In order to achieve the required time complexity, we must modify the singly linked list data structure to retain a pointer to the tail of the list as it does the head. Furthermore, we must enqueue new elements to the tail and dequeue from the head in order to avoid list traversal.

ENQUEUE-VIA-LIST(L, x)

1 node = new LinkedListNode(x)

2 if L.tail == NIL:

3     L.head = node

4     L.tail = node

5 else:

6     L.tail.next = node

7     L.tail = node

8 node.next = NIL

Line 8 would likely be handled by the constructor invoked on line 1 but I included it here for specificity.

DEQUEUE-VIA-LIST(L)

1 if L.head == NIL:

2     error "underflow"

3 result = L.head.key

4 if L.head == L.tail:

5     L.tail == NIL

6 L.head = L.head.next

7 return result

The logic on lines 4 and 5 handle the event in which a single value list has its head unset but the tail remains.