Intermediate·1 min read
Doubly Linked Lists
Extend linked lists with bidirectional traversal and O(1) deletion.
Doubly Linked Lists
Each node has two pointers: prev and next.
``
NULL ← [Prev|Data|Next] ⇄ [Prev|Data|Next] ⇄ [Prev|Data|Next] → NULL
Node 1 Node 2 Node 3
``Advantages over Singly Linked List
- Bidirectional traversal - go forward and backward
- O(1) deletion if you have the node reference (no need to find prev)
- Easier deletion of the last node
Trade-off
- Extra memory: One pointer per node (prev)
- Slightly more complex insertion (update 4 pointers vs 2)
When to Use
- Browser forward/back navigation
- LRU Cache implementation
- Music playlist (next/previous song)
- Text editor undo/redo
Code Example
python
class DNode:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def push_back(self, data):
node = DNode(data)
if not self.head:
self.head = self.tail = node
return
node.prev = self.tail
self.tail.next = node
self.tail = node
def push_front(self, data):
node = DNode(data)
if not self.head:
self.head = self.tail = node
return
node.next = self.head
self.head.prev = node
self.head = node
def delete_node(self, node):
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 display_forward(self):
elements, curr = [], self.head
while curr:
elements.append(str(curr.data))
curr = curr.next
return "NULL ⇄ " + " ⇄ ".join(elements) + " ⇄ NULL"
def display_backward(self):
elements, curr = [], self.tail
while curr:
elements.append(str(curr.data))
curr = curr.prev
return "NULL ⇄ " + " ⇄ ".join(elements) + " ⇄ NULL"
dll = DoublyLinkedList()
for v in [1, 2, 3, 4, 5]:
dll.push_back(v)
print(dll.display_forward())
print(dll.display_backward())Practice Problems
- 01Implement a browser history system using a doubly linked list
- 02Flatten a multilevel doubly linked list
- 03Reverse a doubly linked list in groups of k