Linked Lists — Singly, Doubly, When They Win

Review boundary and corrected contracts

Linked-list operations assume acyclic disjoint lists except explicit cycle tests and require valid removal positions. O(1) splicing needs the relevant node/predecessor, not arbitrary positional lookup. Reversal tests must preserve identity. Cache and allocation costs depend on the implementation; exact LRU is one application of node handles, not a claim about every production cache.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own linked lists to the point that reverse-in-place, cycle detection, and merge-two-sorted feel like piano scales — and know when NOT to use one in production.

Why this session exists

Linked lists make pointer discipline concrete: reversal must preserve the unvisited tail, and cycle detection must compare node identity rather than values. In application Python, start with list or deque unless a measured workload needs explicit node handles. Exact LRU designs and intrusive kernel lists illustrate useful constant-time rewiring; their existence does not mean every cache or scheduler uses the same representation.

You will be able to

• Draw a singly-linked list and mutate it (insert / delete / reverse) at the whiteboard.

• Write Floyd's cycle-detection algorithm and explain why the pointers meet.

• Reverse a singly linked list in place with a 4-line loop.

• Explain the three real production wins for linked lists over arrays.

• Explain CPython deque's linked-block representation and the textbook hashmap-plus-list exact LRU design, without generalizing them to every implementation.

Prerequisites

• S023 · Arrays & Strings — the baseline we're comparing against.
• S013 · Classes & Objects — nodes as classes.

Pre-read · skim before the session (25 min total)

Further reading: Python collections.deque reference

Further reading: Redis list data type

Further reading: Linked-list overview

(a) Intuition · 5 min

A treasure hunt, not a row of shelves

Real: You start at the first clue. The clue says ‘next clue is under the oak tree’. You walk there and read the next clue: ‘next is at the fountain’. Continue until a clue says ‘END’. You cannot jump to clue #7 without visiting 1–6 in order. But adding a new clue between #3 and #4 is trivial — you just rewrite two clues to reroute through the new one. That's the deal linked lists make.

 
    Each node holds a value and a pointer to the next node. To get to index i you walk from the head, one node at a time — O(i). To insert or delete when you already have the node's predecessor, you rewrite two pointers — O(1).
    Arrays trade this: O(1) index access but O(n) middle inserts. Every ‘linked list vs array’ decision comes down to which of these operations dominates your workload.
  

The trade-off in one line each

Compare the operations you actually perform

• Index access — array O(1), linked list O(n). Arrays provide the better asymptotic bound for arbitrary indexed access.

• Middle insertion after a known node is O(1); singly linked deletion needs the predecessor, while doubly linked deletion can use the node itself. An array usually shifts O(n) entries.

• Middle insert WHEN YOU MUST FIND THE POSITION — both O(n). Array is usually faster in practice due to cache locality.

• Memory overhead depends on representation. A Python list stores references plus spare capacity; separately allocated Python nodes add object metadata and link fields. Singly and doubly linked nodes differ, and the payload objects count too. Measure the actual layout rather than applying a fixed ratio.

Measure the crossover rather than memorize one

Array insertion moves references in bulk; list traversal follows dependent pointers. Either can dominate depending on whether the node is already known, payload layout, language overhead and allocation. There is no universal 10,000-item crossover. Benchmark the same operation and data representation before choosing.

Timeline — the rise and fall of the linked list

The history is not a simple rise-and-fall story. John McCarthy's April 1960 LISP paper describes a representation in which a word points to the next term and the last carries NIL, motivated by symbolic expressions whose sizes are not known in advance. Linked structures remain useful: the Linux kernel list documentation explains embedded circular doubly linked lists while explicitly warning about locality. CPython 3.14.0's deque combines links with fixed-size blocks. These are different design responses, not evidence for a universal year or container size at which arrays replaced lists.

(b) Following and rewiring node links · 15 min

Singly vs doubly linked

Suppose you already hold a reference to B and want to unlink it. In the singly linked chain, B cannot tell you where A is; in the doubly linked chain, the backward link supplies that missing reference. Read the arrows as stored links, not as adjacent locations in memory.

The search for a predecessor is the expensive part of singly linked deletion, not the final pointer update. If you already have that predecessor, the search disappears. The operations below make that distinction concrete; during reversal, saving the successor before changing a link is what keeps the rest of the chain reachable.

The three linked-list surgeries you must own

Insert after node p

Desc: new.next = p.next; p.next = new. Two writes, done. Doubly-linked adds the reverse pointers.

Delete node p (singly, given predecessor q)

Desc: q.next = p.next; p.next = None. For an interior doubly linked node: p.prev.next = p.next; p.next.prev = p.prev. At an endpoint update head/tail or use sentinels; clear detached links if the ownership policy requires it.

Reverse in place

Desc: Three pointers — prev, curr, next_. Loop: save next_ = curr.next; flip curr.next = prev; slide prev = curr; curr = next_. Ends with head = prev.

Floyd's tortoise and hare — cycle detection in one picture

Rewiring also makes it possible to point back into an earlier part of the chain, so a traversal may never reach the end. Here F's next link returns to the existing node C: the cycle is C → D → E → F → C. Repeating a displayed value on a new node would not create a cycle. Track node identity as the two walkers move at different speeds.

Two pointers start at head. Tortoise moves 1 node per step, hare moves 2. If there's a cycle, the hare eventually laps the tortoise — they meet inside the loop. If there's no cycle, the hare hits None. This is one of the most elegant algorithms in CS, and it uses O(1) extra memory.

When linked lists actually win

Cycle detection teaches safe traversal, but it does not make traversal cheap. The production advantage comes from avoiding the walk: for example, an LRU cache's hashmap supplies a node reference, and a doubly linked list lets the cache move that node without searching for its predecessor.

Name: LRU cache

Tagline: collections.OrderedDict, functools.lru_cache

• Move-to-front on access is O(1) with doubly linked

• Array move-to-front is O(n)

• This is a standard exact-LRU design, not a universal eviction implementation; Redis documents a sampled approximation

Name: Intrusive kernel lists

Tagline: Linux list_head

• A containing object embeds link fields instead of allocating a separate wrapper node

• Known entries can be unlinked with constant pointer work, subject to locking and lifetime rules

• Linux also uses other structures; scheduler run queues are not universally linked lists, and an array of references would move references rather than whole process objects

Name: Undo/redo history

Tagline: Text editors, IDEs

• Cheap append + cheap discard from either end

• No random access needed

• A doubly linked history is one option; two stacks or deques can also support undo/redo

Name: Everything else

Tagline: Just use list / deque / array

• Cache locality beats pointer chasing

• Fewer allocations = faster + smaller

• Simpler to reason about

A practical Python alternative

For a double-ended queue, use collections.deque. CPython 3.14.0 links blocks of 64 element references, amortizing link/allocation overhead across each block. This is a versioned implementation detail, not the abstract definition of a deque; indexed access in the middle is still O(n).

Myth: "Linked lists beat arrays for insertion and deletion, because you just repoint two pointers instead of shifting elements."

Pointer chasing introduces dependent loads and often has worse locality than contiguous traversal. Modern hardware can prefetch some patterns, and relative performance needs measurement.

Why: Constant-time rewiring assumes the needed node handles are already available. Searching for them is O(n). Hardware adds another distinction: pointer-following creates dependent loads, while contiguous references can improve locality. Nodes are not guaranteed to miss cache at every step, and Python execution overhead can dominate either layout.

Test: Time a traversal of the same values, contiguous vs chained:import time N = 2_000_000 arr = list(range(N))

class Node: __slots__ = ('v', 'next') def __init__(self, v): self.v = v; self.next = None

head = cur = Node(0) for i in range(1, N): cur.next = Node(i); cur = cur.next

t = time.perf_counter(); s = sum(arr); a = time.perf_counter() - t t = time.perf_counter() s = 0; n = head while n: s += n.v; n = n.next b = time.perf_counter() - t print(a, b, b / a) # local timing only: built-in sum versus a Python pointer loop

This timing compares entire implementations, including built-in versus Python-loop overhead; it does not isolate hardware cache latency. Use smaller N when memory is limited.

Question: Why can a singly linked list delete an interior node in O(1) given a pointer to its predecessor, but not generally given a pointer to the node itself? This asymmetry looks like a trivia question — it is actually the entire design.

Premise: A singly linked list stores, per node, a value and exactly one pointer: to the successor.

Because: that is the minimal structure that can represent a sequence without contiguous memory

Premise: Deleting node X means the sequence must no longer reach X. Reachability comes only from whoever points at X.

Because: the list is defined by the pointer chain; a node nobody points at is simply not in the list

Premise: Nothing in X records who points at X — the pointer runs one way only.

Because: storing a back-pointer is exactly what you refused to pay for when you chose singly over doubly linked

Premise: For an interior node without an external predecessor index, find its predecessor by walking until node.next is X. Removing the head instead updates the head reference directly.

Because: there is no index and no reverse edge; search is the only available primitive

Premise: Interior deletion-by-node therefore requires O(n) search in the singly linked representation, but O(1) link work in the doubly linked representation. The latter stores an extra backward link; object layouts can add other overhead.

Because: the back-pointer converts a search into a dereference

The textbook hash-map plus doubly-linked-list design achieves expected O(1) operations. Production eviction schemes can approximate LRU or use different structures; not every cache uses this exact representation.

Name: Treasure hunt vs. bookshelf

Picture: An array is a bookshelf: you compute the position and reach straight to it. A linked list is a treasure hunt: each clue tells you only where the next clue is. You cannot skip ahead, and you cannot know how far you are from the end without walking it.Everything follows. Constant-time indexed access is unavailable without an additional index; reaching item 900 requires walking links. Splicing is trivial (rewrite one clue). And the walk is slow in a way Big-O hides, because each clue is at an unpredictable address.

• Index access: array O(1), list O(n). This alone disqualifies lists from most data work.

• Splice given the required node and predecessor/endpoints: array O(n), linked list O(1) link work. Search, allocation and synchronization remain separate costs.

• "Given position" is doing all the work in that sentence. If you have to search for the position first, the O(1) is a lie.

• Pointer chasing creates dependent memory reads and can limit prefetching. Contiguous references often improve locality; actual performance still needs measurement.

Trigger: Fire this model the moment you see: an LRU / MRU cache · a free-list allocator · Kafka or WAL segment chaining · a queue that must survive unbounded growth without a realloc · an practice problems about cycle detection · any structure where you already hold a handle to the element you want to remove.

Decision: You need a sequence that grows and shrinks at unpredictable points. Dynamic array, doubly linked list, or a chunked hybrid?

Name: Dynamic array (Python list, C++ vector)

Gain: O(1) indexing and amortised O(1) append. Contiguous storage helps sequential access; Python lists contain references, so payload access is not necessarily contiguous or memory-bandwidth-limited

Cost: middle insert/delete shifts O(n) entries. Growth may relocate the reference buffer and temporarily require both allocations; memory and latency depend on allocator and growth policy

Pick: you read or scan far more than you splice, which is the overwhelmingly common case in analytics and ML pipelines

Name: Doubly linked list

Gain: constant link updates with the necessary handles and no whole-sequence buffer relocation. Allocation, locking and reclamation can still cause latency spikes; node handles are valid only while their objects remain alive

Cost: O(n) indexed access, backward/forward links and separate node storage, dependent loads and allocation overhead; not necessarily one cache miss per node

Pick: frequent rewiring with direct handles, such as an exact-LRU order list or a suitable intrusive kernel/free-list structure

Name: Chunked / unrolled list (deque)

Gain: amortises both sides: contiguous runs give cache-friendly scans, while chunk-level pointers give cheap O(1) ends and no whole-buffer copy

Cost: in CPython deque, indexed access is O(1) near either end and O(n) in the middle. Middle insertion/removal requires movement/traversal and is O(n), not merely O(block size). Other unrolled lists have their own contracts

Pick: you need fast appends and pops at both ends — which is why collections.deque is built exactly this way

Verdict: Start with a dynamic array for indexed reads and scans, or deque for frequent work at both ends. Choose explicit linked nodes when stable handles and cheap rewiring solve a measured problem. Names such as adjacency list or log segment chain do not specify an in-memory representation: arrays, maps, files and linked nodes can all implement related abstractions.

(c) Hands-on · 25 min

Save as linked_list.py. No third-party dependencies. Except for the explicit cycle routines, inputs must be acyclic; merge inputs must also be sorted and node-disjoint. Removal requires 1 ≤ n ≤ list length. These teaching functions do not validate invalid positions. The dataclass's generated equality compares fields recursively, so traversal/cycle tests deliberately use is for identity and must not compare cyclic nodes with ==.

"""linked_list.py — the interview canon for singly linked lists.
 
Run:  python linked_list.py
"""
from __future__ import annotations
from dataclasses import dataclass, field
from typing import Optional
 
 
@dataclass
class Node:
    val: int
    next: Optional["Node"] = None
 
 
# ------------------------------------------------------------------
# Build / print helpers
# ------------------------------------------------------------------
def from_list(values: list[int]) -> Optional[Node]:
    dummy = Node(0)
    curr = dummy
    for v in values:
        curr.next = Node(v)
        curr = curr.next
    return dummy.next
 
 
def to_list(head: Optional[Node]) -> list[int]:
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out
 
 
# ------------------------------------------------------------------
# 1) Reverse in place — the classic 4-line loop
# ------------------------------------------------------------------
def reverse(head: Optional[Node]) -> Optional[Node]:
    prev, curr = None, head
    while curr:
        curr.next, prev, curr = prev, curr, curr.next    # tuple-swap in one line
    return prev
 
 
# ------------------------------------------------------------------
# 2) Detect a cycle — Floyd's tortoise and hare
# ------------------------------------------------------------------
def has_cycle(head: Optional[Node]) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
 
 
# ------------------------------------------------------------------
# 3) Find the cycle's entry point — the second half of Floyd's algorithm
# ------------------------------------------------------------------
def cycle_start(head: Optional[Node]) -> Optional[Node]:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # Restart one pointer from head; both move 1 step at a time; they meet at the entry.
            p = head
            while p is not slow:
                p = p.next
                slow = slow.next
            return p
    return None
 
 
# ------------------------------------------------------------------
# 4) Merge two sorted lists — the classic dummy-node pattern
# ------------------------------------------------------------------
def merge_two_sorted(a: Optional[Node], b: Optional[Node]) -> Optional[Node]:
    dummy = Node(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next
 
 
# ------------------------------------------------------------------
# 5) Find the middle — fast/slow, without measuring length first
# ------------------------------------------------------------------
def middle(head: Optional[Node]) -> Optional[Node]:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
 
 
# ------------------------------------------------------------------
# 6) Remove n-th from end — one pass with a gap
# ------------------------------------------------------------------
def remove_nth_from_end(head: Optional[Node], n: int) -> Optional[Node]:
    dummy = Node(0, head)
    lead = lag = dummy
    for _ in range(n + 1):
        lead = lead.next
    while lead:
        lead = lead.next
        lag = lag.next
    lag.next = lag.next.next
    return dummy.next
 
 
# ------------------------------------------------------------------
# Runner
# ------------------------------------------------------------------
if __name__ == "__main__":
    print("reverse [1,2,3,4,5]:", to_list(reverse(from_list([1, 2, 3, 4, 5]))))
    print("merge [1,3,5]+[2,4,6]:", to_list(merge_two_sorted(from_list([1, 3, 5]), from_list([2, 4, 6]))))
    print("middle [1,2,3,4,5]:", middle(from_list([1, 2, 3, 4, 5])).val)
    print("remove 2nd from end [1,2,3,4,5]:", to_list(remove_nth_from_end(from_list([1, 2, 3, 4, 5]), 2)))
 
    # Build a cycle: 1 -> 2 -> 3 -> 4 -> 5 -> 3
    a = from_list([1, 2, 3, 4, 5])
    tail = a
    while tail.next:
        tail = tail.next
    # find node with val 3
    entry = a
    while entry.val != 3:
        entry = entry.next
    tail.next = entry
    print("has_cycle:", has_cycle(a))
    print("cycle_start value:", cycle_start(a).val)

Anatomy of the script

How the pointer algorithms work

Name: reverse

Desc: Python evaluates the right-hand side before assigning the targets, so curr.next is saved before that link is overwritten. A single source line is not a thread-atomic transaction; the example assumes exclusive ownership of the list during reversal.

Name: has_cycle

Desc: Floyd's insight: in a cycle of length L, the hare gains 1 on the tortoise each step. After at most L steps inside the cycle, they meet. O(n) time, O(1) memory.

Name: cycle_start

Desc: After they meet, restart one pointer from head. Both move at speed 1. They meet exactly at the cycle entry — because of a beautiful modular-arithmetic identity (distance from head to entry equals distance from meet point to entry, mod cycle length).

Name: merge_two_sorted

Desc: The dummy node saves you from writing separate ‘first node’ logic. This trick appears in dozens of linked-list problems.

Name: middle

Desc: Fast/slow: hare runs twice as fast → when hare hits end, tortoise is at the middle. One pass, no length pre-computation.

Name: remove_nth_from_end

Desc: Two-pointer with a gap of n+1. When lead runs off the end, lag is exactly at the predecessor of the node to remove. Elegant and O(n) single-pass.

Expected values and structural checks

ClassName: ml-4 list-decimal space-y-1

reverse: [5,4,3,2,1] from a 4-line function that mutates in place. merge: [1,2,3,4,5,6] — the returned list reuses all input nodes. One temporary dummy node is allocated; it is not part of the returned chain. middle of [1..5] = 3. Of [1..6] = 4 (fast/slow lands on the second middle for even-length). remove 2nd from end [1..5] = [1,2,3,5]. has_cycle: True. cycle_start value: 3 — Floyd's algorithm finds the exact entry.

Goal: Rewrite ‘reverse’ recursively and compare — which is easier to reason about?

Hint: Base case: head is None or head.next is None → return head. Recursive case: reverse(head.next), then flip head.next.next = head, head.next = None. This uses O(n) call-stack space; check sys.getrecursionlimit() rather than assuming an exact failure length.

def reverse_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head
 
# Test both give the same result
h = from_list([1, 2, 3, 4, 5])
print(to_list(reverse_recursive(h)))   # [5,4,3,2,1]

A list longer than the available recursion depth can raise RecursionError; the exact threshold depends on the runtime and existing stack. Iterative reversal uses O(1) auxiliary references and avoids that limit, though constructing and retaining millions of nodes still costs memory and time.

(d) Production reality · 15 min

Where this shows up in the rest of the plan

Root: Linked lists as building blocks

Label: S026 · Stacks & Queues

Desc: CPython deque uses linked blocks; the queue abstraction does not require that representation.

Label: S028 · Trees & BSTs

Desc: Trees generalize navigation through node references, but their branching and no-cycle/root invariants differ from a linked list.

Label: S029 · Heaps & Priority Queues

Desc: A priority queue selects by priority rather than sequence position; a binary heap provides that interface using an array.

Label: S062 · Caching & Redis

Desc: LRU eviction is the classic hashmap-+-doubly-linked-list problem.

Label: S073 · Kernels & Threads

Desc: Linux provides intrusive linked lists alongside trees and other structures. The scheduler policy determines which structures it needs.

Label: S117 · Log-Structured Storage

Desc: LSM-tree memtables and skip-lists — linked-list DNA under a different name.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — click to reveal

Q: What's the fundamental trade-off between an array and a linked list?

A: Arrays offer O(1) indexed access and O(n) middle insertion. Linked lists offer O(n) indexed access and constant link updates when the needed handles are known; singly linked deletion needs the predecessor. Locality often favors arrays, but benchmark the actual operation.

Q: Write the 4-line reverse-in-place loop in pseudocode.

A: prev = None; curr = head while curr: nxt = curr.next curr.next = prev prev = curr; curr = nxt return prev

Q: Why does Floyd's tortoise-and-hare detect a cycle in O(n) time and O(1) memory?

A: The hare gains 1 on the tortoise every step. If there's a cycle of length L, after at most L steps inside the cycle they meet. Total steps: at most O(n). Space: two pointers.

Q: You have a pointer to a node in the MIDDLE of a singly linked list. How do you delete it in O(1)?

A: Copy the next node's value into this one, then set this.next = this.next.next. You've effectively deleted the next node, but the value at this position is now the one that used to be next. It does not remove the specified node object and changes what external references to it observe. It is valid only for a value-sequence contract with a successor, not identity-preserving deletion or the last node.

Q: Why does Python's collections.deque beat a naïve linked list?

A: CPython 3.14.0 links blocks of 64 references, reducing link/allocation overhead relative to one node per element. End operations are approximately O(1); middle access remains O(n). Performance relative to a custom list is workload-dependent.

Q: What is a dummy node and why is it useful?

A: A sentinel node before the real head. It removes the special case ‘what if the operation affects the head?’ — every insert/delete works uniformly. At the end you return dummy.next. It can simplify endpoint handling without a universal reduction in code length.

Q: Give one real system where a linked list is the right choice (not just a homework toy).

A: Linux's list_head embeds links in containing objects and supports constant-time rewiring with valid handles and appropriate synchronization. A textbook exact-LRU cache also combines a hashmap with a doubly linked order list. Redis's sampled approximate-LRU eviction is a different algorithm, not evidence that every cache uses that design.

Q: Why is the recursive reverse dangerous in Python?

A: It consumes one Python call frame per node, so sufficiently long input can exceed the configured recursion limit. Iterative reversal avoids O(n) stack usage; it does not make input storage free. Prefer it when list length is not tightly bounded.

Q: You must merge k sorted linked lists. Naive: merge two at a time → O(k·n). What's better?

A: Let n be the total nodes across k disjoint sorted lists. A heap holds at most one head per nonempty list: pop the smallest, append that node, and push its successor. Use a tie-break counter so equal values do not compare Node objects. Cost is O(k + n log(k + 1)) with O(k) heap space; balanced pairwise merging is another option.

Q: Stretch — explain why in Floyd's cycle algorithm, restarting one pointer from head and moving both at speed 1 finds the exact entry point.

Stretch: true

A: Let d be the distance from head to cycle entry, L the cycle length, and k the offset of the meeting node from the entry, with 0 ≤ k < L. If the tortoise has taken t steps when they meet, it may have completed extra laps: t = d + k + qL for some q ≥ 0. The hare has taken 2t steps, and their equal positions imply 2t − t ≡ 0 (mod L). Hence d + k ≡ 0 (mod L). After restarting one pointer at the head and advancing both one step at a time, d steps bring the restarted pointer to the entry and the other to offset k + d ≡ 0. Before then the restarted pointer is outside the cycle, so this is their first meeting. If d=0, the detected meeting is already at the entry.

Explain-out-loud test

Teach these three in one minute each, no notes:

1. What is a linked list, and what one thing does it do faster than an array?
2. Explain Floyd's cycle detection like I'm your grandparent.
3. Give one real-world system where a linked list is the right choice — and one where it's the wrong choice.

Grind this pattern in the LeetCode track

This session builds the mental model for linked lists. The full pattern treatment — templates, five graded problems each, and the design review follow-ups — lives in the dedicated LeetCode series:

L19 · Linked Lists I · L20 · Linked Lists II

Do the concept here, then go there to build the reflex.

What comes next

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

• 9. Classes — Python 3.14.8 documentation — Multiple names can refer to the same object, so mutations and copied references must be distinguished. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.