3.20 Queue via List

A queue is a first-in, first-out structure. The first value inserted is the first value removed. A singly linked list implements a queue efficiently when the structure keeps both a head pointer and a tail pointer.

The head points to the next node to remove. The tail points to the last node inserted.

Queue {
  head : Node | null
  tail : Node | null
}

Structure

Each node stores a value and a pointer to the next node.

Node {
  value
  next : Node | null
}

The queue invariant is:

if head == null, then tail == null
if head != null, then tail != null
tail.next == null

An empty queue has both pointers set to null.

Enqueue

To enqueue, append a node at the tail.

enqueue(queue, value):
  node = Node(value)
  node.next = null

  if queue.tail == null:
    queue.head = node
    queue.tail = node
  else:
    queue.tail.next = node
    queue.tail = node

The empty case is special because there is no old tail. After inserting the first node, both head and tail must point to that node.

Dequeue

To dequeue, remove the head node.

dequeue(queue):
  if queue.head == null:
    error

  node = queue.head
  queue.head = node.next

  if queue.head == null:
    queue.tail = null

  node.next = null
  return node.value

The important edge case is removing the only node. After removal, head becomes null, so tail must also become null.

Peek

Return the front value without removing it.

peek(queue):
  if queue.head == null:
    error
  return queue.head.value

Empty Check

is_empty(queue):
  return queue.head == null

Because the invariant requires head and tail to be null together, checking head is enough.

Execution Trace

Start with an empty queue.

head = null
tail = null

After enqueueing 1, 2, and 3:

head
 |
 v
1 -> 2 -> 3 -> null
          ^
          |
         tail

After one dequeue:

head
 |
 v
2 -> 3 -> null
     ^
     |
    tail

The removed node 1 is detached from the list.

Why the Tail Pointer Matters

Without a tail pointer, enqueue requires walking to the end of the list.

cur = head
while cur.next != null:
  cur = cur.next
cur.next = node

That makes enqueue O(n). With a tail pointer, enqueue is O(1).

Complexity

The queue stores one node per element, so total storage is O(n).

Ownership Considerations

In a manual-memory language, dequeue should either return the node to the caller or free it after extracting the value.

node = queue.head
queue.head = node.next
node.next = null
free(node)

In a garbage-collected language, detaching the node is usually enough.

Queue with Dummy Head

A dummy head can simplify dequeue logic, but the queue still needs a tail pointer for O(1) enqueue.

dummy.next = null
tail = dummy

Enqueue:

tail.next = node
tail = node

Dequeue:

if dummy.next == null:
  error

node = dummy.next
dummy.next = node.next

if dummy.next == null:
  tail = dummy

node.next = null
return node.value

This version has a stable node before the first real element. The empty queue condition becomes dummy.next == null.

Common Failure Modes

The most common bug is forgetting to reset tail when the last node is removed. This leaves tail pointing to a detached node.

Another common bug is forgetting to set node.next = null before appending. If the node was previously part of another list, it may carry stale links into the queue.

A third bug is implementing enqueue without a tail pointer and accidentally making every enqueue O(n).

Key Insight

A linked-list queue needs two endpoints. The head supports O(1) removal from the front, and the tail supports O(1) insertion at the back. Correctness depends on keeping both endpoints consistent, especially when the queue changes between empty and non-empty states.