Module 5.3 ⏱ 45 min read ⚡ System Design & Data Structures

Design Systems (LRU & LFU Caches)

Combine hash maps with doubly linked lists to achieve $O(1)$ constant time complexity for Least Recently Used (LRU) cache operations.

1. The Architecture of High-Performance Caches

Cache eviction policies such as LRU (Least Recently Used) require two fundamental capabilities: $O(1)$ key-value lookups and $O(1)$ recency re-ordering upon access or insertion. While a standard hash map provides instant $O(1)$ lookups, it cannot track chronological access order. Conversely, a linked list tracks order sequentially but requires $O(n)$ traversal to find or update items.

The Hybrid Solution: Pairing a hash map with a doubly linked list solves both constraints. The hash map stores keys mapped directly to their corresponding list node pointers, enabling instant access while the doubly linked list handles constant-time node promotion and eviction.

2. Implementing LRU Cache Mechanics

To ensure all operations execute in $O(1)$ time, boundary dummy head and tail nodes are maintained:

Get Operation: If the key exists in the hash map, fetch its node, promote it to the front (right after the head), and return its value. If missing, return -1.

Put Operation: If the key exists, update its value and promote it to the front. If it doesn't exist, create a new node and insert it at the front. If capacity is exceeded, evict the node immediately preceding the tail before adding the new entry.

// C++ Solution: LRU Cache (Hash Map + Doubly Linked List) #include <unordered_map> class LRUCache { private: struct Node { int key, val; Node* prev; Node* next; Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {} }; int capacity; std::unordered_map<int, Node*> map; Node* head; Node* tail; void addNode(Node* node) { Node* nextNode = head->next; head->next = node; node->prev = head; node->next = nextNode; nextNode->prev = node; } void removeNode(Node* node) { Node* prevNode = node->prev; Node* nextNode = node->next; prevNode->next = nextNode; nextNode->prev = prevNode; } void moveToHead(Node* node) { removeNode(node); addNode(node); } Node* popTail() { Node* res = tail->prev; removeNode(res); return res; } public: LRUCache(int cap) : capacity(cap) { head = new Node(0, 0); tail = new Node(0, 0); head->next = tail; tail->prev = head; } int get(int key) { if (map.find(key) == map.end()) return -1; Node* node = map[key]; moveToHead(node); return node->val; } void put(int key, int value) { if (map.find(key) != map.end()) { Node* node = map[key]; node->val = value; moveToHead(node); } else { if (map.size() >= capacity) { Node* lru = popTail(); map.erase(lru->key); delete lru; } Node* newNode = new Node(key, value); map[key] = newNode; addNode(newNode); } } };
# Python Solution: LRU Cache (Hash Map + Doubly Linked List) class Node: def __init__(self, key: int = 0, val: int = 0): 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() self.tail = Node() self.head.next = self.tail self.tail.prev = self.head def _add_node(self, node: Node) -> None: next_node = self.head.next self.head.next = node node.prev = self.head node.next = next_node next_node.prev = node def _remove_node(self, node: Node) -> None: prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node def _move_to_head(self, node: Node) -> None: self._remove_node(node) self._add_node(node) def _pop_tail(self) -> Node: res = self.tail.prev self._remove_node(res) return res def get(self, key: int) -> int: if key not_in self.cache: return -1 node = self.cache[key] self._move_to_head(node) return node.val def put(self, key: int, value: int) -> None: if key in self.cache: node = self.cache[key] node.val = value self._move_to_head(node) else: if len(self.cache) >= self.capacity: lru = self._pop_tail() del self.cache[lru.key] new_node = Node(key, value) self.cache[key] = new_node self._add_node(new_node)
// Java Solution: LRU Cache (Hash Map + Doubly Linked List) import java.util.HashMap; import java.util.Map; class LRUCache { class Node { int key, val; Node prev, next; Node(int k, int v) { key = k; val = v; } } private int capacity; private Map<Integer, Node> map; private Node head, tail; public LRUCache(int capacity) { this.capacity = capacity; map = new HashMap<>(); head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; } public int get(int key) { if (!map.containsKey(key)) return -1; Node node = map.get(key); moveToHead(node); return node.val; } public void put(int key, int value) { if (map.containsKey(key)) { Node node = map.get(key); node.val = value; moveToHead(node); } else { if (map.size() >= capacity) { Node lru = popTail(); map.remove(lru.key); } Node newNode = new Node(key, value); map.put(key, newNode); addNode(newNode); } } private void addNode(Node node) { Node nextNode = head.next; head.next = node; node.prev = head; node.next = nextNode; nextNode.prev = node; } private void removeNode(Node node) { Node prevNode = node.prev; Node nextNode = node.next; prevNode.next = nextNode; nextNode.prev = prevNode; } private void moveToHead(Node node) { removeNode(node); addNode(node); } private Node popTail() { Node res = tail.prev; removeNode(res); return res; } }

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for building a fully optimized LRU Cache with $O(1)$ operations.

Quick Check: Test Your Intuition

Why is a doubly linked list preferred over a singly linked list for implementing an LRU Cache?

← Previous: Module 5.2 Next: Module 5.4 →