Linked lists — fewer than you think, harder than they look

Honest take — linked lists are over-represented in interview problems and under-represented in real ML/data code. You'll write maybe one a year in production. You'll read questions about them all the time.

Why the gap? Because linked lists exist for one specific reason — O(1) insert and delete given a pointer to the node. Arrays beat them at almost everything else.

Let's enumerate.

Cache locality — arrays win. Memory-contiguous, prefetcher-friendly, one cache line covers many elements. Linked-list nodes are scattered across the heap; each access can be a cache miss.

Indexing — arrays win. O(1) random access. Linked lists are O(n) — you walk from the head.

Memory overhead — arrays win. A list of N ints is roughly N pointers. A linked list is N pointers plus N node headers (next pointer, possibly prev pointer, possibly a tag).

Iteration speed — arrays win again, by a lot, because of cache effects.

The one place linked lists win — O(1) insert at a known position, when you have a pointer to the node before. This matters in:

LRU caches — a doubly linked list lets you move a node to the front in O(1) when accessed.

Task schedulers — insert and remove in O(1) anywhere in the queue.

Memory allocators — free lists tracking unused blocks.

Undo/redo stacks where you might insert in the middle.

For ML/AI specifically? You'll touch them in interviews, in some library internals, and almost never in your own code. But the underlying skill — pointer manipulation, the three-pointer dance, recognising cycles — generalises to tree and graph code, where it matters more.

Learn linked lists for the skill, not for the structure.

If you can reverse a singly linked list iteratively without bugs, you understand pointer manipulation. It's the most-asked warmup question in interviews because it tests exactly the skill that the harder linked-list questions build on.

The trick is the three-pointer dance.

prev = None
curr = head
while curr is not None:
    nxt = curr.next   # save before we rewire
    curr.next = prev  # rewire current node
    prev = curr       # advance prev
    curr = nxt        # advance curr
return prev

Walk through it on a four-node list — head → 1 → 2 → 3 → 4 → null.

Iteration 1: prev=None, curr=node1. Save nxt=node2. Rewire node1.next=None. Advance prev=node1, curr=node2. State: 1 (next: None), 2 → 3 → 4.

Iteration 2: prev=node1, curr=node2. Save nxt=node3. Rewire node2.next=node1. Advance prev=node2, curr=node3. State: 2 → 1 → None, 3 → 4.

Iteration 3: prev=node2, curr=node3. Save nxt=node4. Rewire node3.next=node2. Advance prev=node3, curr=node4. State: 3 → 2 → 1 → None, 4.

Iteration 4: prev=node3, curr=node4. Save nxt=None. Rewire node4.next=node3. Advance prev=node4, curr=None. State: 4 → 3 → 2 → 1 → None.

Loop ends. Return prev (which is now the new head: node4).

One pass. O(n) time. O(1) extra space. The save-before-rewire is the part that's easy to forget — without it, you lose access to the rest of the list as soon as you change curr.next.

Draw it on paper once. Code it from memory. Done. The skill transfers to harder problems.

Here's a minimal singly linked list in Python — Node class plus a couple of operations. Notice the structural simplicity. A Node holds a value and a pointer to the next node. That's it.

The reverse function is the three-pointer dance from the morning post, written compactly. Read it side-by-side with the explanation; the code matches the steps line by line.

The walk function is a generator. It yields each value as it walks the list head-to-tail. Once you've implemented __iter__ — well, in this case, walk is a top-level generator, but the pattern is the same — your linked list participates in for-loops, list(...) materialisation, sum/len computations.

A few notes on Python-specific design.

We could use a dataclass. @dataclass with two fields would generate __init__ and __repr__ for free. For a structure this small, the manual __init__ is fine. The main reason to keep it manual is that the recursive type 'Node | None' as a default is a bit awkward for dataclasses.

We could use __slots__. For a class that creates millions of instances (linked lists with millions of nodes), __slots__ skips the __dict__ allocation per instance and saves substantial memory. Doesn't matter for interview problems; matters in production data structures.

We should add __repr__. For interview code, often skipped. For real code, always present.

The linked list is mostly a teaching tool here. The Python stdlib has collections.deque which gives you O(1) append-and-popleft semantics with a C-implemented doubly linked list under the hood. For 99% of cases where you'd want a linked list, use deque. For the remaining 1%, hand-roll it.

Question: given a singly linked list, does it have a cycle? (Some node's .next points back to a previous node, creating a loop.)

Naive solution — visit each node, store visited nodes in a set, check membership before adding. O(n) time, O(n) space.

Clever solution — Floyd's tortoise-and-hare algorithm. O(n) time, O(1) space.

slow = head; fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast:
        return True
return False

The insight — slow moves one step per iteration; fast moves two. If there's no cycle, fast hits None (because fast or fast.next is None at some point) and we return False. If there IS a cycle, fast eventually laps slow inside the cycle and they meet at some node.

Why they always meet inside a cycle — relative speed. Inside the cycle, fast gains one step per iteration on slow. Eventually the gap closes to zero, regardless of the cycle's size.

Why O(1) space — we only track two pointers. No set of visited nodes.

A related problem — find the start of the cycle. Variant of Floyd that's also O(1) space. After they meet inside the cycle, reset one pointer to head, then advance both one step at a time. They meet again at the cycle's start. This is the trick interviewers love because it's surprising.

Floyd's algorithm shows up beyond linked lists. The same technique solves 'find the duplicate in an array of n+1 numbers in [1, n]' (treat values as pointers), and certain modular-arithmetic problems.

Know it. The next time you see a 'detect cycle' question, you have a constant-space answer ready.

End of Day 18.

Linked lists are a small chapter in the broader DSA story. The skill is pointer manipulation; the structure is just an excuse to practise it.

What we covered.

Morning, the honest take. Linked lists exist for O(1) insert/delete given a pointer. Arrays win at almost everything else (cache locality, indexing, memory overhead, iteration speed). Real production code uses them rarely; interviews use them constantly.

Midday, the universal warmup — reverse a singly linked list iteratively. The three-pointer dance (prev, curr, next). Save before rewire. One pass, O(n), O(1) extra space.

Afternoon, a 16-line linked list implementation in Python. Node class plus reverse plus a generator-based walk. Notes on when to use __slots__, dataclass, deque alternatives.

Evening, Floyd's cycle detection. Slow/fast pointers, O(1) space. The subtle relative-speed argument that proves they always meet inside a cycle.

A broader thought. Linked lists are an under-rated test of one specific skill — keeping pointer operations correct under change. The same skill makes tree code (rotate a node, splice in a subtree) and graph code (relax an edge) correct. The DSA week that builds toward trees and graphs starts here.

Tomorrow, Day 19, hash maps and sets. The structure that drops you a Big-O class for free. We've already used it in dedup and two-sum; tomorrow we go deep on the mechanics — collision handling, hash function quality, when 'O(1) average' isn't actually average.

See you in the morning.