# 3.3 Sentinel Nodes

A sentinel node is an artificial node placed at the boundary of a linked list. It usually does not store a real user value. Its purpose is to simplify algorithms by ensuring that important positions, especially the head and tail boundaries, always have a node that can be referenced safely.

In a singly linked list, the most common sentinel is a dummy head.

```text
dummy.next = head
```

The real list begins at `dummy.next`. The dummy node itself remains outside the data sequence.

## Problem

Many linked list algorithms have separate cases for the first node. Deleting the head, inserting before the head, or returning a modified head often requires special logic.

Without a sentinel, deletion may look like this:

```text
if head.value == target:
  head = head.next
else:
  prev = head
  cur = head.next
  while cur != null:
    if cur.value == target:
      prev.next = cur.next
      break
    prev = cur
    cur = cur.next
```

The first node must be handled separately because it has no predecessor.

## Solution

Use a dummy node before the head.

```text
dummy = new Node()
dummy.next = head

prev = dummy
cur = head

while cur != null:
  if cur.value == target:
    prev.next = cur.next
    break
  prev = cur
  cur = cur.next

head = dummy.next
```

Now every real node has a predecessor. Even the original head has `dummy` as its predecessor. The deletion rule becomes uniform.

## Core Invariant

During traversal, keep `prev.next == cur`.

```text
prev = dummy
cur = dummy.next

while cur != null:
  ...
```

This invariant gives the algorithm permission to delete `cur` by assigning:

```text
prev.next = cur.next
```

After this assignment, the list remains connected from `dummy.next`.

## Insert Before a Matched Node

A sentinel also simplifies insertion before a node that satisfies a condition.

```text
dummy.next = head
prev = dummy
cur = head

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

head = dummy.next
```

No special case is needed when insertion happens before the original head.

## Remove All Matching Nodes

Sentinels are especially useful when many nodes may be removed, including several at the front.

```text
dummy.next = head
prev = dummy
cur = head

while cur != null:
  if cur.value == target:
    prev.next = cur.next
    cur = cur.next
  else:
    prev = cur
    cur = cur.next

head = dummy.next
```

When a node is deleted, `prev` does not move. It must stay at the last retained node. When a node is retained, both `prev` and `cur` move forward.

## Sentinel in Doubly Linked Lists

A doubly linked list may use two sentinels: one before the first real node and one after the last real node.

```text
head.next = tail
tail.prev = head
```

Here `head` and `tail` are sentinel nodes, not real values. The list is empty when:

```text
head.next == tail
tail.prev == head
```

Insertion between two adjacent nodes becomes uniform.

```text
insert_between(left, right, new):
  new.prev = left
  new.next = right
  left.next = new
  right.prev = new
```

Deletion also becomes uniform.

```text
remove(node):
  left = node.prev
  right = node.next

  left.next = right
  right.prev = left

  node.prev = null
  node.next = null
```

Because every real node has both a predecessor and a successor, deletion never needs to ask whether the node is the first or last real node.

## Example: LRU Cache List

An LRU cache often stores entries in a doubly linked list. The most recently used entry is placed near the front. The least recently used entry is near the back. Sentinels make all moves O(1).

```text
head <-> most_recent <-> ... <-> least_recent <-> tail
```

Move a node to the front:

```text
remove(node)
insert_between(head, head.next, node)
```

Remove the least recently used node:

```text
node = tail.prev
remove(node)
```

These operations do not require special cases for one-element or empty lists, because the sentinels preserve the boundary structure.

## Complexity Summary

| Operation                       |         Without Sentinel |               With Sentinel |
| ------------------------------- | -----------------------: | --------------------------: |
| Delete head                     |             Special case |  Same as deletion elsewhere |
| Insert before head              |             Special case | Same as insertion elsewhere |
| Delete known doubly linked node | May need boundary checks |                     Uniform |
| Empty list handling             |           Often explicit |        Encoded by sentinels |
| Extra memory                    |                     O(1) |                        O(1) |

## Common Failure Modes

A sentinel must not be treated as a real data node. Traversal over a doubly linked list with head and tail sentinels should usually start at `head.next` and stop before `tail`.

```text
cur = head.next
while cur != tail:
  process(cur.value)
  cur = cur.next
```

Another common error is returning `dummy` instead of `dummy.next` after modifying a singly linked list. The dummy node is only a construction aid. The real list starts after it.

Sentinels reduce branching, but they do not remove the need for invariants. In a singly linked list, preserve `prev.next == cur`. In a doubly linked list, preserve the bidirectional condition that adjacent nodes point back to each other.