3.12 Dummy Heads (Dummy Nodes)

A dummy head is a fixed node placed before the real head of a singly linked list. It does not carry user data. It provides a stable predecessor for every real node, including the original head. This removes most boundary cases from insertion and deletion.

Problem

Algorithms that modify the first node require special handling because the head has no predecessor. This leads to branching logic and error-prone code paths.

Construction

Create a dummy node and point it to the current head.

dummy = new Node()
dummy.next = head

All operations proceed from dummy. The final result is returned as:

dummy.next

Core Invariant

Maintain:

prev.next == cur

with initialization:

prev = dummy
cur = dummy.next

This invariant makes deletion and insertion uniform at all positions.

Unified Deletion

Delete the first node that matches a condition.

dummy.next = head

prev = dummy
cur = head

while cur != null:
  if match(cur):
    prev.next = cur.next
    cur.next = null
    break
  prev = cur
  cur = cur.next

head = dummy.next

No special case for deleting the original head.

Unified Insertion Before

Insert before a node that satisfies a condition.

dummy.next = head

prev = dummy
cur = head

while cur != null:
  if condition(cur):
    new.next = cur
    prev.next = new
    break
  prev = cur
  cur = cur.next

head = dummy.next

Insertion before the original head follows the same rule.

Remove All Matches

Dummy nodes simplify repeated deletions.

dummy.next = head

prev = dummy
cur = head

while cur != null:
  if match(cur):
    next = cur.next
    prev.next = next
    cur.next = null
    cur = next
  else:
    prev = cur
    cur = cur.next

head = dummy.next

The invariant ensures that prev always points to the last retained node.

Multiple Dummy Heads

Some algorithms use more than one dummy node to construct multiple output lists.

Example: partition by predicate.

yes_dummy = new Node()
no_dummy = new Node()

yes_tail = yes_dummy
no_tail = no_dummy

Nodes are distributed between the two lists, and then combined if needed.

Dummy Head vs Sentinel

A dummy head is a single node used only at the front of a singly linked list.

A sentinel usually refers to boundary nodes in a doubly linked list, often both head and tail sentinels.

head <-> ... <-> tail

Both serve the same purpose: remove boundary conditions.

Example: Remove Nth Node from End

dummy.next = head

lead = dummy
follow = dummy

for i in 1..n+1:
  lead = lead.next

while lead != null:
  lead = lead.next
  follow = follow.next

node = follow.next
follow.next = node.next
node.next = null

return dummy.next

Without the dummy node, deleting the first node would require a separate branch.

Complexity

The dummy node does not change asymptotic complexity. It reduces branching and error risk.

Common Failure Modes

Returning dummy instead of dummy.next produces an incorrect list.

Traversing from dummy instead of dummy.next may treat the dummy as real data.

Forgetting to update head from dummy.next leaves the external reference unchanged.

Key Insight

A dummy head converts a partial structure into a uniform one. Every node gains a predecessor, so insertion and deletion become local operations with the same rule everywhere. This reduces special cases and makes invariants easier to maintain.