Building an LRU cache

The LRU cache is the classic "combine two structures" question, and it is genuinely used everywhere: CPU caches, database buffer pools, CDN edges, HTTP client caches.

Requirement: get and put in O(1), evicting the least recently used entry when full.

Why one structure is not enough

• A hash map gives O(1) lookup but no notion of recency order.
• A doubly linked list maintains order and removes in O(1) — but finding a node in it is O(n).

Combine them: the map stores key → node, and the list stores recency. The map finds the node, the list moves it.

class LRUCache {
  #map = new Map();
  #head = { key: null, value: null };   // sentinels: most recent side
  #tail = { key: null, value: null };   // least recent side

  constructor(capacity) {
    this.capacity = capacity;
    this.#head.next = this.#tail;
    this.#tail.prev = this.#head;
  }

  #unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

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

  get(key) {
    const node = this.#map.get(key);
    if (!node) return undefined;

    this.#unlink(node);
    this.#pushFront(node);              // touched: now the most recent
    return node.value;
  }

  put(key, value) {
    const existing = this.#map.get(key);

    if (existing) {
      existing.value = value;
      this.#unlink(existing);
      this.#pushFront(existing);
      return;
    }

    if (this.#map.size === this.capacity) {
      const evict = this.#tail.prev;    // the least recently used
      this.#unlink(evict);
      this.#map.delete(evict.key);
    }

    const node = { key, value };
    this.#pushFront(node);
    this.#map.set(key, node);
  }
}

The details interviewers check

• Sentinels. With permanent head and tail nodes there are no null checks and no empty-list special case.
• The key on the node. Eviction starts from the list and must delete from the map — without node.key you cannot.
• get counts as a use. Forgetting to move the node on read is the most common bug.

The shortcut worth knowing

JavaScript's Map preserves insertion order, so a compact LRU is possible with delete then set to move a key to the end. It is fine for small caches and shows you know the language — but write the linked-list version when the question is about data structures, because that is what is being assessed.