Doubly Linked List
DSA · Linked Lists
Theory
In a doubly linked list each node has pointers to both the next and the previous node. This allows traversal in both directions and O(1) deletion of a node when you hold a reference to it, because you can reach its predecessor directly. It uses more memory per node and requires updating two pointers on every change.
Why we use it
It supports fast removal from anywhere and bidirectional movement, which is why browser history and LRU caches use it.
When to use it
Use it for LRU caches, browser back/forward navigation, music playlists, and deques.
How it works
- head <-> node <-> node <-> tail
- Each node stores prev, data and next
- Insert: link new node to both neighbours
- Delete: neighbours point to each other
- Traverse forwards or backwards
Syntax
class DNode:
def __init__(self, v): self.val = v; self.prev = None; self.next = None
Remove node n:
n.prev.next = n.next
n.next.prev = n.prev # O(1)Example
class DNode:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
head = DNode("Home")
about = DNode("About")
blog = DNode("Blog")
head.next, about.prev = about, head
about.next, blog.prev = blog, about
page = blog
print("Current page:", page.val)
page = page.prev
print("Back:", page.val)
page = page.next
print("Forward:", page.val)
about.prev.next = about.next # remove About in O(1)
about.next.prev = about.prev
print("After removal, Home.next =", head.next.val)Key points
- Pointers in both directions
- O(1) removal given the node
- More memory per node
- Backbone of LRU caches