Linked list fundamentals: sentinels, pointer rewiring, doubly-linked design

Open java.util.LinkedList in OpenJDK and look at the linkBefore method. It carries a special case: if the predecessor is null, this is the first node, so update the head reference; otherwise, splice the new node into the chain. CLRS §10.2 shows you can delete that special case for free. Insert one fake node before the real head, treat its next as the head, and the predecessor is never null. The rewire becomes two assignments. The if (f == null) branch vanishes.

That fake node is the sentinel, and the technique generalises beyond linked lists to any data structure whose code branches on "am I at the boundary?" Most of Part 5 stands on it. Reversal in chapter 5.1, group reversal in chapter 5.2, the merge builder in chapter 5.4, the LRU cache's doubly-linked spine in chapter 5.5: every one of those algorithms reads more cleanly because the sentinel is doing the case-work the code would otherwise have to. The chapter you are reading is the one that pays for it once.^[1]

The contract is small. A node holds a value and a pointer to the next node. A list is a chain of nodes ending in null. An empty list is a list with no real nodes, and in the sentinel design it is a single dummy node whose next is null. Five public operations: read by index, insert at the head, insert at the tail, insert at an arbitrary index, delete at an arbitrary index. The signature problem is Design Linked List on LeetCode (LC 707), and solving it cleanly is the proof that you have internalised what this chapter teaches.

What a linked list is#

A node is a value packaged with a pointer:

@dataclass
class ListNode:
    val: int
    next: Optional["ListNode"] = None

That's the whole structural definition. A list is a chain: head -> node -> node -> ... -> null. Reading the chain is a while curr != null loop. There is no index, no arr[i], no contiguous block of memory. To find the third element, you walk from the head, three pointer dereferences in.

Three nodes, three heap allocations, three pointers between them. Random access is O(n); insertion in the middle, given the predecessor, is O(1). Arrays make the opposite trade.

The trade is the reason linked lists exist. A dynamic array (the Dynamic array internals chapter) gives you O(1) random access by indexing into a contiguous buffer, and pays for it with O(n) inserts in the middle: every element to the right has to shift one slot. A linked list inverts that bargain. There is no buffer to shift, so middle inserts and middle deletes are O(1) once you have a pointer at the predecessor. There is no contiguous layout, so reading the k-th element costs k dereferences, and each dereference, in the worst case, fetches a cache line that has nothing to do with the previous one.^[2]

That cache penalty is real. CLRS §10.2 frames the comparison in algorithmic terms; the engineering reality is that in a std::vector<int> with 8-byte ints, sixteen consecutive elements share a 64-byte cache line, so iterating costs roughly one fetch per sixteen reads. In a std::list<int>, every node is its own heap allocation, the nodes scatter across the heap, and iterating costs roughly one fetch per read. On the workloads where both representations are correct, the array beats the linked list by a factor of ten to twenty in practice.^[3]

So when does the linked list win? When the operations are splice in the middle, splice out from the middle, or splice two lists together at the ends, all of them given a pointer that is already at the right place. The LRU cache (chapter 5.5) is the canonical case: it has to evict the least-recently-used entry in O(1) and promote a touched entry to the front in O(1), and a hash map points directly at the relevant node so neither operation needs to walk anything. The linked list is the only data structure that makes both moves O(1) without amortization.

The four pointer primitives#

Every operation in this chapter is one of four shapes. Walk a prev pointer to position k, then do one of:

• Insert after prev: node.next = prev.next; prev.next = node;
• Delete the node after prev: prev.next = prev.next.next;
• Read by walking curr from the head: for k steps: curr = curr.next;
• Append at the tail: walk prev to the last node, then insert after.

The two-line insert is the entire mechanic, and the order of the two lines matters. Snapshot the forward link first; mutate the predecessor's next second. Reverse the order and the second line reads from a pointer the first line just clobbered, the new node points at itself, and the rest of the list orphans. We come back to this in pitfalls.

The delete is one line because the unlinked node walks itself out of the chain: setting prev.next = prev.next.next skips the old prev.next entirely. In a garbage-collected language the orphaned node disappears at the next GC pass. In C++ you capture the pointer first and delete victim; after the rewire; the destructor walks the chain on object teardown for the same reason.

What these four primitives have in common is the predecessor pointer. Insert needs prev because the new node has to splice in after something. Delete needs prev because removing a node mutates the upstream next, not the node itself. Read needs curr only, but the index walker that produces curr is the same loop as the one that produces prev, off by one step.

The annoying case is when prev would be null, the case where the operation is at the head. Without a sentinel, the code has to special-case it. If we are inserting at the head, set head = node and link node.next to the old head. Otherwise walk prev and do the normal rewire. Two paths, two correctness arguments, two places for an off-by-one to hide. OpenJDK's LinkedList carries this branch; it has to, because Java's standard library predates the convention of storing the sentinel inside the data structure.^[1:1]

The sentinel: one node that erases the head case#

Allocate one extra node, owned by the data structure, and put it before the real head. Call it dummy. Its next points at the first real element when one exists, and at null when the list is empty. The val field is unused.

class MyLinkedList:
    def __init__(self) -> None:
        self.dummy: ListNode = ListNode(0)
        self.length: int = 0

Now prev = dummy is a valid starting state for every indexed operation. Insert at index 0 is prev = dummy; insert at index k is prev = dummy followed by k advances. The body of the operation is the same in both cases. The empty-list invariant, the list has no real nodes, is dummy.next == null, and the rewire prev.next = node works on it without inspection.^[1:2]

There is a tax. The sentinel is one extra allocation per list, and every traversal starts from dummy rather than from the first real node. On a 64-bit JVM, that is 32 to 40 bytes per list and one extra dereference per indexed operation.^[4] The tax is small enough that production-quality data structures pay it routinely; the sentinel-free design is faster only when you measure micro-benchmarks on lists shorter than ten elements, and at that size you should be using an array anyway.

The half-sentinel form this chapter teaches puts the dummy before the head only. There is no tail sentinel and no separate tail pointer. That means addAtTail walks the whole chain. The full doubly-linked form with two sentinels (head and tail) gives you O(1) tail operations at the cost of doubling the per-node pointer overhead and complicating every rewire to four assignments instead of two. Chapter 5.5 introduces it because the LRU cache demands O(1) tail eviction; this chapter does not, because the half-sentinel form is the cleaner pedagogy and LC 707's contract treats indexed operations as primary.

Designing the list: LC 707#

Five operations, one data structure. The contract: get(i) returns the value at index i or -1 if i is out of range; addAtHead(v) and addAtTail(v) are convenience wrappers; addAtIndex(i, v) inserts a new node so that the new node's index becomes i; deleteAtIndex(i) removes the node at index i. Insert allows i == length (the append target); delete does not (there is no node at position length). Negative indices and out-of-range indices are silent no-ops on mutators and return -1 on get.^[5]

Every method body collapses to "walk prev to position i - 1 (the sentinel covers i == 0), then do the canonical rewire."

# LC 707. Design Linked List
"""LC 707 Design Linked List, sentinel-driven singly linked list.

The dummy head removes the head-vs-mid case split: every insert and
delete points at a non-null predecessor `prev`, so the wiring is the
same at index 0 and at index k.
"""

from dataclasses import dataclass
from typing import Optional


@dataclass
class ListNode:
    val: int
    next: Optional["ListNode"] = None


class MyLinkedList:
    def __init__(self) -> None:
        self.dummy: ListNode = ListNode(0)
        self.length: int = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.length:
            return -1
        curr = self.dummy.next
        for _ in range(index):
            curr = curr.next  # type: ignore[union-attr]
        return curr.val  # type: ignore[union-attr]

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.length, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.length:
            return
        prev = self.dummy
        for _ in range(index):
            prev = prev.next  # type: ignore[assignment]
        node = ListNode(val, prev.next)
        prev.next = node
        self.length += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.length:
            return
        prev = self.dummy
        for _ in range(index):
            prev = prev.next  # type: ignore[assignment]
        prev.next = prev.next.next  # type: ignore[union-attr]
        self.length -= 1

// LC 707. Design Linked List
/* Sentinel-driven singly linked list. The dummy head removes the
 * head-vs-mid case split: every insert and delete points at a
 * non-null predecessor `prev`, so the wiring is the same at index 0
 * and at index k.
 */
public final class Sol {

    private static final class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    private final ListNode dummy = new ListNode(0);
    private int length = 0;

    public Sol() {}

    public int get(int index) {
        if (index < 0 || index >= length) return -1;
        ListNode curr = dummy.next;
        for (int i = 0; i < index; i++) curr = curr.next;
        return curr.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(length, val);
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > length) return;
        ListNode prev = dummy;
        for (int i = 0; i < index; i++) prev = prev.next;
        ListNode node = new ListNode(val);
        node.next = prev.next;
        prev.next = node;
        length++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= length) return;
        ListNode prev = dummy;
        for (int i = 0; i < index; i++) prev = prev.next;
        prev.next = prev.next.next;
        length--;
    }
}

// LC 707. Design Linked List
// Sentinel-driven singly linked list. The dummy head removes the
// head-vs-mid case split: every insert and delete points at a
// non-null predecessor `prev`, so the wiring is the same at index 0
// and at index k.
#pragma once

class MyLinkedList {
public:
    MyLinkedList() : dummy(new ListNode(0)), length(0) {}

    ~MyLinkedList() {
        ListNode* curr = dummy;
        while (curr != nullptr) {
            ListNode* next = curr->next;
            delete curr;
            curr = next;
        }
    }

    int get(int index) {
        if (index < 0 || index >= length) return -1;
        ListNode* curr = dummy->next;
        for (int i = 0; i < index; ++i) curr = curr->next;
        return curr->val;
    }

    void addAtHead(int val) { addAtIndex(0, val); }
    void addAtTail(int val) { addAtIndex(length, val); }

    void addAtIndex(int index, int val) {
        if (index < 0 || index > length) return;
        ListNode* prev = dummy;
        for (int i = 0; i < index; ++i) prev = prev->next;
        ListNode* node = new ListNode(val);
        node->next = prev->next;
        prev->next = node;
        ++length;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= length) return;
        ListNode* prev = dummy;
        for (int i = 0; i < index; ++i) prev = prev->next;
        ListNode* victim = prev->next;
        prev->next = victim->next;
        delete victim;
        --length;
    }

private:
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int v) : val(v), next(nullptr) {}
    };
    ListNode* dummy;
    int length;
};

// LC 707. Design Linked List
// Sentinel-driven singly linked list. The dummy head removes the
// head-vs-mid case split: every insert and delete points at a
// non-null predecessor `prev`, so the wiring is the same at index 0
// and at index k.
package main

type listNode struct {
	val  int
	next *listNode
}

type MyLinkedList struct {
	dummy  *listNode
	length int
}

func Constructor() MyLinkedList {
	return MyLinkedList{dummy: &listNode{}, length: 0}
}

func (l *MyLinkedList) Get(index int) int {
	if index < 0 || index >= l.length {
		return -1
	}
	curr := l.dummy.next
	for i := 0; i < index; i++ {
		curr = curr.next
	}
	return curr.val
}

func (l *MyLinkedList) AddAtHead(val int) { l.AddAtIndex(0, val) }
func (l *MyLinkedList) AddAtTail(val int) { l.AddAtIndex(l.length, val) }

func (l *MyLinkedList) AddAtIndex(index, val int) {
	if index < 0 || index > l.length {
		return
	}
	prev := l.dummy
	for i := 0; i < index; i++ {
		prev = prev.next
	}
	node := &listNode{val: val, next: prev.next}
	prev.next = node
	l.length++
}

func (l *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= l.length {
		return
	}
	prev := l.dummy
	for i := 0; i < index; i++ {
		prev = prev.next
	}
	prev.next = prev.next.next
	l.length--
}

The two-line insert and the one-line delete are the only mutations. Everything else is index walking. The length field is the source of truth for index validity. Drift between length and the actual chain length causes silent wrong answers, and the reference puts every counter update on the same line-level scope as the rewire so a code reviewer sees both changes in a three-line diff.

Trace the LC 707 operation sequence on a fresh list:

1. addAtHead(1) routes to addAtIndex(0, 1). prev = dummy. Allocate node 1; rewire; length = 1. Chain: dummy -> 1.
2. addAtTail(3) routes to addAtIndex(1, 3). Walk prev once to node 1. Allocate node 3; rewire; length = 2. Chain: dummy -> 1 -> 3.
3. addAtIndex(1, 2). prev = dummy; advance once to node 1. Allocate node 2 with next = node 3; rewire prev.next = node 2; length = 3. Chain: dummy -> 1 -> 2 -> 3.
4. get(1) returns 2.
5. deleteAtIndex(1). prev = dummy; advance once to node 1. Capture victim = node 2; rewire prev.next = victim.next; length = 2. Chain: dummy -> 1 -> 3.
6. get(1) returns 3.

Static fallback: the widget's four key frames render the empty sentinel state, the chain after both head and tail inserts, the chain immediately after the mid-insert with node 2 spliced between nodes 1 and 3, and the chain after the mid-delete reverts to dummy -> 1 -> 3.

The thing the trace makes visible is that step 1 (head-insert) and step 3 (mid-insert) are the same operation. Same predecessor type (the sentinel for one, a real node for the other, but both non-null). Same two-line rewire. Same length update. The reader who watches steps 1 and 3 happen one after the other has internalised the chapter.

A second shape: the dummy-head builder#

The sentinel has a second life beyond owning a list's head. Add Two Numbers (LC 2) hands you two linked lists of digits in reverse order and asks you to return their sum as a linked list.^[6] You don't know how long the answer is until you have walked both inputs, and you cannot append to a chain in O(1) without a tail pointer. The fix is the same trick: allocate a dummy locally, walk a tail pointer, append unconditionally, return dummy.next.

# LC 2. Add Two Numbers
"""Synchronized two-list walk with carry propagation. The dummy head
lets every iteration append unconditionally; `return dummy.next` skips
the sentinel."""

from dataclasses import dataclass
from typing import Optional


@dataclass
class ListNode:
    val: int = 0
    next: Optional["ListNode"] = None


class Solution:
    def addTwoNumbers(
        self,
        l1: Optional[ListNode],
        l2: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode()
        tail = dummy
        carry = 0
        while l1 is not None or l2 is not None or carry:
            v1 = l1.val if l1 is not None else 0
            v2 = l2.val if l2 is not None else 0
            total = v1 + v2 + carry
            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next
        return dummy.next

// LC 2. Add Two Numbers
// Synchronized two-list walk with carry propagation. The dummy head
// lets every iteration append unconditionally; `return dummy.next`
// skips the sentinel.
public final class Sol {

    public static final class ListNode {
        public int val;
        public ListNode next;
        public ListNode() {}
        public ListNode(int val) { this.val = val; }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int v1 = (l1 != null) ? l1.val : 0;
            int v2 = (l2 != null) ? l2.val : 0;
            int total = v1 + v2 + carry;
            carry = total / 10;
            tail.next = new ListNode(total % 10);
            tail = tail.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}

// LC 2. Add Two Numbers
// Synchronized two-list walk with carry propagation. The dummy head
// lets every iteration append unconditionally; `return dummy.next`
// skips the sentinel.
#pragma once

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int v) : val(v), next(nullptr) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy;
        ListNode* tail = &dummy;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int v1 = (l1 != nullptr) ? l1->val : 0;
            int v2 = (l2 != nullptr) ? l2->val : 0;
            int total = v1 + v2 + carry;
            carry = total / 10;
            tail->next = new ListNode(total % 10);
            tail = tail->next;
            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }
        return dummy.next;
    }
};

// LC 2. Add Two Numbers
// Synchronized two-list walk with carry propagation. The dummy head
// lets every iteration append unconditionally; returning dummy.Next
// skips the sentinel.
package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	carry := 0
	for l1 != nil || l2 != nil || carry != 0 {
		v1, v2 := 0, 0
		if l1 != nil {
			v1 = l1.Val
		}
		if l2 != nil {
			v2 = l2.Val
		}
		total := v1 + v2 + carry
		carry = total / 10
		tail.Next = &ListNode{Val: total % 10}
		tail = tail.Next
		if l1 != nil {
			l1 = l1.Next
		}
		if l2 != nil {
			l2 = l2.Next
		}
	}
	return dummy.Next
}

Two things to notice. The loop guard is l1 != null OR l2 != null OR carry: the carry is part of the termination condition because adding [5] and [5] produces [0, 1] with a carry that survives both inputs running out. And the return is dummy.next, not dummy. Return the dummy itself and the result list starts with a spurious 0 followed by the real digits. The naming is what enforces the discipline: call the local dummy (not head) and return dummy.next reads as skip the sentinel; return the real head. The merge builder in Merge two/k sorted lists and the heap-driven k-way merge in Heaps reuse this pattern.

A linked list that actually feels like a one-way iterator, read each value and do something with it, is Convert Binary Number in a Linked List to Integer (LC 1290). Each node holds a 0 or 1; the list is the binary representation MSB-first; the answer is the integer.^[7] Single pass:

# LC 1290. Convert Binary Number in a Linked List to Integer
"""Single-pass walk with a running accumulator. Each node holds 0 or 1;
shift the result left and OR in the current bit.
"""

from dataclasses import dataclass
from typing import Optional


@dataclass
class ListNode:
    val: int
    next: Optional["ListNode"] = None


class Solution:
    def getDecimalValue(self, head: Optional[ListNode]) -> int:
        result = 0
        curr = head
        while curr is not None:
            result = (result << 1) | curr.val
            curr = curr.next
        return result

// LC 1290. Convert Binary Number in a Linked List to Integer
// Single-pass walk with a running accumulator. Each node holds 0 or 1;
// shift the result left and OR in the current bit.
public final class Sol {

    public static final class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) { this.val = val; }
    }

    public int getDecimalValue(ListNode head) {
        int result = 0;
        ListNode curr = head;
        while (curr != null) {
            result = (result << 1) | curr.val;
            curr = curr.next;
        }
        return result;
    }
}

// LC 1290. Convert Binary Number in a Linked List to Integer
// Single-pass walk with a running accumulator. Each node holds 0 or 1;
// shift the result left and OR in the current bit.
#pragma once

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int result = 0;
        ListNode* curr = head;
        while (curr != nullptr) {
            result = (result << 1) | curr->val;
            curr = curr->next;
        }
        return result;
    }
};

// LC 1290. Convert Binary Number in a Linked List to Integer
// Single-pass walk with a running accumulator. Each node holds 0 or 1;
// shift the result left and OR in the current bit.
package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func getDecimalValue(head *ListNode) int {
	result := 0
	curr := head
	for curr != nil {
		result = (result << 1) | curr.Val
		curr = curr.Next
	}
	return result
}

The while curr != null loop is the most common shape in Part 5. Every chapter from 5.1 onward starts a function with it. The line result = (result << 1) | curr.val is the only arithmetic; everything else is the walk.

What it actually costs#

Index-walking dominates everything. Every method that takes an index argument runs in time proportional to the index, because the walker has to traverse index nodes to reach the predecessor.

The half-sentinel design (sentinel before the head, no tail pointer) is what makes head insertions and head deletions O(1): the case split is gone, but there is no separate tail pointer, so tail operations pay an O(n) walk. CLRS §10.2 proves the bounds: LIST-INSERT and LIST-DELETE each do a constant number of pointer rewires after the search step, so the search step dominates.^[1:4] The textbook upgrade that takes addAtTail to O(1) is to add a tail pointer; chapter 5.5 reintroduces it because the LRU cache demands O(1) tail eviction without ever indexing.

The space bound is n + 1 heap nodes (the n real nodes plus the sentinel) plus a constant for the length counter. Per-node space is dominated by the pointer field. On a 64-bit JVM with compressed object pointers, a ListNode with one int and one reference consumes 32 to 40 bytes per node, three to four times what a int[] would for the same payload.^[4:1] Python with a dataclass-decorated node consumes around 56 bytes per instance. C++ with a plain struct ListNode { int val; ListNode* next; } is 16 bytes. Go's struct of int plus pointer is also 16 bytes. The constants matter when you are deciding between a linked list and an array; once you have decided, they are noise.

When the design changes#

Three variants of this chapter's idiom show up later in Part 5 and beyond. The first two reuse what you just learned; the third is the no-sentinel form OpenJDK ships, which the chapter cites as the worked counter-example.

The full doubly-linked sentinel design (chapter 5.5). Two sentinels, head and tail. Every node carries both prev and next. Insertion is four assignments instead of two: node.prev = head; node.next = head.next; head.next.prev = node; head.next = node. Deletion is two: node.prev.next = node.next; node.next.prev = node.prev. The four-assignment insert is harder to internalise than the two-assignment one; chapter 5.5 has the LRU cache to motivate the cost. You don't pay it without a reason.

The no-sentinel singly linked list (OpenJDK style). A nullable first and last reference instead of a sentinel. The addAtIndex(0, ...) path branches: if (length == 0) head = node; else { node.next = head; head = node; }. The case split is small, but it accumulates across every mutator and every reviewer has to re-derive the boundary correctness. OpenJDK's java.util.LinkedList ships this design, and pays for it with if (f == null) branches inside linkFirst, linkLast, and unlink.^[1:5] If you find yourself writing twice as many lines as the sentinel reference above, this is the design you accidentally landed on.

The circular linked list (referenced, not taught here). The tail's next points at a real node rather than at null. Iteration uses curr != head_after_one_loop instead of curr != null. The Josephus problem and round-robin schedulers are the natural consumers; the algorithmic problem of recognising a cycle is owned by Cycle detection, where Floyd's tortoise-and-hare pointer arithmetic does the work in O(1) extra space.

Skip lists and unrolled linked lists are real data structures that show up in Redis sorted sets and a few specialised engines.^[8] They fit in chapter 11 alongside the other probabilistic structures; this chapter mentions them so you know they exist.

Where readers go wrong#

Problem ladder#

CORE (solve all three to claim chapter mastery)#

• LC 1290 — Convert Binary Number in a Linked List to Integer [Easy] • linked-list-traversal
• LC 707 — Design Linked List [Medium] • linked-list-sentinel ★
• LC 2 — Add Two Numbers [Medium] • linked-list-traversal-with-carry

STRETCH (optional)#

• LC 138 — Copy List with Random Pointer [Medium] • linked-list-deep-copy
• LC 1019 — Next Greater Node In Linked List [Medium] • linked-list-as-iterator

Where this leads#

Reversal patterns reuses the ListNode definition and the snapshot-first rule; the prev/curr/next three-pointer rewire is the same shape, applied to every node in turn instead of one node at a time. Cycle detection drops the sentinel because Floyd's tortoise-and-hare reasons about the original successor function. Merge two/k sorted lists keeps the dummy-head builder pattern from Add Two Numbers and uses it as the merge primitive. And LRU cache introduces the doubly-linked sentinel design that this chapter only references: two sentinels, four-assignment inserts, O(1) at both ends. Same node type, four different disciplines.

References#