linked-lists

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.25 Case Studies

This section combines multiple patterns from the chapter into complete, end-to-end linked list algorithms. Each example highlights how invariants, pointer discipline, and structural operations interact. Case Study 1: Merge Sort on Linked Lists Problem Sort a singly linked list in O(n log n) time using O(1) extra space. Approach Use divide-and-conquer: Split the list into two halves Recursively sort each half Merge the sorted halves Implementation sort(head): if head ==...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

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. It combines two data structures: a hash map for O(1) lookup and a doubly linked list for O(1) recency updates. The hash map answers "where is the entry for this key?" The list answers "which entry was used least recently?" Problem Design a cache with these operations: get(key) ->...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.15 Skip Lists

A skip list augments a sorted linked list with multiple levels of forward pointers. Higher levels “skip” over many nodes, enabling fast search, insertion, and deletion. The structure is probabilistic: node heights are assigned randomly, which yields expected logarithmic performance without rotations or strict balancing. Structure Each node stores a value and an array of forward pointers. Node { value next[0..h] // level 0 is the base list } A...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.13 Pointer Aliasing

Pointer aliasing occurs when two or more references point to the same node. In linked list algorithms, aliasing is unavoidable. Multiple variables often refer to the same structure during traversal, insertion, deletion, or merging. Correct algorithms treat aliasing as a controlled property. Incorrect algorithms create unintended sharing, which leads to structural corruption. Problem You manipulate a linked list using multiple pointers. Some of these pointers may refer to the same...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.23 Testing Pointer Code

Pointer code should be tested by checking structure, not only values. A linked list can contain the right values while still having broken links, accidental cycles, stale tails, or shared nodes that should have been detached. Good tests therefore verify both the sequence and the shape of the list. Problem You want to test linked list algorithms such as insertion, deletion, reversal, splitting, merging, and LRU operations. A weak test...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.22 Edge Cases

Edge cases are inputs that sit near the boundary of an algorithm's assumptions. In linked list problems, these cases usually involve empty lists, one-node lists, changes at the head, changes at the tail, repeated values, cycles, shared nodes, or invalid positions. A linked list algorithm is often correct for the middle of the list before it is correct for the boundaries. This section gives a checklist for finding and handling...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.11 Insertion Patterns

Insertion adds nodes into a linked list by creating new links while preserving reachability of all existing nodes. In a singly linked list, insertion is defined relative to a known position, usually a predecessor node. In a doubly linked list, insertion can be defined relative to either neighbor. Problem Given a linked list and a rule for placement, insert a new node or a sequence of nodes while maintaining structural...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.24 Complexity Analysis

Linked list algorithms are dominated by pointer traversal and constant-time link updates. The key to correct analysis is to count how many nodes are visited and how many pointers are changed. Unlike arrays, there is no random access, so position-based operations depend on traversal length. Cost Model Use these basic costs: read next pointer: O(1) write next pointer: O(1) allocate node: O(1) free node: O(1) compare values: O(1) A loop...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.18 Iterators

An iterator is an object or procedure that visits the nodes of a linked list one at a time. It separates traversal from the operation applied to each node. This separation is useful because many list algorithms have the same walking pattern but different processing logic. Problem You need to scan a linked list without exposing every detail of pointer movement to the caller. Typical uses include: print every value...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.17 Memory Ownership

Memory ownership describes which part of a program is responsible for creating, linking, unlinking, and destroying a node. In linked list algorithms, pointer correctness is only one side of the problem. The other side is lifetime correctness: every node that remains linked must be alive, and every node that is removed must still be handled according to the memory model of the language. Problem You have a linked list whose...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.14 Persistent Lists

A persistent list is a list that preserves older versions after an update. Instead of modifying nodes in place, the algorithm creates new nodes for the changed prefix and shares the unchanged suffix. This style is common in functional programming, immutable data structures, undo systems, and versioned state. Problem You want to update a list while keeping the original list available. For example, given: old: 1 -> 2 -> 3...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.16 Intrusive Lists

An intrusive list stores the linkage fields inside the objects being linked. Instead of allocating a separate wrapper node that contains a value, each object contains its own next pointer, or both prev and next pointers for a doubly linked list. This design is common in kernels, memory allocators, schedulers, game engines, and low-level systems where allocation, ownership, and memory layout must be controlled carefully. Problem You want to maintain...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.19 Stack via List

A stack is a last-in, first-out (LIFO) structure. A singly linked list implements a stack naturally by treating the head as the top. All operations occur at the head, which gives constant-time push and pop. Structure Use a singly linked list: Node { value next : Node | null } Stack { head : Node | null } The invariant is: head points to the top of the stack Push...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.20 Queue via List

A queue is a first-in, first-out structure. The first value inserted is the first value removed. A singly linked list implements a queue efficiently when the structure keeps both a head pointer and a tail pointer. The head points to the next node to remove. The tail points to the last node inserted. Queue { head : Node | null tail : Node | null } Structure Each node stores...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.12 Dummy Heads (Dummy Nodes)

A dummy head is a fixed node placed before the real head of a singly linked list. It does not carry user data. It provides a stable predecessor for every real node, including the original head. This removes most boundary cases from insertion and deletion. Problem Algorithms that modify the first node require special handling because the head has no predecessor. This leads to branching logic and error-prone code paths....

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.4 Reversal

Reversal transforms a linked list so that the direction of all edges is flipped. For a list a -> b -> c -> d -> null the result is d -> c -> b -> a -> null The operation is structural. No values change. Only the next pointers are reassigned. Problem Given the head of a singly linked list, reverse the list in place and return the new head....

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.8 Split Patterns

Splitting a linked list means cutting one list into two or more lists while preserving the original nodes. The operation changes links, not values. It appears in merge sort, partitioning, alternating lists, palindrome checks, and algorithms that process the front and back halves separately. Problem Given the head of a singly linked list, divide it into parts according to a rule. Common rules include: split into first half and second...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

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

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

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. The structure is defined inductively: an empty list is nil , and a non-empty list is a node followed by another list. This definition forces all traversal to proceed in one direction, from head to tail. Structure A minimal node definition in pseudocode is: Node { value next...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.7 Merge Two Sorted Lists

Merging combines two sorted singly linked lists into one sorted list by relinking nodes. The operation does not create new nodes. It reuses existing nodes and preserves their order. Problem Given two lists l1 and l2 , both sorted in non-decreasing order, produce a single sorted list. l1: a1 -> a2 -> ... l2: b1 -> b2 -> ... Return a list that contains all nodes from both inputs, ordered....

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

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. Unlike simple two-list merge, these patterns generalize to conditional routing, alternating consumption, or multi-way combination. Problem Given one or more input lists, construct an output list by selecting nodes according to a rule, without allocating new nodes. Typical rules include: merge two sorted lists merge k sorted lists alternate...

Programming › Algorithm Cookbook ›

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

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

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. In such a structure, traversal never reaches null . Detecting this condition requires reasoning about the movement of pointers rather than counting nodes. Problem Given the head of a singly linked list, determine whether the list contains a cycle. If a cycle exists, optionally identify the node where the cycle...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

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. Compared with a singly linked list, it gives bidirectional movement, but every structural update must preserve two links instead of one. Structure A minimal node definition is: Node { value prev : Node | null next : Node | null } The...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.10 Deletion Patterns

Deletion removes one or more nodes from a linked list by changing links around them. The values stored in the nodes are usually irrelevant. What matters is the predecessor of the node being removed and the successor that must remain reachable afterward. In a singly linked list, deletion is harder than insertion because a node does not know its predecessor. For this reason, most deletion algorithms maintain a prev pointer,...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.6 Fast and Slow Pointers

Fast and slow pointers are two references that traverse the same linked structure at different speeds. Usually, the slow pointer moves one step at a time, while the fast pointer moves two steps at a time. This simple difference creates information about the shape of the list: whether a cycle exists, where the middle lies, or how to split the list into two parts. Problem You need to locate structural...

#linked-lists

3.25 Case Studies

3.21 LRU Cache Structure

3.15 Skip Lists

3.13 Pointer Aliasing

3.23 Testing Pointer Code

3.22 Edge Cases

3.11 Insertion Patterns

3.24 Complexity Analysis

3.18 Iterators

3.17 Memory Ownership

3.14 Persistent Lists

3.16 Intrusive Lists

3.19 Stack via List

3.20 Queue via List

3.12 Dummy Heads (Dummy Nodes)

3.4 Reversal

3.8 Split Patterns

3.3 Sentinel Nodes

3.1 Singly Linked Lists

3.7 Merge Two Sorted Lists

3.9 Merge Patterns

Chapter 3. Linked Lists and Pointers

3.5 Cycle Detection

3.2 Doubly Linked Lists

3.10 Deletion Patterns

3.6 Fast and Slow Pointers