LRU Cache

How an LRU cache works

Two data structures cooperating:

1. Hash map: key → linked list node. O(1) lookup.
2. Doubly linked list: ordered most-recently-used (head) to least-recently-used (tail). O(1) move-to-head and remove-tail.

Operations:

• get(key): hash-lookup. On hit, move the node to the head, return its value. On miss, return null.
• put(key, value): if key exists, update value, move node to head. Otherwise, if at capacity, remove tail (evict LRU). Insert new node at head and store in hash map.

Both operations are O(1) — no scans, no comparisons against other entries. The only catch is keeping the linked list and hash map synchronized; bugs in synchronization cause subtle leaks and incorrect evictions.

JavaScript implementation (using Map's insertion-order property)

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // Map preserves insertion order — front to back
  }

  get(key) {
    if (!this.map.has(key)) return undefined;
    // Move to "most recent" by deleting + re-setting
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key);
    } else if (this.map.size >= this.capacity) {
      // Evict the least recently used (front of insertion order)
      const oldestKey = this.map.keys().next().value;
      this.map.delete(oldestKey);
    }
    this.map.set(key, value);
  }
}

const cache = new LRUCache(3);
cache.put('a', 1);  // [a]
cache.put('b', 2);  // [a, b]
cache.put('c', 3);  // [a, b, c]
cache.get('a');     // [b, c, a]
cache.put('d', 4);  // [c, a, d] — b evicted
cache.get('b');     // undefined

Map's key order is insertion order — re-setting moves a key to the back. This makes the implementation 20 lines instead of 60. For very high-throughput cases (millions of ops/sec), an explicit linked list is slightly faster due to lower allocation overhead.

Explicit hash + doubly linked list

class Node {
  constructor(key, value) {
    this.key = key; this.value = value;
    this.prev = null; this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    // Sentinel nodes simplify edge cases (empty list, head/tail mutations)
    this.head = new Node(null, null);
    this.tail = new Node(null, null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _addToFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return undefined;
    this._remove(node);
    this._addToFront(node);
    return node.value;
  }

  put(key, value) {
    let node = this.map.get(key);
    if (node) {
      node.value = value;
      this._remove(node);
      this._addToFront(node);
      return;
    }
    if (this.map.size === this.capacity) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
    node = new Node(key, value);
    this._addToFront(node);
    this.map.set(key, node);
  }
}

Python implementation

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache: return None
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        elif len(self.cache) >= self.capacity:
            self.cache.popitem(last=False)  # evict oldest
        self.cache[key] = value

# Or use functools.lru_cache for memoization with LRU eviction:
from functools import lru_cache

@lru_cache(maxsize=128)
def expensive(x):
    # Compute something expensive
    return x * x

LRU variants and alternatives

Policy	Eviction rule	Best for
LRU	Least recently used	Workloads with temporal locality (default)
LFU	Least frequently used	Frequency-driven access patterns
FIFO	Oldest insertion (regardless of access)	Hardware-cheap, lower hit rate
Random	Random victim	Adversarial workloads, no locality
2Q	Two LRU lists — recent vs frequent	Scan-resistant; database buffer pools
ARC (Adaptive Replacement Cache)	Self-tuning between recency and frequency	Mixed workloads; ZFS, IBM DB2
CLOCK	Approximate LRU using a single bit per entry	OS page caches; cheaper than exact LRU
W-TinyLFU	Window-based frequency + admission control	Modern caches; Caffeine (Java), Ristretto (Go)

For new caches, W-TinyLFU is the modern best-in-class — better hit rate than LRU on most real workloads. ARC is patent-encumbered for some uses; CLOCK is the standard in OS kernels.

When LRU is the right choice

• Web browsers and CDN caches. Recent URLs are likely to be re-fetched. LRU works well.
• Database buffer pools. Recently-read pages are likely to be re-read. Many DBs use LRU variants (2Q, CLOCK, ARC).
• Function-result memoization. Python's @lru_cache, JS WeakMap-based memo wrappers — recent inputs are likely to recur.
• Object pools and connection pools. Reuse recently-released resources before allocating new ones.
• Image / asset caches in mobile apps. Recently-viewed images stay; old ones evict to make room.

Skip LRU when the workload has no temporal locality (random access patterns), when the eviction cost is high (each evicted page must be flushed to disk — write-back caches need careful policy), or when you can fit everything in memory (no eviction needed).

Common LRU bugs

• Hash map and linked list out of sync. Adding to one without the other corrupts the cache silently. Encapsulate both inside the cache class; never expose the internal data structures.
• Not moving on get. If get doesn't update the access order, the policy degenerates to FIFO. Always move-to-head on hit.
• Not handling capacity 0. A 0-capacity cache should never store anything; some implementations throw on put or silently never evict. Decide and document.
• Stale references after eviction. If callers hold references to evicted values, weak references or explicit invalidation are needed. In garbage-collected languages, holding strong references prevents memory release.
• Concurrent access without locking. Hash map + linked list mutations aren't atomic. Concurrent get + put can corrupt the structure. Use a lock per operation, a concurrent-safe library (Java ConcurrentLinkedHashMap, Caffeine), or a different policy that's easier to make concurrent.
• Pretending it's O(1) when it's not. Some implementations use a singly linked list, making move-to-head O(n) (must scan from head to find predecessor). Always use a doubly linked list, or pay the asymptotic cost.