An LRU (Least Recently Used) cache is a memory management strategy that evicts the least recently accessed item when storage is full. The challenge is achieving O(1) time complexity for both lookups and updates.
A hash map gives us O(1) lookups but doesn't track access order. A linked list tracks order but requires O(n) time to find specific elements. The solution is combining both structures.
The key insight is using a doubly linked list to maintain access order, while a hash map provides direct node access. The hash map stores key -> node mappings, where each node contains the actual key-value pair plus prev/next pointers.
When an item is accessed:
When adding new items at capacity:
Singly linked lists require O(n) time to remove arbitrary nodes because you need the previous node. Doubly linked lists store both directions, enabling O(1) removal from anywhere in the list.
The elegant approach uses dummy head/tail nodes to eliminate edge cases. Instead of checking "is this the first/last node?", you always insert after head and remove before tail. This simplifies the logic significantly.
1class Node:
2 def __init__(self, key, value):
3 self.key = key
4 self.value = value
5 self.prev = None
6 self.next = None
7
8class SimpleCache:
9 def __init__(self):
10 self.cache = {} # key -> node mapping
11 # Dummy nodes eliminate edge cases
12 self.head = Node(None, None)
13 self.tail = Node(None, None)
14 self.head.next = self.tail
15 self.tail.prev = self.head
16
17 def move_to_front(self, node):
18 # Remove from current position
19 node.prev.next = node.next
20 node.next.prev = node.prev
21
22 # Insert after head
23 node.next = self.head.next
24 node.prev = self.head
25 self.head.next.prev = node
26 self.head.next = node