Doubly Linked List
Learn how doubly linked lists add backward pointers to enable traversal in both directions.
Doubly Linked List
A doubly linked list gives each node two pointers — next pointing forward and prev pointing backward. This enables traversal in both directions and makes certain operations faster — particularly deleting a known node.
None ← [10] ⇄ [20] ⇄ [30] ⇄ [40] ⇄ [50] → None
↑ ↑
head tailThe node
class Node:
def __init__(self, value):
self.value = value
self.next = None # forward pointer
self.prev = None # backward pointerFull implementation
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def append(self, value):
"""Add to the end — O(1) with tail pointer"""
new_node = Node(value)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self.size += 1
def prepend(self, value):
"""Add to the beginning — O(1)"""
new_node = Node(value)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.size += 1
def delete_node(self, node):
"""Delete a specific node — O(1) if node is known"""
if node.prev:
node.prev.next = node.next
else:
self.head = node.next # deleting head
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev # deleting tail
self.size -= 1
def delete_head(self):
"""Remove from beginning — O(1)"""
if not self.head:
return None
value = self.head.value
self.delete_node(self.head)
return value
def delete_tail(self):
"""Remove from end — O(1) with tail pointer"""
if not self.tail:
return None
value = self.tail.value
self.delete_node(self.tail)
return value
def traverse_forward(self):
result = []
current = self.head
while current:
result.append(current.value)
current = current.next
return result
def traverse_backward(self):
result = []
current = self.tail
while current:
result.append(current.value)
current = current.prev
return resultThe key advantage — O(1) delete of a known node
In a singly linked list, to delete a node you need a reference to the node before it. That means walking from the head — O(n).
In a doubly linked list, every node knows its own previous node. So if you have a reference to the node, you can delete it in O(1):
# singly linked — need to find the previous node first — O(n)
def delete(self, target_node):
current = self.head
while current.next != target_node:
current = current.next
current.next = target_node.next # bypass target
# doubly linked — node knows its own prev — O(1)
def delete_node(self, node):
node.prev.next = node.next
node.next.prev = node.prevThis is why LRU cache is implemented with a doubly linked list — we need to delete arbitrary nodes instantly.
Real use case — LRU Cache
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict() # doubly linked + hash map
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # remove least recently usedPython's OrderedDict is a doubly linked list with a hash map on top. move_to_end() is O(1) because of the prev pointer. Without it, moving a node to the end would require O(n) traversal.
Singly vs Doubly — comparison
| Singly | Doubly | |
|---|---|---|
| Memory per node | One pointer | Two pointers |
| Traversal direction | Forward only | Both directions |
| Delete known node | O(n) | O(1) |
| Append with tail pointer | O(1) | O(1) |
| Delete tail | O(n) | O(1) |
| Use case | Simple lists, stacks | LRU cache, browser history |
Complexity
| Operation | Time | Space |
|---|---|---|
| Prepend | O(1) | O(1) |
| Append (with tail) | O(1) | O(1) |
| Delete head | O(1) | O(1) |
| Delete tail | O(1) | O(1) |
| Delete known node | O(1) | O(1) |
| Search | O(n) | O(1) |
| Traverse | O(n) | O(1) |