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
def 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…