DSA course menu
Doubly Linked Lists in Python (With an LRU Cache Example)
Learn doubly linked lists: nodes with next and prev pointers, sentinel nodes, O(1) removal of any node, and building an LRU cache with a doubly linked list and a dictionary.
On this page
In a doubly linked list, each node points to both its next and its previous node. That one extra pointer lets you walk backwards and, more importantly, remove any node in O(1) when you have a reference to it, because the node knows its own neighbours.
None ◀──[ prev | 3 | next ]◀──▶[ prev | 7 | next ]◀──▶[ prev | 1 | next ]──▶ NoneSentinel nodes remove the edge cases#
Most linked list bugs happen at the ends. A common trick is two sentinel (dummy) nodes, head and tail, that are always present. Real items live between them, so every insert and delete has a node on both sides and needs no if for the empty case.
class Node:
def __init__(self, value=None):
self.value = value
self.prev = self.next = None
class DoublyLinkedList:
def __init__(self):
self.head, self.tail = Node(), Node() # sentinels
self.head.next, self.tail.prev = self.tail, self.head
self.size = 0
def _insert_between(self, node, before, after):
node.prev, node.next = before, after
before.next = after.prev = node
self.size += 1
return node
def push_front(self, value):
return self._insert_between(Node(value), self.head, self.head.next)
def push_back(self, value):
return self._insert_between(Node(value), self.tail.prev, self.tail)
def remove(self, node): # O(1)
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1
return node.value
def values(self):
out, node = [], self.head.next
while node is not self.tail:
out.append(node.value)
node = node.next
return out
def values_backward(self):
out, node = [], self.tail.prev
while node is not self.head:
out.append(node.value)
node = node.prev
return out
d = DoublyLinkedList()
a = d.push_back("A")
b = d.push_back("B")
d.push_back("C")
d.push_front("Z")
print(d.values(), d.values_backward())
d.remove(b) # O(1): we already hold the node
print(d.values(), "size", d.size)['Z', 'A', 'B', 'C'] ['C', 'B', 'A', 'Z']
['Z', 'A', 'C'] size 3Building an LRU cache#
A least recently used (LRU) cache keeps at most capacity items. When it is full and a new item arrives, it throws away the item that was used longest ago. Both get and put must be O(1).
The classic design combines two structures:
- a dictionary from key to node, for O(1) lookup;
- a doubly linked list ordered by use: most recent at the front, least recent at the back. Moving a node to the front, or removing the back node, is O(1).
class Node:
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.nodes = {}
self.head, self.tail = Node(), Node()
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.nodes:
return None
node = self.nodes[key]
self._unlink(node) # mark as most recently used
self._push_front(node)
return node.value
def put(self, key, value):
if key in self.nodes:
self._unlink(self.nodes[key])
node = Node(key, value)
self.nodes[key] = node
self._push_front(node)
if len(self.nodes) > self.capacity:
oldest = self.tail.prev # least recently used
self._unlink(oldest)
del self.nodes[oldest.key]
print("evicted", oldest.key)
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
print(cache.get("a")) # "a" is now the most recent
cache.put("c", 3) # full: evicts "b", the least recent
print(cache.get("b"), cache.get("c"))1
evicted b
None 3Singly or doubly linked?#
Common mistakes#
Practice#
Practice exercise
Add a pop_back() method to DoublyLinkedList that removes and returns the last value, or None if the list is empty. It must be O(1).
Show hint
With sentinels, the last real node is self.tail.prev. The list is empty when that node is self.head.
Show solution
class Node:
def __init__(self, value=None):
self.value = value
self.prev = self.next = None
class DoublyLinkedList:
def __init__(self):
self.head, self.tail = Node(), Node()
self.head.next, self.tail.prev = self.tail, self.head
def push_back(self, value):
node = Node(value)
node.prev, node.next = self.tail.prev, self.tail
self.tail.prev.next = node
self.tail.prev = node
def pop_back(self):
last = self.tail.prev
if last is self.head:
return None
last.prev.next = self.tail
self.tail.prev = last.prev
return last.value
d = DoublyLinkedList()
for v in [1, 2, 3]:
d.push_back(v)
print(d.pop_back(), d.pop_back(), d.pop_back(), d.pop_back())3 2 1 NoneKey takeaway#
Next: the problems interviewers love, Linked List Problems.
Finished this lesson?