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.

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:

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.

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.

prev = dummy
cur = dummy.next

while cur != null:
  ...

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

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.

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.

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.

head.next = tail
tail.prev = head

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

head.next == tail
tail.prev == head

Insertion between two adjacent nodes becomes uniform.

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

Deletion also becomes uniform.

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

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

Move a node to the front:

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

Remove the least recently used node:

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

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.

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.