Chapter 4

Linked Lists: The Art of Pointers

Chapter 4: Linked Lists — The Art of Pointers

Imagine a line of students queuing up. The array approach: everyone stands on a contiguous strip of ground, sorted by number. To insert someone in the middle, everyone behind them must shift one step back. The linked list approach: each person holds a slip of paper with the location of the next person. Want to insert someone? Just rewrite two slips of paper.

This analogy reveals the most fundamental characteristic of linked lists: logical order is completely decoupled from physical storage location. Nodes can be scattered anywhere in memory, connected only by pointers (references). This grants tremendous flexibility, but at a cost — you can no longer "calculate" where the k-th element is; you must follow pointers from the beginning, one by one.

Level 1 · What You Need to Know

4.1 Singly Linked Lists: The Simplest Chain Structure

4.1.1 Node Definition

The basic building block of a linked list is the node. Each node contains two parts: the stored data and a reference to the next node.

class ListNode:
    """Singly linked list node"""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next  # Points to the next node; None means end of list

This seemingly simple definition embodies an important computer science concept: self-referential data structures. The type definition references its own type, allowing us to describe unbounded structures with finite code.

WHY — Why use a class instead of tuples/dicts? In Python, you could certainly use (val, next_ref) tuples or dicts to simulate a linked list. But classes offer advantages: (1) Attribute access node.next is faster than dictionary lookup node['next'] (in CPython, attribute access goes through __dict__ hash table or __slots__, and IDEs provide autocomplete); (2) You can add __repr__ for debugging; (3) It's the convention in LeetCode/interviews.

4.1.2 Building a Linked List

def build_linked_list(values):
    """Build a linked list from a Python list, return head node"""
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# Example: 1 -> 2 -> 3 -> None
head = build_linked_list([1, 2, 3])

4.1.3 Traversal

def traverse(head):
    """Traverse and print each node"""
    current = head
    while current:
        print(current.val, end=" -> ")
        current = current.next
    print("None")

Traversal has O(n) time complexity and O(1) space complexity. This is the most fundamental pattern in linked list operations — a pointer walking from head to tail.

4.1.4 Insertion Operations

Linked list insertion has three cases: head insertion, tail insertion, and middle insertion.

def insert_at_head(head, val):
    """Insert at the head — O(1)"""
    new_node = ListNode(val)
    new_node.next = head
    return new_node  # New node becomes the new head

def insert_at_tail(head, val):
    """Insert at the tail — O(n)"""
    new_node = ListNode(val)
    if not head:
        return new_node
    current = head
    while current.next:
        current = current.next
    current.next = new_node
    return head

def insert_after(node, val):
    """Insert after a given node — O(1) (assuming you already have a reference)"""
    if not node:
        return
    new_node = ListNode(val)
    new_node.next = node.next
    node.next = new_node

Key insight: Head insertion is O(1), but tail insertion is O(n) — because you must traverse to the end first. This is why many implementations maintain a tail pointer.

4.1.5 Deletion Operations

def delete_node(head, target):
    """Delete the first node with value equal to target"""
    # Special case: delete head node
    if head and head.val == target:
        return head.next
    
    current = head
    while current and current.next:
        if current.next.val == target:
            current.next = current.next.next  # Skip the target node
            return head
        current = current.next
    return head  # Target not found

The core of deletion: find the predecessor of the target node, then make the predecessor's next skip over the target. This means you need to maintain a reference to the predecessor.

4.1.6 Search

def search(head, target):
    """Search for a value in the linked list — O(n)"""
    current = head
    while current:
        if current.val == target:
            return current
        current = current.next
    return None

Time Complexity Summary:

Operation	Time Complexity	Notes
Head insertion	O(1)	Only one pointer modification
Tail insertion	O(n) or O(1)	Depends on whether tail pointer is maintained
Insert after given node	O(1)	Already have reference to position
Delete head	O(1)	Just return head.next
Delete by value	O(n)	Must search first
Search	O(n)	Must traverse linearly
Random access (k-th)	O(n)	Cannot index like arrays

4.2 Doubly Linked Lists: Freedom in Both Directions

The limitation of singly linked lists is that traversal is unidirectional. If you're standing at some node and want to go back to the previous one, you can't — unless you start over from the head. Doubly linked lists solve this by adding a prev pointer to each node.

class DoublyListNode:
    """Doubly linked list node"""
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

4.2.1 Insertion and Deletion in Doubly Linked Lists

def dll_insert_after(node, val):
    """Insert after node in a doubly linked list — O(1)"""
    new_node = DoublyListNode(val)
    new_node.next = node.next
    new_node.prev = node
    if node.next:
        node.next.prev = new_node
    node.next = new_node
    return new_node

def dll_delete(node):
    """Delete a node from a doubly linked list — O(1)
    Precondition: node is not head or tail (or sentinels are used)
    """
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev

The greatest advantage of doubly linked lists: given a reference to any node, you can delete it in O(1). Singly linked lists cannot do this — you must find the predecessor, which requires traversing from the head.

4.2.2 Python collections.deque Under the Hood

WHO — Source: CPython source code, Modules/_collectionsmodule.c.

Python's standard library collections.deque is not implemented as a simple doubly linked list. It's a hybrid of doubly linked list + fixed-size array blocks. Each block is a fixed-size array of 64 elements, and multiple blocks are connected via a doubly linked list.

Block 0          Block 1          Block 2
[a,b,c,...,64] <-> [e,f,g,...,64] <-> [h,i,j,...,64]

WHY — Why not a pure doubly linked list? The problem with pure linked lists is: each element requires its own node object (Python object overhead is ~56 bytes), making memory utilization extremely poor. The blocked strategy lets every 64 elements share one pair of prev/next pointers, dramatically reducing memory overhead while maintaining O(1) insertion/deletion at both ends.

This design is also called an Unrolled Linked List, formally proposed by Shao, Bodik, and Goldstein in 1994 (though the idea of unrolling predates their paper).

4.3 Circular Linked Lists

In a circular linked list, the last node doesn't point to None — it points back to some node in the list (usually the head).

def build_circular(values):
    """Build a circular linked list"""
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    current.next = head  # Tail points back to head
    return head

4.3.1 The Josephus Problem

WHO — Source: Flavius Josephus, a 1st-century Jewish historian, described the original version of this problem in The Jewish War. The modern mathematical formalization was done by W. Ahrens (1918).

Problem statement: n people stand in a circle. Starting from person 1, count to k — that person leaves. Resume counting from the next person until everyone has left. Determine the elimination order.

def josephus(n, k):
    """Josephus problem — circular linked list simulation"""
    # Build circular linked list
    head = ListNode(1)
    current = head
    for i in range(2, n + 1):
        current.next = ListNode(i)
        current = current.next
    current.next = head  # Form the circle
    
    result = []
    prev = current  # prev points to the node before current
    curr = head
    
    while curr.next != curr:  # Until only one person remains
        # Count k-1 times (move k-1 steps)
        for _ in range(k - 1):
            prev = curr
            curr = curr.next
        # Eliminate
        result.append(curr.val)
        prev.next = curr.next  # Remove current node
        curr = curr.next
    
    result.append(curr.val)  # Last person
    return result

# josephus(7, 3) => [3, 6, 2, 7, 5, 1, 4]

Mathematical solution: The Josephus problem has an elegant recurrence J(n, k) = (J(n-1, k) + k) % n that computes the last survivor's index in O(n) time without simulating the entire process.

def josephus_survivor(n, k):
    """Find the last survivor (0-indexed) — O(n) mathematical solution"""
    pos = 0
    for i in range(2, n + 1):
        pos = (pos + k) % i
    return pos  # Convert to 1-indexed: pos + 1

4.4 Linked Lists vs Arrays: A Comprehensive Comparison

Dimension	Array (Python list)	Linked List
Random access	O(1)	O(n)
Head insertion	O(n)	O(1)
Tail insertion	Amortized O(1)	O(n) or O(1)*
Middle insertion	O(n)	O(1)**
Deletion	O(n)	O(1)**
Memory layout	Contiguous	Scattered
Cache friendliness	Excellent	Poor
Extra space	None (or small pre-allocation)	One/two pointers per node
Fixed size?	Dynamic resize (with copy cost)	Naturally dynamic

*With tail pointer. **When you already have a reference to the position.

WHY — Why does cache matter? Modern CPU L1 cache access takes ~1ns, while main memory access takes ~100ns — a 100x difference. Arrays' contiguous memory layout means CPU prefetch can load upcoming data into cache ahead of time; linked list nodes are scattered across the heap, so nearly every node.next dereference causes a cache miss.

WHO — Source: Bjarne Stroustrup (creator of C++) has emphasized this point in numerous talks, most famously in his GoingNative 2012 keynote "Why you should avoid linked lists," where he showed experimental data demonstrating that even for insertion/deletion-heavy workloads, std::vector often outperforms std::list due to cache effects.

4.5 Common Operations

4.5.1 Reversing a Linked List

This is the most classic linked list operation and one of the most frequent interview questions (LeetCode #206).

def reverse_list(head):
    """Iterative reversal — O(n) time, O(1) space"""
    prev = None
    curr = head
    while curr:
        next_temp = curr.next  # Save the next node
        curr.next = prev       # Reverse the pointer
        prev = curr            # Advance prev
        curr = next_temp       # Advance curr
    return prev  # prev is now the new head

Visual walkthrough:

Start:  None <- 1    2 -> 3 -> None
               prev  curr

Step 1: None <- 1 <- 2    3 -> None
                     prev  curr

Step 2: None <- 1 <- 2 <- 3
                          prev  curr=None

Recursive version:

def reverse_list_recursive(head):
    """Recursive reversal — O(n) time, O(n) space (stack)"""
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head  # Make successor point back to me
    head.next = None       # Break the original forward link
    return new_head

4.5.2 Merging Two Sorted Lists (LeetCode #21)

def merge_two_sorted(l1, l2):
    """Merge two sorted lists — O(n+m) time, O(1) space"""
    dummy = ListNode(0)  # Sentinel node
    tail = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    
    tail.next = l1 if l1 else l2  # Append the remaining portion
    return dummy.next

4.5.3 Finding the Middle Node (Two Pointers)

def find_middle(head):
    """Fast/slow pointers to find middle — O(n) time, O(1) space
    For even length, returns the left-of-center middle node
    """
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    return slow

WHY — Why two pointers? If you traverse once to compute length n, then walk n/2 steps to find the middle, that's 1.5n steps. The two-pointer approach needs only n steps — when the fast pointer finishes, the slow pointer is exactly at the middle. Although both are O(n), the constant factor is smaller. More importantly, the two-pointer technique doesn't require knowing the list length, making it applicable to streaming data of unknown length.

4.5.4 Remove Nth Node From End (LeetCode #19)

def remove_nth_from_end(head, n):
    """Remove the nth node from the end — single pass"""
    dummy = ListNode(0)
    dummy.next = head
    fast = slow = dummy
    
    # fast advances n+1 steps ahead
    for _ in range(n + 1):
        fast = fast.next
    
    # Move both until fast reaches the end
    while fast:
        fast = fast.next
        slow = slow.next
    
    # slow is now the predecessor of the target
    slow.next = slow.next.next
    return dummy.next

Trick: Advance the fast pointer by n+1 steps (not n), so when fast reaches None, slow is exactly one position before the target — convenient for deletion.

4.6 Common Mistakes

Mistake 1: Forgetting to Handle Empty Lists

# Wrong! If head is None, head.val crashes
def bad_search(head, target):
    if head.val == target:  # NoneType has no attribute 'val'
        return head
    ...

# Correct: check if head is None first
def good_search(head, target):
    if not head:
        return None
    if head.val == target:
        return head
    ...

Mistake 2: Losing Pointer References

# Wrong! This breaks the chain
def bad_insert_after(node, val):
    new_node = ListNode(val)
    node.next = new_node      # The rest of the list after node is lost!
    new_node.next = node.next  # node.next is already new_node here

# Correct: save first, or set new node's next before modifying node
def good_insert_after(node, val):
    new_node = ListNode(val)
    new_node.next = node.next  # Connect to the rest first
    node.next = new_node       # Then modify the predecessor

Mistake 3: Modifying the List During Traversal

# Dangerous! Deleting nodes during traversal may skip elements or loop forever
current = head
while current:
    if should_delete(current):
        # How to correctly delete here? You've lost the prev reference!
        pass
    current = current.next

The correct approach is to maintain a prev pointer, or use a sentinel node.

Level 2 · Deeper Understanding

4.7 Cycle Detection with Fast/Slow Pointers (Floyd's Algorithm)

WHO — Source: Robert W. Floyd, informally proposed in 1967 (he never published a formal paper on it, but Donald Knuth attributes the algorithm to Floyd in The Art of Computer Programming). Also called the "tortoise and hare" algorithm.

Problem: Given a linked list, determine if it contains a cycle.

Core idea: Set up two pointers — slow moves one step at a time, fast moves two steps. If there's a cycle, the fast pointer will eventually catch the slow one (like runners on a track — the faster one will lap the slower one). If there's no cycle, fast will reach None first.

def has_cycle(head):
    """Floyd's cycle detection — O(n) time, O(1) space (LeetCode #141)"""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

WHY — Why are they guaranteed to meet? Let the cycle length be C. When the slow pointer enters the cycle, the fast pointer is already somewhere inside. At each step, the fast pointer gains one step on the slow pointer, reducing their gap by 1. In at most C steps, the gap shrinks from some value to 0, meaning they meet.

More formal proof: Suppose slow takes k steps to reach the cycle entrance; at that point, fast has taken 2k steps. Fast's position in the cycle is (2k - steps_before_cycle) % C. Once both are in the cycle, their gap decreases by 1 per step, so they meet within at most C additional steps. Total time complexity: O(n).

For deeper discussion of cycle detection and its variants, see Chapter 23: Two Pointers and Sliding Window.

4.8 Finding the Cycle Entrance: Mathematical Derivation

Problem: Given a linked list with a cycle, find the node where the cycle begins (LeetCode #142).

def detect_cycle_entry(head):
    """Find the cycle entrance node"""
    slow = fast = head
    
    # Phase 1: Detect the cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle
    
    # Phase 2: Find the entrance
    # Reset one pointer to head, then advance both at the same speed
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

Mathematical derivation:

Let the distance from head to cycle entrance be a, from entrance to meeting point be b, and from meeting point back to entrance be c. Cycle length C = b + c.

At the meeting point, slow has traveled a + b steps
Fast has traveled a + b + nC steps (n is the number of extra laps, n >= 1)
Fast travels at twice slow's speed: 2(a + b) = a + b + nC
Simplifying: a + b = nC, i.e., a = nC - b = (n-1)C + c

This means: walking a steps from the head reaches the entrance, and walking (n-1) full laps plus c steps from the meeting point also reaches the entrance. So in Phase 2, both pointers advance at the same speed and meet at the entrance.

4.9 Skip Lists: An Introduction

WHO — Source: William Pugh, 1990 paper "Skip Lists: A Probabilistic Alternative to Balanced Trees," published in Communications of the ACM.

A skip list builds upon a sorted linked list by adding multiple levels of "express lanes" to achieve O(log n) search.

Level 3: head ---------> 6 --------------------------> None
Level 2: head ---------> 6 ---------> 25 -----------> None
Level 1: head ---> 3 --> 6 ---> 9 --> 25 ---> 30 ---> None
Level 0: head -> 1 -> 3 -> 6 -> 7 -> 9 -> 12 -> 25 -> 30 -> 42 -> None

Core idea: Each node randomly decides how many levels it appears in. Upon insertion, a coin flip (with probability p, typically p=0.5 or p=0.25) determines whether the node is "promoted" to the next level. Search starts from the highest level, using express lanes to skip over many nodes.

import random

class SkipNode:
    def __init__(self, val, level):
        self.val = val
        self.forward = [None] * (level + 1)  # One next pointer per level

class SkipList:
    MAX_LEVEL = 16
    P = 0.5  # Promotion probability
    
    def __init__(self):
        self.header = SkipNode(-float('inf'), self.MAX_LEVEL)
        self.level = 0  # Current highest level
    
    def random_level(self):
        """Randomly determine the level for a new node"""
        lvl = 0
        while random.random() < self.P and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl
    
    def search(self, target):
        """O(log n) average time search"""
        current = self.header
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].val < target:
                current = current.forward[i]
        current = current.forward[0]
        return current and current.val == target
    
    def insert(self, val):
        """O(log n) average time insertion"""
        update = [None] * (self.MAX_LEVEL + 1)
        current = self.header
        
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].val < val:
                current = current.forward[i]
            update[i] = current
        
        new_level = self.random_level()
        if new_level > self.level:
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.header
            self.level = new_level
        
        new_node = SkipNode(val, new_level)
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

WHY — Why did Redis choose skip lists over red-black trees?

WHO — Source: Salvatore Sanfilippo (antirez), creator of Redis, explained this decision in GitHub issues and multiple replies in 2014.

antirez's reasoning (paraphrased):

Simpler implementation: Skip list code is roughly half the size of red-black tree code — easier to understand, debug, and maintain.
Naturally efficient range queries: The bottom level of a skip list is a sorted linked list; range queries just find the start and traverse sequentially. Range queries on red-black trees require in-order traversal, which is more complex to implement.
Concurrency-friendly: Skip lists can more easily be made lock-free (though Redis is single-threaded, this is a general advantage).
Tunable memory locality: By adjusting p, you can trade between time and space. Redis uses p=0.25, resulting in an average of only 1.33 pointers per node.

Expected complexity of skip lists:

Operation	Average	Worst Case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Space	O(n)	O(n log n)

The worst case (all nodes at the highest level) has exponentially small probability and can be ignored in practice.

4.10 Linked Lists in LRU Cache

WHO — Source: The LRU (Least Recently Used) cache eviction strategy traces back to 1960s research on operating system page replacement algorithms. As an interview problem, it's LeetCode #146.

LRU Cache core requirements:

get(key): O(1) retrieval, marking the item as most recently used
put(key, value): O(1) insertion; evict the least recently used item when at capacity

Solution: Hash Map + Doubly Linked List

class LRUNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> LRUNode
        # Sentinel nodes: eliminate boundary conditions
        self.head = LRUNode()  # dummy head
        self.tail = LRUNode()  # dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _remove(self, node):
        """Remove a node from the doubly linked list — O(1)"""
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _add_to_front(self, node):
        """Insert node right after head (marks it as most recently used) — O(1)"""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
    
    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add_to_front(node)
            return node.val
        return -1
    
    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add_to_front(node)
        else:
            if len(self.cache) >= self.capacity:
                # Evict the least recently used (node before tail)
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
            node = LRUNode(key, value)
            self.cache[key] = node
            self._add_to_front(node)

WHY — Why do we need a doubly linked list? The hash map provides O(1) lookup but cannot maintain usage order. The linked list maintains order but has O(n) search. Combined: the hash map stores key-to-node mappings for O(1) access, and the doubly linked list maintains usage order with O(1) move/delete for any node.

WHY — Why doubly linked instead of singly linked? Because _remove(node) needs to modify both node's predecessor and successor. With a singly linked list, you'd need to traverse from the head to find the predecessor, making deletion O(n).

For detailed discussion of hash tables, see Chapter 8. For more LRU Cache variants and industrial implementations, see Chapter 38.

4.11 Recursion vs Iteration for Linked Lists: Trade-offs

The recursive structure of linked lists — a node plus "the rest of the list" — makes them naturally suited for recursive processing. But recursion isn't always the best choice.

# Recursive traversal
def recursive_traverse(head):
    if not head:
        return
    print(head.val)
    recursive_traverse(head.next)

# Recursive length
def recursive_length(head):
    if not head:
        return 0
    return 1 + recursive_length(head.next)

Comparison:

Dimension	Recursion	Iteration
Code conciseness	Usually more concise	May be longer
Space complexity	O(n) stack space	O(1)
Stack overflow risk	Crashes if list > recursion limit	No such risk
Tail-call optimization	Python does NOT support it	N/A
Debugging difficulty	Harder (deep call stacks)	Easier

WHY — Python doesn't support tail-call optimization: Guido van Rossum explicitly stated in his 2009 blog post "Neopythonic: Tail Recursion Elimination" that Python will not implement TCO, because it would destroy the readability of tracebacks — Python's philosophy values clear error reporting over performance optimization.

Practical advice: When working with linked lists in Python, almost always prefer iteration. Recursive solutions are better for teaching and proving correctness. CPython's default recursion limit is 1000 (modifiable via sys.setrecursionlimit()), meaning linked lists with more than 1000 nodes will crash the recursive version.

Level 3 · Going Deeper

4.12 The History of Linked Lists

WHO — Source: Allen Newell, Cliff Shaw, Herbert A. Simon, 1955-1956, at RAND Corporation and Carnegie Mellon University, developing IPL (Information Processing Language).

The linked list was not invented to solve a specific programming problem — it was invented to build artificial intelligence. In 1955, Newell, Shaw, and Simon were developing the Logic Theorist — the first AI program in history, designed to automatically prove mathematical theorems. They needed a flexible data structure to represent and manipulate symbolic expressions (logical formulas), but the computers of the time only had fixed-size arrays.

Their solution was the IPL language, whose core data structure was the linked list. Each "cell" in IPL contained a symbol value and an address pointing to the next cell. This design directly influenced John McCarthy's creation of LISP in 1958 — LISP's name stands for "LISt Processing," and the linked list is the language's foundational data structure.

Historical influence chain:

IPL (1955-56, Newell/Shaw/Simon)
    |
LISP (1958, McCarthy) — the cons cell IS a linked list node
    |
All modern functional languages' list types
    (Haskell, ML, Erlang, Clojure...)

Fun fact: Newell and Simon won the 1975 Turing Award for their pioneering work in AI. The linked list was merely a byproduct of their work, yet its impact on computer science has been more far-reaching than the Logic Theorist itself.

4.13 XOR Linked Lists: Saving Pointer Space with XOR

WHO — Source: This technique was widely known in the systems programming community in the 1990s. The earliest formal description is difficult to trace, but Knuth mentions a similar idea in exercises in The Art of Computer Programming Vol. 1 (1968).

A regular doubly linked list stores two pointers per node (prev and next). An XOR linked list stores only one value: prev_addr XOR next_addr.

Principle:

Let nodes A, B, C have memory addresses addr(A), addr(B), addr(C)

Regular doubly linked list:
  A.prev = None, A.next = addr(B)
  B.prev = addr(A), B.next = addr(C)
  C.prev = addr(B), C.next = None

XOR linked list:
  A.link = 0 XOR addr(B) = addr(B)
  B.link = addr(A) XOR addr(C)
  C.link = addr(B) XOR 0 = addr(B)

Traversal method: If you're at node B and know you came from A (i.e., you know addr(A)), then:

next_addr = B.link XOR addr(A)
          = (addr(A) XOR addr(C)) XOR addr(A)
          = addr(C)  (because X XOR X = 0)

Python pseudocode (Python cannot directly manipulate memory addresses; here we simulate using id() and ctypes):

import ctypes

class XORNode:
    def __init__(self, val):
        self.val = val
        self.npx = 0  # XOR of prev and next addresses

def xor(a, b):
    """XOR two node addresses (using id)"""
    return a ^ b

def insert_at_head(head, val):
    new_node = XORNode(val)
    new_node.npx = id(head) if head else 0
    if head:
        # head.npx = 0 XOR old_next_addr
        # New head.npx = id(new_node) XOR old_next_addr
        head.npx = xor(id(new_node), head.npx)
    return new_node

def traverse_xor(head):
    """Traverse an XOR linked list"""
    prev_addr = 0
    current = head
    while current:
        print(current.val, end=" -> ")
        next_addr = xor(prev_addr, current.npx)
        prev_addr = id(current)
        # Need to recover the object from address (in C, just dereference the pointer)
        current = ctypes.cast(next_addr, ctypes.py_object).value if next_addr else None
    print("None")

WHY — Why is it rarely used in practice?

Terrible readability: Code is extremely hard to understand and maintain.
Debugging difficulty: You can't directly inspect predecessors/successors in a debugger.
Conflicts with garbage collectors: GC needs to traverse all references to determine reachability. XOR-encoded "pointers" are invisible to the GC, and nodes may be incorrectly reclaimed. This makes XOR linked lists completely unusable in languages with GC (Java/Python/Go).
Modern memory is abundant: When each pointer was 4 bytes, saving one pointer was meaningful. Now even with 8-byte pointers, memory is rarely the bottleneck.

Applicable scenarios: Extreme embedded systems (memory measured in KB), using C/C++ with manual memory management.

4.14 Free Lists in Memory Allocators

WHO — Source: Free lists are among the oldest dynamic memory management techniques, dating back to 1960s ALGOL compilers. Doug Lea's dlmalloc (1987) and the subsequent ptmalloc2 (glibc's default allocator) extensively use free list variants.

When you call malloc() to allocate memory, how does the allocator know which memory blocks are free? The answer is the free list.

Core idea: String all free memory blocks together in a linked list. On allocation, take a block from the head; on deallocation, insert the block back at the head.

Free List (chain of free blocks):
[16B block] -> [32B block] -> [16B block] -> [64B block] -> None

malloc(16):
  Take the first 16B block, return to user
  Free List: [32B block] -> [16B block] -> [64B block] -> None

free(ptr):
  Insert ptr's block back at the head
  Free List: [16B block] -> [32B block] -> [16B block] -> [64B block] -> None

The elegant part: The linked list pointers for free blocks are stored within the free blocks themselves! Since no one is using the free block, its first few bytes can hold the next pointer. This means maintaining the free list requires zero additional memory overhead.

// Simplified free list implementation (C pseudocode)
typedef struct free_block {
    struct free_block *next;  // Stored inside the free block itself
} free_block_t;

free_block_t *free_list = NULL;

void *my_malloc(size_t size) {
    // Find an appropriately sized block in free_list
    free_block_t *block = free_list;
    free_list = block->next;
    return (void *)block;
}

void my_free(void *ptr) {
    // Insert the freed block at the head of free_list
    free_block_t *block = (free_block_t *)ptr;
    block->next = free_list;
    free_list = block;
}

Modern allocator optimizations:

Segregated Free Lists: Classified by size — 16-byte blocks have one list, 32-byte blocks have another, and so on. Allocation goes directly to the corresponding size class, avoiding fragmentation.
glibc's fastbin: Uses LIFO singly linked lists for small blocks (<=160 bytes); both allocation and deallocation are O(1).
jemalloc / tcmalloc: Use thread-local free lists to avoid lock contention.

4.15 Linux Kernel's list_head: Intrusive Linked Lists

WHO — Source: Linux kernel, include/linux/list.h. This design was introduced starting with Linux 2.1 (circa 1996), contributed by multiple kernel developers.

Traditional linked lists (like our implementations above) are "non-intrusive": the list node contains the data. The Linux kernel uses "intrusive" linked lists: the data structure embeds the list node within itself.

// Linux kernel's list_head definition
struct list_head {
    struct list_head *next, *prev;
};

// Usage: embed list_head in your data structure
struct task_struct {
    pid_t pid;
    char comm[16];
    struct list_head tasks;     // Process list
    struct list_head children;  // Child process list
    // ... other fields
};

Key technique: The container_of macro. Given the address of a list_head, how do you find the enclosing structure?

// container_of macro: derive structure pointer from member pointer
#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

// Traverse the process list
struct task_struct *task;
struct list_head *pos;
list_for_each(pos, &init_task.tasks) {
    task = container_of(pos, struct task_struct, tasks);
    printk("PID: %d, Name: %s\n", task->pid, task->comm);
}

WHY — Why does the kernel use intrusive linked lists?

Zero extra memory allocation: No need to kmalloc a separate list node for each entry. The list head is embedded in the existing structure, allocated together with it.
One object can be in multiple lists simultaneously: For example, task_struct is simultaneously in the process list, run queue, and wait queue — just embed multiple list_head fields.
Type-agnostic: list_head operations (insert, delete, traverse) don't care what the enclosing structure type is — highly reusable code.
Cache-friendly: List nodes and data are in the same memory block, reducing pointer chasing and cache misses.

Similar idea in Python:

class IntrusiveNode:
    """Intrusive linked list node mixin"""
    def __init__(self):
        self.list_prev = None
        self.list_next = None

class Process(IntrusiveNode):
    """Process object that IS a list node"""
    def __init__(self, pid, name):
        super().__init__()
        self.pid = pid
        self.name = name

class IntrusiveList:
    """Intrusive doubly linked list"""
    def __init__(self):
        self.head = IntrusiveNode()
        self.head.list_prev = self.head
        self.head.list_next = self.head  # Empty list points to itself
    
    def insert(self, node):
        """Insert at head"""
        node.list_next = self.head.list_next
        node.list_prev = self.head
        self.head.list_next.list_prev = node
        self.head.list_next = node
    
    def remove(self, node):
        """Remove a specific node"""
        node.list_prev.list_next = node.list_next
        node.list_next.list_prev = node.list_prev

Level 4 · Engineering Practice

4.16 Why Linked Lists Are Rarely Used in Python

In real-world Python projects, you almost never need to implement your own linked list. Here's why:

1. Python's list is already good enough

Python's list is a dynamic array under the hood (C-implemented, a PyObject ** pointer array). Although head insertion is O(n):

CPython's list.insert(0, x) is implemented with memmove, which is very fast on modern CPUs (contiguous memory, prefetch-friendly)
For fewer than ~100,000 elements, O(n) list.insert(0, x) can be faster than a linked list's O(1) because every node.next in a linked list is a cache miss

2. collections.deque covers most scenarios

from collections import deque

d = deque()
d.appendleft(1)  # O(1) head insertion
d.append(2)      # O(1) tail insertion
d.popleft()      # O(1) head deletion
d.pop()          # O(1) tail deletion

deque has O(1) operations at both ends, sufficient to replace most linked list use cases.

3. Python object overhead is massive

Every Python object takes at least 56 bytes (sys.getsizeof(object()) = 56). A ListNode object:

import sys
node = ListNode(42)
print(sys.getsizeof(node))  # 48 (base object size)
# Plus __dict__: additional 104 bytes
# Total: ~152 bytes to store a single int (which itself only needs 28 bytes)

By comparison, storing an int reference in a list costs only 8 bytes (one pointer). Linked lists have abysmal space efficiency.

4. When are linked lists still useful?

LRU Cache and similar scenarios requiring O(1) deletion of arbitrary elements (paired with a hash map)
Scenarios requiring frequent insertion/deletion during iteration (though in Python you typically work around this differently)
Teaching and interviews (mental training for pointer manipulation)
Low-level systems programming (OS, embedded) — but that's usually not in Python

4.17 High-Frequency Interview Problems

4.17.1 Palindrome Linked List (LeetCode #234)

Approach: Find middle -> Reverse second half -> Compare one by one -> (Optional) Restore the list

def is_palindrome(head):
    """O(n) time, O(1) space palindrome check"""
    if not head or not head.next:
        return True
    
    # 1. Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # 2. Reverse second half
    second_half = reverse_list(slow.next)
    
    # 3. Compare
    p1, p2 = head, second_half
    result = True
    while p2:
        if p1.val != p2.val:
            result = False
            break
        p1 = p1.next
        p2 = p2.next
    
    # 4. Restore the list (good practice)
    slow.next = reverse_list(second_half)
    
    return result

4.17.2 Intersection of Two Linked Lists (LeetCode #160)

Approach: Two pointers start at the heads of both lists. When one reaches the end, redirect it to the other list's head. If there's an intersection, they'll meet at the intersection node.

def get_intersection_node(headA, headB):
    """O(n+m) time, O(1) space"""
    if not headA or not headB:
        return None
    
    pA, pB = headA, headB
    
    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    
    return pA  # Either the intersection or None (both reach end simultaneously)

WHY — Why does this work? Let list A have length a, list B have length b, and the common portion have length c. Pointer A's path: a + (b - c); pointer B's path: b + (a - c). Both are equal: a + b - c = b + a - c. So they are guaranteed to arrive at the intersection simultaneously (or both reach None simultaneously).

4.17.3 Sort List (LeetCode #148 — Merge Sort)

WHY — Why merge sort for linked lists? Quicksort requires random access (partition operations) and doesn't suit linked lists. Merge sort only needs sequential access and merge operations — a perfect fit for linked lists. Moreover, linked list merge doesn't require extra O(n) space (unlike array merge which needs a temporary array).

def sort_list(head):
    """Linked list merge sort — O(n log n) time, O(log n) space (recursion stack)"""
    if not head or not head.next:
        return head
    
    # Find middle and split
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    mid = slow.next
    slow.next = None  # Split into two halves
    
    # Recursively sort both halves
    left = sort_list(head)
    right = sort_list(mid)
    
    # Merge
    return merge_two_sorted(left, right)

Advanced: Bottom-up iterative merge sort can achieve O(1) space (no recursion stack), but code complexity increases significantly.

4.17.4 Reverse Nodes in k-Group (LeetCode #25)

This is a "Hard" level linked list problem that comprehensively tests pointer manipulation skills.

def reverse_k_group(head, k):
    """Reverse every k nodes as a group"""
    # Check if there are k nodes remaining
    count = 0
    node = head
    while node and count < k:
        node = node.next
        count += 1
    
    if count < k:
        return head  # Fewer than k nodes, don't reverse
    
    # Reverse the first k nodes
    prev = None
    curr = head
    for _ in range(k):
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    
    # head is now the last node of the reversed segment
    # curr is the start of the next group
    head.next = reverse_k_group(curr, k)  # Recursively handle the rest
    
    return prev  # prev is the new head of the reversed segment

Iterative version (preferred in interviews since it won't stack overflow):

def reverse_k_group_iterative(head, k):
    """Iterative k-group reversal"""
    dummy = ListNode(0)
    dummy.next = head
    group_prev = dummy
    
    while True:
        # Check if there are k nodes remaining
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if not kth:
                return dummy.next
        
        group_next = kth.next
        
        # Reverse nodes between group_prev.next and kth
        prev, curr = kth.next, group_prev.next
        for _ in range(k):
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        
        # Update connections
        tmp = group_prev.next
        group_prev.next = kth
        group_prev = tmp

# Test: reverse_k_group_iterative(build_linked_list([1,2,3,4,5]), 2)
# Result: 2 -> 1 -> 4 -> 3 -> 5

4.18 The Sentinel Node (Dummy Head) Technique

The sentinel node (also called a dummy node) is one of the most practical techniques in linked list programming.

WHY — Why do we need sentinels? The most annoying part of linked list operations is boundary conditions: the head node has no predecessor, the tail node has no successor. Inserting/deleting the head node requires special handling (because you need to update the head reference). A sentinel node unifies all operations by placing a fake node before the real head.

def remove_elements(head, val):
    """Remove all nodes with value val (LeetCode #203)
    Comparison: without sentinel vs with sentinel
    """
    # Method 1: Without sentinel — special handling for head
    while head and head.val == val:
        head = head.next
    current = head
    while current and current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
    return head
    
    # Method 2: With sentinel — uniform handling
    dummy = ListNode(0)
    dummy.next = head
    current = dummy
    while current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
    return dummy.next

Benefits of using a sentinel:

No need to separately handle the "delete head node" case
Uniform code logic, less error-prone
Return dummy.next at the end — it's naturally the correct new head (whether the original head survived or was deleted)

Rule of thumb: If your linked list operation might modify the head node, use a sentinel. This includes:

Deletion operations (head might be deleted)
Merge/sort operations (the new head is uncertain)
Insertion operations (might insert at the head)

4.19 When to Use Linked Lists and When Not To

Scenarios where linked lists (or their variants) should be used:

Frequent insertion/deletion at known positions: For example, text editor line buffers (though modern editors often use ropes or piece tables).
O(1) concatenation of two sequences: Merging two linked lists requires changing just one pointer. Array concatenation is O(n).
Implementing specialized data structures: LRU Cache, LFU Cache, and Fibonacci Heap all use linked lists internally.
Severe memory fragmentation preventing large contiguous allocations: Common in embedded systems.
Extremely large elements expensive to move: But in Python/Java where objects are references, "moving" just moves a pointer — this reason doesn't apply.

Scenarios where linked lists should NOT be used:

Random access needed: Linked list get(i) is O(n).
Small data sets (fewer than a few thousand elements): Array cache friendliness will dominate linked list's theoretical advantages.
Binary search needed: Cannot efficiently binary search on a linked list (unless using a skip list).
High-level languages with GC (Python/Java): Object overhead makes linked list space efficiency abysmal.
Parallel/vectorized computation: Modern CPU SIMD instructions require contiguous memory.

Decision tree summary:

Need random access?
  -> Yes: Use array
  -> No:
    Need operations at both ends?
      -> Yes: Use deque
      -> No:
        Need O(1) deletion of arbitrary known nodes?
          -> Yes: Use linked list + hash map
          -> No:
            Large dataset with frequent middle insertions?
              -> Yes: Consider linked list or skip list
              -> No: Use array

Chapter Summary

Linked lists are the foundation for understanding pointers/references and dynamic data structures. Although linked lists are rarely used directly in modern high-level languages, their ideas are everywhere:

Operating system process scheduling queues (Linux list_head)
Memory allocator free block management (free lists)
Databases and cache systems (LRU, skip lists)
Compiler symbol table implementations
Network protocol stack packet queues

Mastering linked lists is not about memorizing pointer manipulation code templates — it's about understanding: when logical order is decoupled from physical location, what freedom do you gain, and what cost do you pay?

In the next chapter, we'll study stacks and queues — abstractions obtained by restricting the "access patterns" of linked lists and arrays. This "constraint as power" design philosophy is a recurring theme in computer science.

Rate this chapter

4.5 / 5 (83 ratings)