Chapter 3. Linked Lists and Pointers – brain

Linked lists are the first data structure in this book where the shape of the data matters as much as the values stored inside it. An array gives direct access by index, but a linked list gives access through references from one node to the next. This changes the way algorithms are written. A solution must track not only what value is being inspected, but also which node owns the next link, which pointer must be preserved, and which edge in the list must be rewired.

This chapter develops linked list algorithms as pointer transformations. The basic operations are simple: create a node, follow a next pointer, insert a node, delete a node, and stop at nil. The difficulty comes from composition. Reversing a list, merging two sorted lists, detecting a cycle, or deleting the nth node from the end all require a small invariant about which part of the list has already been processed and which part remains untouched.

A recurring pattern is the use of sentinel nodes. A sentinel gives the algorithm a stable predecessor before the real head of the list. This removes many special cases, especially when the head itself may be inserted, deleted, or replaced. Another common pattern is the fast and slow pointer method, where two references move at different speeds to detect cycles, locate the middle, or split a list.

The chapter also treats linked lists as a way to study ownership and aliasing. Two variables may refer to the same node. Updating one link may change what another part of the program can reach. This is why linked list bugs are often structural rather than arithmetic: lost tails, accidental cycles, skipped nodes, double deletion, and stale references.

By the end of the chapter, you should be able to reason about linked list algorithms using three questions: which node am I holding, which link will I modify, and what part of the structure must remain reachable after the modification. This discipline will carry forward into trees, graphs, caches, and memory-sensitive systems.

3.1 Singly Linked ListsA singly linked list is a sequence of nodes where each node stores a value and a reference to the next node.

3.2 Doubly Linked ListsA doubly linked list is a sequence of nodes where each node stores a value, a reference to the next node, and a reference to the previous node.

3.3 Sentinel NodesA sentinel node is an artificial node placed at the boundary of a linked list.

3.4 ReversalReversal transforms a linked list so that the direction of all edges is flipped.

3.5 Cycle DetectionA cycle exists in a linked list when some node’s `next` pointer eventually leads back to a previously visited node.

3.6 Fast and Slow PointersFast and slow pointers are two references that traverse the same linked structure at different speeds.

3.7 Merge Two Sorted ListsMerging combines two sorted singly linked lists into one sorted list by relinking nodes.

3.8 Split PatternsSplitting a linked list means cutting one list into two or more lists while preserving the original nodes.

3.9 Merge PatternsMerging is a family of constructions that combine multiple linked lists into one or more output lists while preserving structural invariants.

3.10 Deletion PatternsDeletion removes one or more nodes from a linked list by changing links around them.

3.11 Insertion PatternsInsertion adds nodes into a linked list by creating new links while preserving reachability of all existing nodes.

3.12 Dummy Heads (Dummy Nodes)A dummy head is a fixed node placed before the real head of a singly linked list.

3.13 Pointer AliasingPointer aliasing occurs when two or more references point to the same node.

3.14 Persistent ListsA persistent list is a list that preserves older versions after an update.

3.15 Skip ListsA skip list augments a sorted linked list with multiple levels of forward pointers.

3.16 Intrusive ListsAn intrusive list stores the linkage fields inside the objects being linked.

3.17 Memory OwnershipMemory ownership describes which part of a program is responsible for creating, linking, unlinking, and destroying a node.

3.18 IteratorsAn iterator is an object or procedure that visits the nodes of a linked list one at a time.

3.19 Stack via ListA stack is a last-in, first-out (LIFO) structure.

3.20 Queue via ListA queue is a first-in, first-out structure.

3.21 LRU Cache StructureAn LRU cache stores a fixed number of key-value entries and removes the least recently used entry when capacity is exceeded.

3.22 Edge CasesEdge cases are inputs that sit near the boundary of an algorithm's assumptions.

3.23 Testing Pointer CodePointer code should be tested by checking structure, not only values.

3.24 Complexity AnalysisLinked list algorithms are dominated by pointer traversal and constant-time link updates.

3.25 Case StudiesThis section combines multiple patterns from the chapter into complete, end-to-end linked list algorithms.