Implementing LRU Cache
What you'll learn: You'll discover how to combine hash tables with doubly linked lists to build a Least Recently Used (LRU) cache that achieves blazing-fast O(1) operations.
The Problem
An LRU cache evicts the least recently used item when it reaches capacity. You need both fast lookups (get) and fast updates (put), plus a way to track which item was used longest ago.
Why Neither Structure Alone Works
A hash table gives O(1) lookups but can't efficiently track access order. A doubly linked list maintains order beautifully (most recent at head, least recent at tail) but requires O(n) to find items.
The Hybrid Solution
Combine both structures:
- Hash table: Maps keys to nodes in the linked list (O(1) lookup)
- Doubly linked list: Maintains access order (O(1) reordering)
How get(key) Works
- Hash table finds the node instantly
- Move that node to the list's head (it's now "most recently used")
- Return its value
Both steps are O(1) because doubly linked lists allow constant-time removal and insertion when you have the node reference.
How put(key, value) Works
- If key exists: update value, move node to head
- If key is new:
- Add to hash table and list head
- If cache is full, remove tail node from both list and hash table (it's the LRU item)
Analogy: Imagine a stack of papers on your desk. The hash table is your mental index ("The Smith report is 5 sheets down"), and the stack itself is your linked list. Every time you access a paper, you pull it out and put it on top. When the stack is too tall, you discard the bottom sheet.
Key Takeaway: LRU cache achieves O(1) get and put by using a hash table for fast key lookups and a doubly linked list for efficient order maintenance—each structure compensates for the other's weakness.