Overview
Curated: · Written: · Reviewed:
Linked lists
Linked lists are the structure interviews ask about most and production code should reach for least, and holding both facts at once is the mark of a good answer. This guide separates what the structure genuinely buys — constant-time splicing at a node you already hold — from the constant-time insertion candidates often claim, and it is direct about why contiguous storage usually wins on real hardware. It then works through the pointer manipulations that interviews actually test: sentinel-based splicing, iterative reversal, the runner gap, cycle detection and its visited-set alternative, merge sort by splitting and splicing, and the doubly linked list plus hash map that makes an LRU cache constant time.
what a linked list actually buys
A linked list gives constant-time insertion and removal at a position you already hold a reference to, and nothing else.
Each node stores a value and a reference to the next node, so splicing is a couple of pointer writes, while reaching position i takes i steps.
Splicing at a held node is O(1); reaching position i is O(i).
node.next = node.next.next # O(1) - you already hold the node
# but getting there:
node = head
for _ in range(i): node = node.next # O(i) - the part people forget to quote
Interview trap. Quoting constant-time insertion without the qualifier 'at a known node' is the single most common error, because finding the position is the linear part.
Engineering practice. Choose a linked list only when the algorithm already holds the node — an LRU cache, an intrusive queue, a free list — and use an array otherwise.
why arrays usually win in practice
For most workloads a dynamic array outperforms a linked list even on insertion-heavy patterns, because of memory locality.
Array elements are contiguous and prefetchable, while each linked node is a separate allocation reached through a dependent load that may miss the cache.
Same asymptotics; the contiguous scan is the one the hardware can prefetch.
import timeit
timeit.timeit("sum(a)", "a = list(range(1_000_000))", number=10) # ~0.04s, contiguous
# A linked traversal of 1,000,000 nodes is a dependent load per element:
# roughly 10x slower, with 3-5x the memory.
Interview trap. Comparing the two structures on asymptotics alone predicts the wrong winner for the sizes real programs use.
Engineering practice. Default to the contiguous structure, and justify a linked list with a measurement or a specific structural need rather than with a complexity table.
the dummy head node
A sentinel node before the real head removes the special case where the operation affects the first element.
With a sentinel, every insertion and deletion has a predecessor to modify, so the head-specific branch disappears entirely.
The sentinel removes the head special case, so the splice logic exists once.
def remove_all(head, target):
dummy = Node(None, head) # every real node now has a predecessor
prev = dummy
while prev.next:
if prev.next.val == target: prev.next = prev.next.next
else: prev = prev.next
return dummy.next # the new head, whatever happened
Interview trap. Handling the head as a special case duplicates the splice logic, and the two copies drift apart as the code is maintained.
Engineering practice. Allocate the sentinel at the start of the function and return the node after it, which is both shorter and easier to argue correct.
iterative reversal
Reversing a singly linked list needs three pointers and one pass, and the order of the four assignments inside the loop is the whole algorithm.
Save the next node, redirect the current node's link backwards, advance the trailing pointer to the current node, then advance the current pointer to the saved node.
Save next before redirecting, or the rest of the list is lost.
prev, node = None, head
while node:
nxt = node.next # save first
node.next = prev # then redirect
prev, node = node, nxt
return prev
# 1 -> 2 -> 3 becomes 3 -> 2 -> 1. Redirect before saving and the loop ends after one step.
Interview trap. Redirecting the link before saving the next node loses the rest of the list, and the loop then terminates early with a two-element result.
Engineering practice. Write the save first, and trace a three-node list by hand — that length exposes every ordering error.
recursive reversal and its cost
The recursive reversal is shorter but uses stack depth proportional to the list length.
Each frame holds one node, so a list longer than the runtime stack allows fails with an overflow rather than a slow result.
Elegant, and O(n) stack: 10,000 nodes overflow the default 1,000-frame limit.
def reverse(node, prev=None):
if not node: return prev
nxt = node.next; node.next = prev
return reverse(nxt, node) # one frame per node
reverse(build(10_000)) # RecursionError
Interview trap. Presenting the recursive version as equivalent hides an O(n) space cost that the iterative version does not have.
Engineering practice. State the space bound alongside the time bound, and prefer the iterative form for lists whose length is bounded only by input size.
reversing a sublist
Reversing a range inside a list requires holding the node before the range and the node after it, both captured before any link is changed.
The range is reversed in isolation and then spliced back, so the surrounding links are restored from the two saved references.
Capture both boundaries before any link changes.
dummy = Node(None, head)
before = dummy
for _ in range(left - 1): before = before.next # captured now
tail = before.next # will become the range's end
# ... reverse the range ...
before.next = new_head; tail.next = after # spliced from the saved references
Interview trap. Recomputing the boundary nodes after the reversal reads links that the reversal has already changed, producing a cycle or a truncated list.
Engineering practice. Capture both boundaries first, reverse, then splice, and use a sentinel so the case where the range starts at the head needs no branch.
deleting a node
Deleting from a singly linked list requires the predecessor, which is why deletion given only the target node is not generally possible.
The usual workaround copies the successor's value into the target and deletes the successor instead, which works only when the target is not the last node.
The value-copy trick breaks identity and cannot delete the tail.
def delete_given_only(node):
node.val = node.next.val # any external reference to node.next is now wrong
node.next = node.next.next # and this fails outright if node is the tail
Interview trap. The value-copy trick breaks identity: any external reference to the successor now points at a freed or wrong node.
Engineering practice. Track the predecessor during traversal, and treat the copy trick as a puzzle answer rather than a production technique.
the runner technique
Two pointers separated by a fixed gap find the nth node from the end in one pass.
The leading pointer advances n steps first; both then advance together, so when the leader reaches the end the trailer is exactly n nodes back.
Advance the leader n steps first; the gap is what locates the nth from the end.
dummy = Node(None, head)
lead = trail = dummy
for _ in range(n): lead = lead.next
while lead.next: lead = lead.next; trail = trail.next
trail.next = trail.next.next # removes the nth from the end
# 1->2->3->4->5, n=2 removes 4. n=5 removes the head, which the dummy handles.
Interview trap. Getting the gap off by one produces a solution that deletes the wrong node, and the error is invisible unless the test targets the head or the tail.
Engineering practice. Derive the gap from the sentinel-based formulation, and test removing the first and last nodes explicitly.
cycle detection in constant space
A fast pointer and a slow pointer detect a cycle without a visited set.
Inside a cycle the gap between the two pointers closes by one each step, so they must eventually coincide; without a cycle the fast pointer reaches the end.
Check both fast and fast.next before advancing.
slow = fast = head
while fast and fast.next: # both, or an even-length acyclic list crashes
slow, fast = slow.next, fast.next.next
if slow is fast: return True
return False
Interview trap. Dereferencing the fast pointer's second step without checking the first for null crashes on even-length acyclic lists.
Engineering practice. Check both the fast pointer and its successor before advancing, and test lists of both parities.
the visited-set alternative
A hash set of visited nodes also detects cycles, in linear time and linear space, and is sometimes the better answer.
It identifies the entry node directly with no second phase, and it generalises to structures where the pointer walk is not a simple chain.
Linear memory, but it gives the entry node with no second phase.
seen = set()
while node:
if id(node) in seen: return node # the entry, directly
seen.add(id(node)); node = node.next
On a 1,000,000-node list that is roughly 33 MB against the walk's 56 bytes.
Interview trap. Dismissing it as inferior ignores that its simplicity is worth real memory when the list is short and the code must be obviously correct.
Engineering practice. Use the constant-space walk when memory is constrained, the set when clarity matters or the structure branches, and say which constraint decided it.
finding the intersection of two lists
Two lists that merge share every node after the junction, so the intersection is found by aligning their lengths.
Advancing the pointer on the longer list by the length difference makes both pointers equidistant from the end, after which they meet at the junction.
Compare identity, not value: equal values are not the junction.
a, b = headA, headB
while a is not b: # `is`, not `==`
a = a.next if a else headB # both walk len(A) + len(B) and meet at the junction
b = b.next if b else headA
return a # None when they never intersect
Interview trap. Comparing values instead of node identity reports a false intersection whenever the two lists happen to contain equal values.
Engineering practice. Compare node identity, not value, and handle the no-intersection case by letting both walks terminate at null together.
merging two sorted lists
Merging sorted lists is splicing, not copying: no new nodes are needed and the operation is constant space.
A sentinel and a tail pointer let each step attach the smaller head and advance that list, with the remaining list attached wholesale at the end.
Splice, do not allocate: the result reuses the input nodes.
dummy = tail = Node(None)
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 # attach the remainder wholesale
return dummy.next
Interview trap. Building a new list by allocating nodes doubles the memory and loses the main advantage the linked structure had here.
Engineering practice. Splice in place with a sentinel, and remember to attach the non-empty remainder rather than looping over it.
merge sort on a linked list
Merge sort is the natural sort for a linked list because it needs no random access and merges by splicing.
The list is split at the midpoint found by a fast-and-slow walk, each half is sorted recursively, and the results are merged in constant extra space per merge.
No random access needed, and each merge is O(1) extra space.
def sort(head):
if not head or not head.next: return head
mid = split(head) # sever, then recurse
return merge(sort(head), sort(mid))
O(n log n) time, O(log n) stack depth from the recursion.
Interview trap. Quicksort on a linked list is possible but partitions poorly without random access, and its pivot choice degrades more sharply.
Engineering practice. Use merge sort, and note the O(log n) stack depth from the recursion when defending its space bound.
splitting a list in half
The midpoint split must sever the first half's tail, or the recursion never terminates.
The slow pointer ends at the midpoint, and the node before it must have its link set to null so the two halves are genuinely separate lists.
Sever the first half's tail, or the recursion never terminates.
def split(head):
slow, fast, prev = head, head, None
while fast and fast.next:
prev, slow, fast = slow, slow.next, fast.next.next
prev.next = None # the severing step
return slow
# On 1 -> 2 the halves are [1] and [2]; without prev.next = None both halves are 1 -> 2.
Interview trap. Splitting without severing leaves both halves sharing a suffix, which recurses forever or produces duplicated elements.
Engineering practice. Keep a pointer to the node before the slow pointer, sever explicitly, and test the two-element case where the split is most fragile.
doubly linked lists
A backward link makes deletion possible given only the target node, at the cost of a second pointer per node and a second update per operation.
Every splice must fix four links rather than two, and every invariant now has a mirror that can be violated independently.
Four links per splice, and forgetting one corrupts only the reverse walk.
def unlink(node):
node.prev.next = node.next
node.next.prev = node.prev # the line that is easy to omit
node.prev = node.next = None
Assert both directions in tests; a forward-only check passes a half-broken list.
Interview trap. Updating the forward links and forgetting one backward link produces a list that traverses correctly in one direction and corrupts in the other.
Engineering practice. Write splice and unsplice as single functions used everywhere, and assert both directions in tests rather than only the forward walk.
circular lists and sentinels
A circular doubly linked list with one sentinel removes every null check and every empty-list special case.
The sentinel is always present, so insertion and removal never encounter a null neighbour and the empty list is the sentinel pointing at itself.
Terminate on the sentinel, not on None - there is no None.
sentinel.next = sentinel.prev = sentinel # the empty list
node = sentinel.next
while node is not sentinel: # not `while node`
visit(node); node = node.next
Interview trap. Iterating a circular list with a null-termination loop never ends, so the termination condition must be the sentinel itself.
Engineering practice. Terminate on reaching the sentinel, and keep the sentinel out of any user-visible iteration.
the LRU cache structure
A least-recently-used cache is a hash map to nodes of a doubly linked list, which is the canonical case where the linked structure is genuinely right.
The map gives O(1) access to any node and the list gives O(1) move-to-front and eviction from the tail, so every operation is constant time.
Map to nodes plus a doubly linked list: every operation O(1).
def get(self, key):
node = self.index.get(key)
if not node: return -1
self.unlink(node); self.push_front(node) # O(1) reorder
return node.val
def evict(self):
lru = self.sentinel.prev # O(1) - no scan for the oldest
self.unlink(lru); del self.index[lru.key]
Interview trap. Implementing the recency order with an array or by timestamp scanning turns the constant-time eviction into a linear one.
Engineering practice. Keep the map and list strictly in sync in one class, and test that eviction and access reorder produce the same state as a reference model.
intrusive lists
Embedding the links inside the stored object removes a level of indirection and an allocation per element.
The node is the object, so insertion needs no allocation and the memory layout is decided by the object rather than by the container.
The object is the node: no allocation per insertion, one membership per link set.
class Task:
__slots__ = ("payload", "next", "prev") # links live in the object
# Inserting a Task into two lists with one link set corrupts both, silently.
Interview trap. An object can then belong to at most one list per embedded link set, and forgetting that produces silent corruption when it is inserted twice.
Engineering practice. Use intrusive lists where allocation must be avoided, and make the single-membership rule explicit in the type or in an assertion.
memory overhead per element
A linked node costs at least one pointer per link plus allocator overhead, which for small values can exceed the value itself.
A list of machine integers can use three to five times the memory of an array holding the same values, before fragmentation.
A Python list of a million ints is 8 MB; a node-per-element list is far more.
import sys
sys.getsizeof(list(range(1_000_000))) # 8,000,056 bytes
sys.getsizeof(Node(0, None)) # 56 bytes header + 2 pointers, per element
Interview trap. Ignoring per-node overhead makes a linked structure look free in a design document and expensive in production.
Engineering practice. Compute the per-element overhead when sizing, and consider a chunked or unrolled list when the element is small.
unrolled lists and deques
A list of small arrays recovers most of the locality of an array while keeping cheap insertion at block boundaries.
This is how most standard-library deques are built, which is why they offer constant-time operations at both ends without the per-element pointer cost.
collections.deque is a linked list of blocks, which is why both ends are O(1).
from collections import deque
d = deque(range(1_000_000))
d.popleft() # O(1) - a list would shift 1,000,000 elements
d.pop() # O(1)
d[500_000] # O(n) - indexing is the price
Interview trap. Assuming a deque is a linked list of single elements mispredicts both its memory use and its iteration speed.
Engineering practice. Reach for the standard deque before writing a linked list, and read its documented complexity for the operations in question.
recursion over lists
Recursive list algorithms are elegant and carry stack depth proportional to length, which makes them unsuitable for unbounded input.
Every recursive list function has an iterative equivalent using an explicit pointer or stack, with identical time complexity and constant or explicit space.
Readable, and bounded by the recursion limit rather than by memory.
sys.setrecursionlimit(1000) # default
# A recursive length() overflows at ~1,000 nodes; the iterative one runs to memory.
Interview trap. Choosing recursion for readability on a structure whose length is attacker-controlled turns a style preference into a crash.
Engineering practice. Use recursion for bounded lists and tests, and convert to iteration wherever length is unbounded.
in-place versus copying
Most list algorithms can rearrange links in place, which is the reason to use the structure at all.
In-place rearrangement is constant space but destroys the caller's list, so the contract has to say which happens.
Say whether the input is consumed; the caller's head may no longer be the head.
new_head = reverse(head)
# `head` now points at the tail. Returning the new head is not optional.
Interview trap. Mutating the caller's list while returning a new head leaves the caller holding a reference into the middle of the result.
Engineering practice. Document whether the input is consumed, and return the new head explicitly so the caller can rebind.
testing pointer manipulation
Link-manipulation defects concentrate at the head, the tail, and lengths zero, one, and two.
Those cases are where a missing sentinel, an unsevered link, or an off-by-one gap first becomes visible.
The defects live at lengths 0, 1 and 2, and at the head and tail.
for n in range(0, 4):
lst = build(list(range(n)))
assert to_list(reverse(lst)) == list(reversed(range(n)))
Interview trap. Testing only on lists of five or more elements passes almost every incorrect implementation in this family.
Engineering practice. Test exhaustively at small lengths against a reference built from an array, and assert the full resulting sequence rather than just the head.
detecting corruption
A corrupted list usually manifests as an infinite loop rather than an exception, so traversals over untrusted structures need a bound.
A cycle introduced by a bad splice makes any length or print operation hang, consuming a thread indefinitely.
A bad splice hangs the traversal instead of raising.
def length(head, limit=10_000_000):
n = 0
while head:
n += 1
if n > limit: raise Corrupted("cycle or runaway list")
head = head.next
return n
Interview trap. Assuming a hang is a performance problem rather than a structural one sends the investigation in the wrong direction.
Engineering practice. Bound traversal length in debug builds or add a cycle check in the invariant assertion, so corruption fails loudly and early.
choosing the structure
The question is not whether a linked list can do the job but whether anything else does it better, and usually something does.
Arrays win on iteration and memory, hash maps win on lookup, deques win on both ends, and the linked list wins only when nodes are held externally and spliced.
Name the operation that needs a held node, or use the array.
| Need | Structure |
|---|---|
| Index access, iteration, memory | list |
| Cheap push/pop at both ends | deque |
| O(1) reorder of a node you already hold | doubly linked list + index |
| Keyed lookup | dict |
Interview trap. Selecting a linked list because the problem says 'list' is a naming coincidence, not a design argument.
Engineering practice. Name the operation that requires a held node, and if there is none, choose the contiguous structure.