Back
+30 XP
Concept

Least Recently Used (LRU) Cache from Scratch

Unbounded in-memory caches cause catastrophic out-of-memory crashes. A production Least Recently Used (LRU) cache couples a hash map for $O(1)$ key lookups with a doubly linked list for $O(1)$ recency tracking, evicting the oldest unaccessed node when hitting capacity bounds 🧠🧱⚡.

python
class LRUNode:
    def __init__(self, k, v):
        self.k, self.v = k, v
        self.prev = self.next = None

class MiniLRU:
    def __init__(self, cap=2):
        self.cap = cap
        self.map = {}
        self.head, self.tail = LRUNode(0, 0), LRUNode(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

cache = MiniLRU(2)
print(f"LRU Initialized with capacity {cache.cap} 🚀")

# 16. Least Recently Used (LRU) Cache from Scratch Storing calculation results or database records in an unbounded dictionary is the primary cause of out-of-memory (OOM) fatal crashes. When your app serves 100,000 users, an unconstrained cache grows until the Linux kernel terminates the process 🛑. ```python # The Dual Data Structure Invariant: # 1. Hash Map: Provides O(1) key-to-node pointer lookup. # 2. Doubly Linked List: Provides O(1) node reordering and tail eviction. # # [Head (Dummy)] <-> [Most Recent] <-> ... <-> [Least Recent] <-> [Tail (Dummy)] ``` ### The $O(1)$ Mechanics - **On `get(key)`**: Find node via hash map. Unlink it from its current position and prepend it directly after `head`. Return the value. - **On `put(key, val)`**: If key exists, update value and move to front. If new and capacity is breached, remove `tail.prev`, delete its key from the hash map, and insert the new item at the front. - Every operation runs in pure **$O(1)$ constant time** 🧠🧱⚡. --- ### Interactive Pop-Quiz 🧠 #### Why does an LRU cache require a doubly linked list rather than a single linked list to achieve true $O(1)$ eviction? - [ ] A doubly linked list allows removing a node in $O(1)$ time because the node directly references its predecessor (`node.prev`) 🏎️ - [ ] A single linked list cannot store string keys in Python - [ ] Doubly linked lists automatically compress data with zlib - [ ] Single linked lists cause the operating system kernel to freeze --- ### Practical Challenge 🎯 Implement `LRUCache(capacity: int)` from scratch without using `collections.OrderedDict`. Implement `get(key: str) -> int` (returning -1 on misses, moving accessed nodes to front) and `put(key: str, val: int)` (updating existing or evicting least recently used node from tail). Instantiate with capacity 2, put 'a'=1, put 'b'=2, access 'a', put 'c'=3 (evicting 'b'), assert 'b' is -1 and 'a' and 'c' are present. Print results. <details> <summary>Solution</summary> ```python class Node: def __init__(self, key: str, val: int): self.key = key self.val = val self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} self.head = Node("", 0) self.tail = Node("", 0) self.head.next = self.tail self.tail.prev = self.head def _remove(self, node: Node): p, n = node.prev, node.next p.next = n n.prev = p def _add_to_front(self, node: Node): node.next = self.head.next node.prev = self.head self.head.next.prev = node self.head.next = node def get(self, key: str) -> int: if key not in self.cache: return -1 node = self.cache[key] self._remove(node) self._add_to_front(node) return node.val def put(self, key: str, val: int): if key in self.cache: node = self.cache[key] node.val = val self._remove(node) self._add_to_front(node) else: if len(self.cache) >= self.capacity: lru = self.tail.prev self._remove(lru) del self.cache[lru.key] new_node = Node(key, val) self.cache[key] = new_node self._add_to_front(new_node) lru = LRUCache(2) lru.put("a", 1) lru.put("b", 2) assert lru.get("a") == 1 lru.put("c", 3) # Evicts 'b' assert lru.get("b") == -1 assert lru.get("c") == 3 assert lru.get("a") == 1 print("LRUCache verified: 'b' evicted, 'a' and 'c' preserved") ``` </details>

Checkpoint

Why does an LRU cache require a doubly linked list rather than a single linked list to achieve true $O(1)$ eviction? 🧠

Practice

Implement `LRUCache(capacity: int)` from scratch without using `collections.OrderedDict`. Implement `get(key: str) -> int` (returning -1 on misses, moving accessed nodes to front) and `put(key: str, val: int)` (updating existing or evicting least recently used node from tail). Instantiate with capacity 2, put 'a'=1, put 'b'=2, access 'a', put 'c'=3 (evicting 'b'), assert 'b' is -1 and 'a' and 'c' are present. Print results. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks