Day 9: Doubly Linked List | Bidirectional Traversal & O(1) Deletions
Two-way pointers, O(1) node deletion, and how browser history really works.
Day 9: Doubly Linked List Explained Simply
What happens when a one-way street turns into a two-way highway—and why do your browser's Back and Forward buttons depend on it?
In 30 Seconds
A Doubly Linked List is an upgraded linked list where every node carries two pointers instead of one: a next pointer aiming forward to the following node, and a prev pointer [a reference pointing backward to the preceding node]. Because every node knows both its neighbors, you can walk forward from the head or backward from the tail [the pointer tracking the very last node]. You trade a tiny bit of extra memory per node for effortless two-way navigation and instant deletions.
The Real-World Analogy: Coupled Train Cars
Imagine a passenger train sitting on the tracks where every train car is linked to the car in front of it and the car behind it with heavy steel couplers.
- If you are standing in Car 3, you can walk forward into Car 4 or step backward into Car 2.
- The locomotive at the front is the Head, and the caboose at the rear is the Tail.
- If workers need to unhook Car 3 for repairs, they don't have to walk all the way from the locomotive to figure out which car sits ahead of Car 3; Car 3 is already directly coupled to both Car 2 and Car 4!
Picture This
Here is the anatomy of a 3-node Doubly Linked List with head and tail pointers and bidirectional arrows:
HEAD TAIL
| |
v v
+------+----+------+ +------+----+------+ +------+----+------+
| None | 10 | *---+---->| * | 20 | *---+---->| * | 30 | None |
+------+----+------+ +--+---+----+------+ +--+---+----+------+
prev data next | |
+---> points back to 10 +---> points back to 20
And here is what happens when you delete the middle node (20) directly:
Before: [10] <===> [20] <===> [30]
Step 1: node_20.prev.next = node_20.next (10's next skips over 20 to 30)
Step 2: node_20.next.prev = node_20.prev (30's prev skips over 20 to 10)
After: [10] <==============> [30] (Node 20 is cleanly detached!)
How It Actually Works
- Upgrade the Node Structure: Give each
Nodethree fields:data,prev(defaultNone), andnext(defaultNone). - Maintain Both Ends: Keep both a
headpointer (front) and atailpointer (end) so appending items takes $O(1)$ instant time. - Wire Two Links on Insertion: Update four pointers when inserting between
AandB:new.prev = A,new.next = B,A.next = new, andB.prev = new. - Delete Without Searching Backward ($O(1)$): Given a direct reference to any node
X, stitchX.prevdirectly toX.nextwithout traversing from the start.
Show Me The Code
# Day 9: Doubly Linked List Implemented from Scratch in Python
class DNode:
def __init__(self, data):
self.data = data
self.prev = None # Points to the previous node
self.next = None # Points to the next node
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def append(self, data):
"""Adds a new node to the end (tail) in O(1) constant time."""
new_node = DNode(data)
if self.head is None:
self.head = self.tail = new_node
return
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def delete_node(self, node):
"""Removes a specific node reference in O(1) time without searching."""
if node is None:
return
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev
def print_forward(self):
vals = []
curr = self.head
while curr:
vals.append(str(curr.data))
curr = curr.next
print("Forward: " + " <-> ".join(vals))
def print_backward(self):
vals = []
curr = self.tail
while curr:
vals.append(str(curr.data))
curr = curr.prev
print("Backward: " + " <-> ".join(vals))
if __name__ == "__main__":
dll = DoublyLinkedList()
dll.append("Page A")
dll.append("Page B")
dll.append("Page C")
dll.print_forward() # Output: Forward: Page A <-> Page B <-> Page C
dll.print_backward() # Output: Backward: Page C <-> Page B <-> Page A
Dry Run
| Step | Action Taken | Current Data Structure State | Pointer Status |
|---|---|---|---|
| 1 | Create new_node = DNode("Page B") | ["Page A"], ["Page B"] | head = A, tail = A |
| 2 | Set new_node.prev = self.tail | ["Page A"] <--- ["Page B"] | B.prev points to A |
| 3 | Set self.tail.next = new_node | ["Page A"] <---> ["Page B"] | A.next points to B |
| 4 | Update self.tail = new_node | head -> ["Page A"] <---> ["Page B"] <- tail | Both ends updated! |
Speed & Memory
| Operation | Best Case | Average Case | Worst Case | Why? |
|---|---|---|---|---|
| Search by Value | $O(1)$ | $O(N)$ | $O(N)$ | Still must scan node by node from head or tail. |
| Insert at Head / Tail | $O(1)$ | $O(1)$ | $O(1)$ | Direct access via head and tail pointers. |
| Delete Known Node | $O(1)$ | $O(1)$ | $O(1)$ | node.prev gives instant access to the preceding node. |
Where You'll See It In Real Life
- Web Browser History: Clicking Back follows
current.prev, and Forward followscurrent.next. - Music & Video Playlists: Media players use doubly linked lists for Previous/Next track navigation and drag-and-drop reordering.
- LRU Cache Eviction Engines: High-speed caches pair a hash map with a doubly linked list to evict the oldest item in $O(1)$ time.
Traps To Avoid
- Trap 1: Updating only
nextpointers and forgettingprevpointers.
Fix: Always treat links as pairs; ifA.next = B, setB.prev = A. - Trap 2: Crashing when deleting the
headortailnode.
Fix: Checkif node.prev is Noneandif node.next is Nonebefore dereferencing neighbors. - Trap 3: Leaving dangling references on deleted nodes.
Fix: Setnode.prev = Noneandnode.next = Noneupon removal.
Practice
- Easy: Add an
insert_at_front(data)method toDoublyLinkedList. - Medium: Write a method
reverse()that reverses a doubly linked list in-place by swappingprevandnextpointers. - Hard: Design a browser history tracker class supporting
visit(url),back(steps), andforward(steps).
TL;DR
- Doubly Linked Lists give every node both a
nextand aprevpointer for two-way traversal. - Keeping a
tailpointer makes insertions at both ends $O(1)$, and knowing a node lets you delete it in $O(1)$. - You trade a small amount of extra memory per node for huge flexibility in navigation and cache design.
References Consulted
- GeeksforGeeks - Doubly Linked List Tutorial — referenced for verification — all content above is original.
- Programiz - Types of Linked List — referenced for verification — all content above is original.
Covered Log Update
Already covered: [Big-O notation, Arrays, Two Pointers, Strings, Sliding Window, Prefix Sums, Recursion basics, Singly Linked List, Doubly Linked List]