Building an LRU Cache from Scratch

The LRU cache is a classic interview question because it tests two data structures at once: a hash map for O(1) lookups and a doubly linked list for O(1) insertion and removal at either end. Together they give O(1) get and set with LRU eviction. The hash map stores key → node references. The doubly linked list maintains access order: the head is the most recently used entry, the tail is the least recently used. On get, move the node to the head. On set, if at capacity, remove the tail node and delete its key from the map. JavaScript's Map preserves insertion order and supports delete + re-insert to simulate "move to end," which is why the simplified version in the previous lesson works — but the hash map + doubly linked list version is what interviewers and production libraries (like Python's functools.lru_cache) implement under the hood.

Before

Naive approach — scan all entries to find LRU

// O(n) eviction — too slow at scale
function evictLRU(cache) {
  let oldest = null, oldestTime = Infinity;
  for (const [key, entry] of cache) {
    if (entry.lastAccessed < oldestTime) {
      oldestTime = entry.lastAccessed;
      oldest = key;
    }
  }
  cache.delete(oldest);
}

After

O(1) eviction — hash map + doubly linked list

class LRUNode {
  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();
    this.head = new LRUNode(0, 0);
    this.tail = new LRUNode(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

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

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

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._addToHead(node);
    return node.value;
  }

  set(key, value) {
    if (this.map.has(key)) {
      this._remove(this.map.get(key));
    } else if (this.map.size >= this.capacity) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
    const node = new LRUNode(key, value);
    this._addToHead(node);
    this.map.set(key, node);
  }
}

Key Takeaway

Hash map for O(1) lookup + doubly linked list for O(1) reordering — the standard LRU implementation in interviews and production.