Linked Lists as Treasure Hunts
A treasure hunt: the first clue tells you where the second clue is, the second points to the third. Nothing is numbered and nothing is in a row — to reach clue 5 you must physically follow clues 1 through 4. But slipping a new clue in is trivial: rewrite one clue to point at it.
Following the clues
step 1 / 18An empty list. No numbered slots — just clues waiting to point at each other.empty list
Array vs linked list — the whole trade in one table
| operation | array | linked list | who wins |
|---|---|---|---|
| read the i-th item | O(1) | O(n) — walk i hops | array |
| insert/delete at front | O(n) — shift all | O(1) — re-aim two pointers | list |
| insert after a node you HOLD | O(n) | O(1) | list |
| search by value | O(n) | O(n) | tie |
| memory per element | value only | value + next pointer (+prev if doubly) | array |
| cache friendliness | contiguous — prefetcher loves it | scattered — every hop may miss cache | array (often decisive in practice) |
The honest footnote
On modern hardware the cache line is so dominant that arrays beat linked lists even at some jobs the table awards to lists — the O(1) relink only wins if FINDING the spot was already free (you held a pointer). That is why real linked lists appear where handles are held for you: LRU caches, schedulers, undo chains, allocators.
Python specifics
- Python has no built-in singly linked list — you build nodes from a class (or dicts, as this exercise does), and that is deliberate: list covers most needs better.
- collections.deque IS the standard library's linked structure — a doubly linked list of 64-slot blocks: O(1) at both ends, O(n) in the middle.
- A node class is three lines: class Node: def __init__(self, value, next=None): self.value, self.next = value, next.
- Every node is a full Python object: ~56 bytes overhead per node vs 8 bytes per list slot — a 7× memory tax for the relink superpower.
class Node:
def __init__(self, value, nxt=None):
self.value, self.next = value, nxt
def insert_after(node, value):
node.next = Node(value, node.next)
return node.next
# two writes. nothing shifts.Inserting after a known node in a linked list costs…
A node is {"value": ..., "next": ...} and the list ends at next: None. list_to_array(head) follows the clues and returns the values in order.