LRU Cache

A Least Recently Used (LRU) cache evicts the item that was accessed least recently when the cache is full. LRU is used everywhere: CPU caches, browser page caches, database buffer pools, and CDN edge nodes. It is also one of the most popular system-design interview questions.

The Core Insight

Map iterates in insertion order. When you delete a key and immediately set it again, it moves to the end of the iteration order. That means the first key in the Map is always the least recently used — the one to evict.

This gives us O(1) get and put without a single pointer or custom node.

Implementation

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // key → value, insertion order = recency
  }

  get(key) {
    if (!this.cache.has(key)) return -1;

    // Move to end (most recently used)
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key); // remove so re-insert goes to end
    } else if (this.cache.size >= this.capacity) {
      // Evict least recently used — first key in the Map
      const lruKey = this.cache.keys().next().value;
      this.cache.delete(lruKey);
    }
    this.cache.set(key, value);
  }
}

Walkthrough

const lru = new LRUCache(3);

lru.put(1, "one");   // cache: {1}
lru.put(2, "two");   // cache: {1, 2}
lru.put(3, "three"); // cache: {1, 2, 3}

lru.get(1);          // returns "one", cache: {2, 3, 1}  — 1 moved to end
lru.put(4, "four");  // capacity exceeded; evict 2 (LRU), cache: {3, 1, 4}

console.log(lru.get(2)); // -1 — evicted
console.log(lru.get(3)); // "three"
console.log(lru.get(1)); // "one"
console.log(lru.get(4)); // "four"

Complexity

Both operations are O(1) because Map.delete and Map.set are O(1), and Map.keys().next() retrieves the first key in O(1).

Why the Textbook Solution Uses a Doubly Linked List

The Map-only approach works in JavaScript because the spec mandates insertion-order iteration. In languages without this guarantee (older Java HashMap, C++ unordered_map) you cannot rely on it. The canonical solution uses a doubly linked list to maintain recency order, with a HashMap pointing to each node for O(1) access. This is exactly how java.util.LinkedHashMap is implemented internally.

You will build the doubly linked list version in the linked lists track, which gives you full control and deepens your understanding of pointer manipulation.

A Note on Production Use

For real applications prefer a battle-tested library such as lru-cache on npm or the platform’s built-in (e.g., Redis MAXMEMORY allkeys-lru). The implementation above is for learning — it lacks TTL expiry, thread safety, and serialisation.

Up Next

Learn how doubly linked lists work and build the textbook LRU cache variant that does not depend on language-specific map ordering.