S025 · Linked Lists — Singly, Doubly, When They Win
The data structure interviewers still love — plus the three real-world situations where a linked list actually beats an array.
🎯 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 are a rite of passage. In real Python code you'll rarely build one from scratch — list beats it on every axis except a few narrow wins. But in interviews, they're a proving ground for pointer discipline: if you can reverse a linked list in place with a dummy node, you can reason about pointers anywhere. And they DO win in specific real systems: LRU caches, OS kernel task queues, and Redis lists all pick a linked list on purpose.
- 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.
- State, in one sentence each, why deques and LRU caches are linked lists under the hood.
Prerequisites
- S023 · Arrays & Strings — the baseline we're comparing against.
- S013 · Classes & Objects — nodes as classes.
(a) Intuition · 5 min
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
- Index access — array O(1), linked list O(n). Arrays always win here.
- Middle insert / delete WHEN YOU HAVE THE NODE — array O(n), linked list O(1). Linked list wins here.
- Middle insert WHEN YOU MUST FIND THE POSITION — both O(n). Array is usually faster in practice due to cache locality.
- Memory overhead — array = 1 pointer per slot; linked list = ~3 pointers per node (value + next + prev + allocator overhead). Arrays are usually 2–4× smaller.
Timeline — the rise and fall of the linked list
- 1955IPL invents linked listsAllen Newell + Herbert Simon build Information Processing Language for AI research — pointers over contiguous memory to support flexible symbolic structures.
- 1958LISPJohn McCarthy's LISP makes the cons cell (a two-slot linked-list node) the foundational data type. Half of programming language design flows from here.
- 1972Unix kernel task listKen Thompson uses doubly-linked lists for process tables — O(1) removal when a process exits.
- 1990STL list<T>C++ ships std::list as a doubly-linked list. Programmers overuse it for a decade before realising vector is usually faster.
- 2014Bjarne's ‘Vector vs List’ talkBjarne Stroustrup demonstrates that std::vector beats std::list on random insert for containers up to ~500k items — cache is king.
- 2016Rust's LinkedList<T> stays nicheRust ships one but the docs literally recommend Vec instead. The community consensus is complete.
(b) Visual walkthrough · 15 min
Singly vs doubly linked
The three linked-list surgeries you must own
new.next = p.next; p.next = new. Two writes, done. Doubly-linked adds the reverse pointers.
q.next = p.next; p.next = None. In doubly-linked with only p: p.prev.next = p.next; p.next.prev = p.prev.
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
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
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 why every LRU implementation is doubly-linked + hashmap
Linux task_struct
- Processes must be O(1) removable from any list at any time
- Signal handlers, wait queues, run queue — all doubly linked
- Contiguous arrays would need to shuffle process memory
Text editors, IDEs
- Cheap append + cheap discard from either end
- No random access needed
- Doubly linked is the natural fit
Just use list / deque / array
- Cache locality beats pointer chasing
- Fewer allocations = faster + smaller
- Simpler to reason about
"Linked lists beat arrays for insertion and deletion, because you just repoint two pointers instead of shifting elements."
The splice is O(1), but only if you already hold a pointer to the node. Getting there is O(n), and that traversal is a chain of dependent pointer loads the CPU cannot prefetch. In practice an array's O(n) memmove usually wins up to surprisingly large n, because memmove is a sequential, vectorised, cache-perfect operation.
Because the myth is true in the model you were taught in — a machine where every memory access costs the same. That machine has not existed since the 1980s. An L1 hit is ~1ns, a DRAM miss is ~100ns, and a linked list walk is a near-guaranteed miss per node because each node lives at an unrelated address. Big-O counts operations; it does not count that one of your operations is 100× more expensive than the other.
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) # chain is many times slower for identical workWhy can a singly linked list delete a node in O(1) given a pointer to its predecessor, but not given a pointer to the node itself? This asymmetry looks like a trivia question — it is actually the entire design.
- 1A singly linked list stores, per node, a value and exactly one pointer: to the successor.forced by · that is the minimal structure that can represent a sequence without contiguous memory
- 2Deleting node X means the sequence must no longer reach X. Reachability comes only from whoever points at X.forced by · the list is defined by the pointer chain; a node nobody points at is simply not in the list
- 3Nothing in X records who points at X — the pointer runs one way only.forced by · storing a back-pointer is exactly what you refused to pay for when you chose singly over doubly linked
- 4So to unlink X you must find its predecessor, and the only way to find it is to walk from the head until
node.next is X.forced by · there is no index and no reverse edge; search is the only available primitive - 5Hence deletion-by-node is O(n) in a singly linked list and O(1) in a doubly linked one, and the difference is exactly one pointer per node.forced by · the back-pointer converts a search into a dereference
Therefore the singly/doubly choice is not stylistic — it is buying O(1) arbitrary deletion for the price of 8 extra bytes per node plus the discipline of keeping two pointers consistent on every mutation.
And note what this predicts: an LRU cache needs O(1) eviction of an arbitrary node found via a hash map, so it must use a doubly linked list. That is not a stylistic choice in the classic LRU design — the derivation forces it. Go look at any production LRU implementation and you will find a hash map pointing into a doubly linked list, every time.
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. Random access is impossible (no arithmetic gets you to item 900). 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 position: array O(n), list O(1). This is the only thing lists are actually for.
- "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 defeats the prefetcher. Contiguity is a performance feature, not an implementation detail.
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 interview question about cycle detection · any structure where you already hold a handle to the element you want to remove.
You need a sequence that grows and shrinks at unpredictable points. Dynamic array, doubly linked list, or a chunked hybrid?
collections.deque is built exactly this wayDefault to the dynamic array and stop thinking about it. Modern hardware makes contiguity worth roughly an order of magnitude, and the O(n) memmove you were taught to fear is the single most optimised operation your CPU has. Reach for a linked list only when the derivation above forces you to: you hold a handle and need O(1) removal.
The honest summary for production data work: you will implement a linked list for an LRU cache or an interview, and almost never otherwise. But you must understand it, because it is the substrate underneath deques, adjacency lists, free lists, and every write-ahead log segment chain you will debug.
(c) Hands-on · 25 min
Save as linked_list.py. Zero dependencies.
"""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
Linked List Cycle - Floyd's Tortoise and Hare - Leetcode 141 - Python
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]Try reverse_recursive(from_list(list(range(2000)))) and watch it crash with RecursionError. Iterative reverse handles 2 million nodes fine. This is why production code prefers iteration over recursion on linked lists.
(d) Production reality · 15 min
The Linux kernel has hundreds of thousands of processes coming and going. Each needs to be listable by scheduler, by parent, by process group, by wait queue, and be removable from any of them in O(1) when the process exits.
An array of PIDs would need to shuffle megabytes of process descriptors on every exit — unacceptable.
list_head struct. Insert / remove is O(1) pointer rewiring. Linux ships one of the most-copied macro libraries in history — include/linux/list.h.functools.lru_cache, Java's LinkedHashMap, and Redis's maxmemory-policy allkeys-lru all use.std::list ‘because middle-insert is O(1)’. Profiling six months later shows it's the slowest container in their codebase — cache misses on every traversal, allocator pressure from small nodes.std::vector. Middle inserts are now O(n) but the constant is so tiny that for lists up to ~500k items vector is FASTER than list on random insert (Bjarne's talk demonstrates this empirically). For occasional middle inserts on huge lists, std::deque or a gap-buffer beats both.Where this shows up in the rest of the plan
(e) Recall + stretch · 10 min
Explain-out-loud test
Teach these three in one minute each, no notes:
- What is a linked list, and what one thing does it do faster than an array?
- Explain Floyd's cycle detection like I'm your grandparent.
- Give one real-world system where a linked list is the right choice — and one where it's the wrong choice.
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.