Doubly Linked Lists
Linked Lists: lesson 10 of 10
Add a backwards pointer and removal stops needing a search.
Lesson 10 of 10 · 6 min
Doubly Linked Lists
Step 1 of 6
targetunlink b
sentinel
head•
·
c•
·
b•
·
a•
sentinel
tail•
Two sentinels and three values. Every node holds a next (above) and a prev (below).
The Idea
A prev field costs one pointer per node and changes what is cheap. Given a node, both of its neighbours are in hand, so unlinking is two assignments and no walking.
Two sentinel nodes — a permanent head and tail that hold no data — mean every node always has neighbours, so the edge cases vanish.
Real-World Example
Carriages in a train, each coupled to the one ahead and the one behind. Pulling a carriage out of the middle is a job for the two couplings either side of it; nobody walks to the engine first.
The Code
class Node:
def __init__(self, v): self.val, self.prev, self.next = v, None, None
def unlink(n): # O(1): both neighbours are already in hand
n.prev.next, n.next.prev = n.next, n.prev
n.prev = n.next = None
def insert_after(at, n):
n.prev, n.next = at, at.next
at.next.prev, at.next = n, n
head, tail = Node("head"), Node("tail") # sentinels: no None checks anywhere
head.next, tail.prev = tail, head
for v in "abc": insert_after(head, Node(v)) # each one lands at the front
unlink(head.next.next) # drop the middle node
n, out = head.next, []
while n is not tail: out.append(n.val); n = n.next
print(out) # ['c', 'a']Your turn
What does this print?
class Node:
def __init__(self, v): self.val, self.prev, self.next = v, None, None
x, y, z = Node("x"), Node("y"), Node("z")
x.next, y.prev, y.next, z.prev = y, x, z, y
y.prev.next, y.next.prev = y.next, y.prev
out, n = [], x
while n: out.append(n.val); n = n.next
print(out)Mini quiz
1 / 3