3.25 Case Studies
This section combines multiple patterns from the chapter into complete, end-to-end linked list algorithms.
Tag
Linked-Lists
26 notes
3.24 Complexity Analysis
Linked list algorithms are dominated by pointer traversal and constant-time link updates.
3.23 Testing Pointer Code
Pointer code should be tested by checking structure, not only values.
3.22 Edge Cases
Edge cases are inputs that sit near the boundary of an algorithm's assumptions.
3.21 LRU Cache Structure
An LRU cache stores a fixed number of key-value entries and removes the least recently used entry when capacity is exceeded.
3.20 Queue via List
A queue is a first-in, first-out structure.
3.19 Stack via List
A stack is a last-in, first-out (LIFO) structure.
3.18 Iterators
An iterator is an object or procedure that visits the nodes of a linked list one at a time.
3.17 Memory Ownership
Memory ownership describes which part of a program is responsible for creating, linking, unlinking, and destroying a node.
3.16 Intrusive Lists
An intrusive list stores the linkage fields inside the objects being linked.
3.15 Skip Lists
A skip list augments a sorted linked list with multiple levels of forward pointers.
3.14 Persistent Lists
A persistent list is a list that preserves older versions after an update.
3.13 Pointer Aliasing
Pointer aliasing occurs when two or more references point to the same node.
3.12 Dummy Heads (Dummy Nodes)
A dummy head is a fixed node placed before the real head of a singly linked list.
3.11 Insertion Patterns
Insertion adds nodes into a linked list by creating new links while preserving reachability of all existing nodes.
3.10 Deletion Patterns
Deletion removes one or more nodes from a linked list by changing links around them.
3.9 Merge Patterns
Merging is a family of constructions that combine multiple linked lists into one or more output lists while preserving structural invariants.
3.8 Split Patterns
Splitting a linked list means cutting one list into two or more lists while preserving the original nodes.
3.7 Merge Two Sorted Lists
Merging combines two sorted singly linked lists into one sorted list by relinking nodes.
3.6 Fast and Slow Pointers
Fast and slow pointers are two references that traverse the same linked structure at different speeds.
3.5 Cycle Detection
A cycle exists in a linked list when some node’s `next` pointer eventually leads back to a previously visited node.
3.4 Reversal
Reversal transforms a linked list so that the direction of all edges is flipped.
3.3 Sentinel Nodes
A sentinel node is an artificial node placed at the boundary of a linked list.
3.2 Doubly Linked Lists
A 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.1 Singly Linked Lists
A singly linked list is a sequence of nodes where each node stores a value and a reference to the next node.
Chapter 3. Linked Lists and Pointers
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.