Footprints in both directions
Doubly Linked Lists
The analogy
Now each clue also says where you came from, so you can walk the hunt backwards. It costs a bit more paper on every clue, but you are never stuck facing one way.
Visualizer
Footprints in both directions
step 1 / 12head→4→8→15→16→null
Same list, but every node now also remembers where it came from. Two pointers per node instead of one.head ⇄ 4 ⇄ 8 ⇄ 15 ⇄ 16 ⇄ null
📖 In depth — the full reference
Singly vs doubly linked
| ability | singly | doubly | price of doubly |
|---|---|---|---|
| walk forward | O(1)/hop | O(1)/hop | — |
| walk backward | impossible without re-walking | O(1)/hop | one extra pointer per node |
| delete a node you HOLD | O(n) — must find its previous | O(1) — node.prev is right there | every insert must wire 4 pointers, not 2 |
| insert before a held node | O(n) | O(1) | same |
| memory per node | value + 1 pointer | value + 2 pointers | +8 bytes/node |
collections.deque — the doubly linked workhorse
| operation | cost | note |
|---|---|---|
| append(x) / appendleft(x) | O(1) | both ends are first-class |
| pop() / popleft() | O(1) | this is why BFS uses deque, never list.pop(0) |
| d[i] middle access | O(n) | it is a list of blocks, not an array |
| maxlen=k | auto-evicts | a rolling window in one argument |
| rotate(k) | O(k) | carousel behaviour for free |
See it yourself
from collections import deque
history = deque(maxlen=3) # a browser's back button
for page in ['a', 'b', 'c', 'd']:
history.append(page)
print(list(history)) # ['b', 'c', 'd'] — 'a' fell off
history.pop() # go back: O(1)
history.appendleft('start') # O(1) at the other end toodef remove(node):
node.prev.next = node.next
node.next.prev = node.prev
# O(1) — no search for a predecessor
from collections import deque
d = deque([4, 8, 15])
d.appendleft(1) # O(1) at BOTH ends
d.pop() # O(1)Check yourself
The extra prev pointer buys you…
Practice — write it yourself
count_nodes(head) walks a linked list ({"value", "next"} dicts) and returns how many nodes it has. No lists allowed — just the walk.
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser