Linked Lists

A linked list is a chain of nodes where each node holds a value and a pointer to the next node — nothing more. There is no contiguous block of memory backing it, no fixed address you can jump to by doing arithmetic. That single design choice flips arrays' trade-off on its head: you lose O(1) random access, but once you're holding a node, inserting or deleting next to it costs O(1), because you're only rewriting a couple of pointers, not shifting an entire block of memory. Interviewers reach for linked lists constantly because the pointer-rewiring itself is where bugs live — dangling references, lost sublists, off-by-one hops — so a linked-list question tests whether you can reason precisely about state that changes one step at a time. The concept also underlies real systems: a browser's back/forward history, an LRU cache's eviction order, the internal structure of a hash table bucket using chaining, and — less obviously — the call stack itself is conceptually a linked list of frames.

Deep Dive: A Node Is Just Value + Pointer

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

n3 = Node(30, None)
n2 = Node(20, n3)
n1 = Node(10, n2)
head = n1

There is exactly one thing that makes a structure a linked list: a node does not know where the *next* node lives in memory in any predictable way — it only knows because a previous node explicitly told it, by storing that address. This is the opposite of an array, where element i's address is computable from the base address and i alone. The practical consequence is that you cannot ask "give me the 5th element" without starting at head and following .next five times — there is no shortcut, so indexed access is O(n).

What you get in exchange is that a node's neighbors are just references, and references are cheap to rewrite. If you already hold a reference to a node, splicing a new node next to it, or removing it, touches only that node and its immediate neighbors — a constant number of pointer writes regardless of how long the list is. That's the entire trade the structure is built around: pay per-access cost to gain near-free insert/delete once you're positioned.

Deep Dive: Insert and Delete — the Actual Pointer Rewiring

new_node = Node(5)
new_node.next = head
head = new_node

prev = head
for _ in range(k - 1):     # walk to index k-1
    prev = prev.next
new_node.next = prev.next  # 25 -> 30
prev.next = new_node       # 20 -> 25

prev = node_holding_10
prev.next = prev.next.next

Every one of these operations is "cheap" only in the pointer-rewiring step itself; the O(n) or O(k) cost, when it exists, comes entirely from the walk needed to *find* the right node, not from the rewiring. That distinction matters in interviews: insert-at-head is O(1) full stop, because you already hold head. Insert-at-position-k is O(k) because reaching the (k-1)th node requires k-1 hops — the rewiring at the end is still O(1). Compare this to an array insert at position k, which is O(n) even once you've *found* position k (trivially, in O(1), via indexing) — because inserting means shifting every element after k one slot to the right. The two structures spend their O(n) in different places: array insertion pays for the shift, linked-list insertion pays for the walk.

Deletion is the mirror image, and the classic trap is deleting the head or deleting when you only hold a reference to the node itself (not its predecessor). To delete a node you need the node *before* it, because that's the only place holding the pointer that must be rewritten — this is exactly why doubly linked lists exist (see below): they let you go backward without a separate walk.

Deep Dive: Reversing a Linked List — Why Three Pointers

def reverse(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next    # save
        curr.next = prev   # flip
        prev = curr        # step prev
        curr = nxt         # step curr
    return prev

You need three pointers — prev, curr, and a temporary nxt — because reversing a link means overwriting curr.next, and once you overwrite it, the only way to reach the rest of the original list is through whatever you saved beforehand. If you update curr.next = prev before saving the original curr.next somewhere, you have permanently lost the pointer to the remainder of the list — everything after curr becomes unreachable garbage. That's the single most common bug on this problem: doing the rewire before the save. The order in the code above is non-negotiable: save, rewire, advance, advance — in exactly that sequence.

Two pointers are not enough because at every step you need to simultaneously know three things: where you're advancing from (curr), where you already reversed to (prev, to point curr backward at), and where you're advancing to next (nxt, saved before it's destroyed). Drop any one of the three and you either lose the rest of the list or lose the ability to link backward.

Deep Dive: Singly vs Doubly vs Circular

A doubly linked list's extra prev pointer is worth its memory cost exactly when you need to move backward or delete a node given only a reference to that node (not its predecessor) — e.g. an LRU cache, where you hold a hash map of key to node and must unlink that node in O(1) on every access. Without prev, "delete this node" secretly costs O(n), because you'd have to walk from head to find its predecessor first. The cost is real, though: every node carries a second pointer (meaningful memory overhead at scale), and every insert/delete must keep two pointers consistent instead of one — twice the chances of a rewiring bug.

Circular lists solve a different problem: "there is no natural end" scenarios like a round-robin CPU scheduler cycling through processes or a music player set to repeat. The termination condition changes from "next is None" to "next is back to where I started," which is itself a common interview trap if you forget to guard against an infinite loop.

Key Pointers

• A node is value + pointer(s); there is no computable address for the k-th node, so indexed access is O(n).
• Insert/delete are O(1) once you're already at the right node — the O(n)/O(k) cost, when present, is the walk to find that node, not the pointer rewiring itself.
• Insert-at-head is O(1) on a linked list but O(n) on an array, because the array must shift every existing element over.
• Reversing a list needs three pointers (prev, curr, nxt) because overwriting curr.next destroys your only path to the rest of the list unless you saved it first.
• The reverse order matters: save next, rewire curr.next = prev, advance prev, advance curr — swapping the first two steps loses the tail of the list.
• Doubly linked lists trade extra memory (a second pointer per node) and more bookkeeping for O(1) backward traversal and O(1) deletion given just the node.
• Circular lists replace "next is None" termination with "next is back to head" — useful for round-robin and repeating structures, but an easy infinite-loop trap.
• Floyd's cycle detection (slow/fast pointers) finds a cycle in O(n) time, O(1) space, because a faster pointer gaining one node per step on a slower one must eventually lap it if the list loops.

How It Works

1. To search for a value: start at head, compare, follow .next, repeat until found or None — O(n) worst case, no shortcuts.
2. To insert at head: point the new node's next at the current head, then move head to the new node — in that order, or you overwrite the only reference to the old list.
3. To insert at tail: walk to the last node (O(n)) unless you maintain a tail pointer (O(1)), then set tail.next to the new node and move tail.
4. To insert at position k: walk to the node at position k-1, splice the new node in between it and its current next.
5. To delete a node: get a reference to its predecessor, then set predecessor.next = node.next, skipping the target node so nothing points to it anymore.
6. To reverse: iterate with prev/curr/nxt as shown above, ending when curr is None; return prev as the new head.
7. To detect a cycle: advance a slow pointer one step and a fast pointer two steps per iteration; if they ever point to the same node, there's a cycle, because the fast pointer closes the gap by one node every step and cannot skip past the slow pointer inside a loop.
8. To find the cycle's *start* (Floyd's extension): after slow and fast meet, reset one pointer to head and advance both one step at a time — they meet again exactly at the cycle's entry node, a consequence of the distances working out from where the first meeting happens.

Try It Yourself

Building a list, inserting at a position, reversing it with the three-pointer technique, and detecting a cycle with Floyd's algorithm.

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def reverse(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next   # save before we overwrite curr.next
        curr.next = prev  # rewire
        prev = curr       # advance prev
        curr = nxt         # advance curr
    return prev

def insert_at_position(head, pos, val):
    if pos == 0:
        return Node(val, head)
    node = head
    for _ in range(pos - 1):
        node = node.next
    node.next = Node(val, node.next)
    return head

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# build 10 -> 20 -> 30 -> 40
head = Node(10, Node(20, Node(30, Node(40))))
print("original          :", to_list(head))
head = insert_at_position(head, 2, 25)
print("after insert(2,25):", to_list(head))
head = reverse(head)
print("reversed          :", to_list(head))

# cycle test
a = Node(1); b = Node(2); c = Node(3)
a.next = b; b.next = c; c.next = a  # cycle back to a
print("has_cycle (cyclic):", has_cycle(a))

x = Node(1, Node(2, Node(3)))
print("has_cycle (acyclic):", has_cycle(x))

# Output:
# original          : [10, 20, 30, 40]
# after insert(2,25): [10, 20, 25, 30, 40]
# reversed          : [40, 30, 25, 20, 10]
# has_cycle (cyclic): True
# has_cycle (acyclic): False

Common Mistakes & Interview Traps

• Assuming a linked list has O(1) random access "because it's O(1) to insert" — insertion once positioned is O(1), but reaching position k is O(k), so indexed access is O(n).
• In the reverse-list algorithm, writing curr.next = prev before saving nxt = curr.next — this permanently severs the path to the rest of the original list.
• Forgetting to update head when the node being deleted or inserted-before is the current head, leaving head pointing at a now-orphaned or wrong node.
• Trying to delete a node "given only that node" in a singly linked list without its predecessor — you cannot rewire a pointer you don't have access to; either walk from head or use a doubly linked list.
• Off-by-one when inserting at position k: walking to index k instead of k-1 splices the new node one slot too late.
• Treating a circular list's termination the same as a normal list's ("stop when next is None") and looping forever, since the tail's next is never None by design.

Interview Q&A

Q: Why is inserting at the head of a linked list O(1) but inserting at the head of an array O(n)?

A: A linked-list head-insert only rewrites two pointers: the new node's next and the list's head reference — a constant amount of work no matter how long the list is. An array has no spare slot at index 0; inserting there means shifting every one of the n existing elements one position to the right first, which is O(n) work by definition.

Q: Walk through reversing a singly linked list step by step.

A: Keep three pointers: prev (starts None), curr (starts at head), and a temporary nxt. Each iteration: save nxt = curr.next, set curr.next = prev to flip the link backward, then advance prev = curr and curr = nxt. Repeat until curr is None; prev is now the new head, and every link in the list points the opposite direction from before.

Q: Why do you need three pointers (not two) to reverse a list safely?

A: You need to know where you came from (prev, to point backward to), where you are (curr, being rewired), and where you're going (nxt) simultaneously. Two pointers can't hold all three pieces of information at once — the moment you overwrite curr.next you need the original value already saved somewhere, which is exactly what the third pointer is for.

Q: What breaks if you update next before saving it?

A: If you run curr.next = prev before capturing nxt = curr.next, the reference to the rest of the original list is gone — nothing in your program points to it anymore, so it becomes unreachable. The algorithm silently produces a reversed fragment of just the nodes visited so far instead of the full reversed list.

Q: Singly vs doubly linked list — what's the real trade-off?

A: A doubly linked list adds a prev pointer to every node, which costs extra memory per node and extra bookkeeping on every insert/delete (two pointers to keep consistent instead of one), but in exchange you get O(1) backward traversal and O(1) deletion given only a reference to the node itself — no need to walk from head to find its predecessor. It's worth it specifically when your access pattern needs backward movement or node-handle deletion, like an LRU cache; otherwise a singly linked list is strictly cheaper.

Q: How would you detect a cycle in a linked list, and why does Floyd's algorithm work?

A: Run two pointers from head, a slow one advancing one node per step and a fast one advancing two. If there's no cycle, the fast pointer simply reaches None first. If there is a cycle, both pointers are eventually confined inside the loop, and because the fast pointer gains exactly one node of distance on the slow pointer every step, that gap must eventually shrink to zero — they collide inside the loop. It runs in O(n) time and O(1) space, unlike a hash-set approach which is O(n) time but O(n) space.

Follow-up: Once you know there's a cycle, how do you find where it starts?

A: After slow and fast meet inside the cycle, reset one pointer to head and leave the other at the meeting point, then advance both one step at a time. They meet again exactly at the cycle's entry node — this falls out of the distance math (the distance from head to the entry equals the distance from the meeting point to the entry, going around the loop).

Follow-up: Could you detect a cycle without Floyd's algorithm?

A: Yes — walk the list and put each visited node's identity (not value, since values can repeat) into a hash set, checking membership before each insert; a repeat means a cycle. That's O(n) time like Floyd's, but O(n) extra space instead of O(1), which is the trade-off interviewers are usually checking you can articulate.

Follow-up: Why can't you use node *values* to detect a cycle instead of node identity?

A: Distinct nodes can legitimately hold the same value (a list of [5, 3, 5, 3] is perfectly acyclic), so matching on value would produce false positives. You must track the actual object/memory identity of each node, not its data.

Trade-offs

A linked list is the wrong choice whenever your workload is dominated by random access or by iterating repeatedly with cache-friendly locality — an array (or dynamic array) wins there because contiguous memory means the CPU can prefetch ahead, while a linked list scatters nodes across the heap and forces a pointer chase on every hop, which is slow in practice even though both are "O(n) to traverse" on paper. A linked list also costs extra memory per element for the pointer(s) themselves, which matters when storing many small values. It earns its place specifically when you need frequent insertion/deletion at known positions (especially the front, or given a node handle in a doubly linked list) and don't need random access — the internal chaining of a hash table bucket, an LRU cache's eviction list, or an undo history that only ever removes from one end are all good fits. When in doubt for general-purpose storage, default to a dynamic array; reach for a linked list only when its specific insert/delete pattern is the actual bottleneck.

PracticeSolve related problems in the 150 →