# 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.

```text id="d7m2k1"
dummy = new Node()
dummy.next = head
```

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

```text id="f2h9a8"
dummy.next
```

## Core Invariant

Maintain:

```text id="n4t6q3"
prev.next == cur
```

with initialization:

```text id="p8x1c5"
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.

```text id="c3r5u9"
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.

```text id="x6w2b7"
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.

```text id="z9k4h2"
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.

```text id="q5n8m1"
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.

```text id="k1p7z4"
head <-> ... <-> tail
```

Both serve the same purpose: remove boundary conditions.

## Example: Remove Nth Node from End

```text id="b2m9s6"
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

| Operation                 | Time | Space |
| ------------------------- | ---: | ----: |
| Setup dummy               | O(1) |  O(1) |
| Any traversal using dummy | O(n) |  O(1) |
| Insert/delete at head     | O(1) |  O(1) |

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.