Data Structures #3 — LRU Cache

An LRU (Least Recently Used) cache combines a hash map with a doubly linked list to achieve O(1) get and put, evicting the least recently accessed item when at capacity. It's one of the most practical data structures — used in browsers, databases, and CDNs.

Prerequisites: Data Structures #1 — Linked List, Data Structures #2 — Hash Table

1. The Key Insight — Two Data Structures Working Together

The hash map gives O(1) lookup by key. The doubly linked list maintains access order with O(1) move-to-front and remove-from-end. Together: O(1) for all operations.

Hash Map:                          Doubly Linked List:
{                                  HEAD (MRU)
  "a" → Node("a"),                  ↓
  "b" → Node("b"),                 Node("c")  ← most recently used
  "c" → Node("c"),                  ↓
}                                  Node("a")
                                    ↓
                                   Node("b")  ← least recently used
                                    ↓
                                   TAIL

2. Full LRU Cache Implementation

3. LRU Using JavaScript Map (Simplest Implementation)

Map iterates in insertion order — you can abuse this for an LRU in just a few lines:

4. Why Doubly Linked List + Hash Map?

Key Takeaways

• LRU = Hash Map (O(1) lookup) + Doubly Linked List (O(1) reorder + O(1) evict from end).
• Dummy head/tail nodes eliminate null-check edge cases.
• JavaScript's Map iterates in insertion order — you can build an LRU with just Map in ~15 lines.
• Use Map.keys().next().value to get the least recently used key in a Map-based LRU.
• LRU caches are everywhere: browser cache, database buffer pool, CDN edge caches, Redis eviction.

Next: Data Structures #4 — Binary Heap & Priority Queue — implement a min-heap and priority queue with O(log n) operations.