Design an LRU Cache

The ask

A fixed-capacity cache with O(1) get(key) and put(key, value); when full, evict the least-recently-used entry.

The insight

You need two things in O(1): lookup by key and "move this to most-recent" / "find the least-recent". No single structure gives both, so combine:

• a hash map key → node for O(1) lookup, and
• a doubly linked list in recency order (head = most recent, tail = least), so moving a node or evicting the tail is O(1).

See it run

Step through the canonical trace below. Watch how get promotes a key to the front, and how a put into a full cache evicts the tail (the least-recently-used key). The map and the list highlight together — that pairing is the whole trick. Edit the capacity or the operations to test your own sequence.

Think it through like the interview

Don't memorize the structure — derive it. The derivation is reusable; the memorized answer dies on the first follow-up.

Implementation

class Node {
  constructor(
    public key: number,
    public val: number,
    public prev: Node | null = null,
    public next: Node | null = null,
  ) {}
}

class LRUCache {
  private map = new Map<number, Node>();
  private head = new Node(0, 0); // sentinel MRU side
  private tail = new Node(0, 0); // sentinel LRU side

  constructor(private capacity: number) {
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  private remove(n: Node) {
    n.prev!.next = n.next;
    n.next!.prev = n.prev;
  }
  private addFront(n: Node) {
    n.next = this.head.next;
    n.prev = this.head;
    this.head.next!.prev = n;
    this.head.next = n;
  }

  get(key: number): number {
    const n = this.map.get(key);
    if (!n) return -1;
    this.remove(n);
    this.addFront(n); // mark most-recently-used
    return n.val;
  }

  put(key: number, val: number): void {
    const existing = this.map.get(key);
    if (existing) { existing.val = val; this.remove(existing); this.addFront(existing); return; }
    if (this.map.size === this.capacity) {
      const lru = this.tail.prev!;       // evict least-recently-used
      this.remove(lru);
      this.map.delete(lru.key);
    }
    const n = new Node(key, val);
    this.addFront(n);
    this.map.set(key, n);
  }
}

Complexity & follow-ups

• Time: O(1) for both get and put. Space: O(capacity).
• Thread-safety: wrap operations in a lock, or use a concurrent structure; note the lock is the contention point at scale (shard the cache to reduce it).
• TTL: store an expiry per node and treat expired as a miss (lazy) + a sweeper.
• LFU instead of LRU: evict least-frequently-used — needs frequency buckets; more complex, better for skewed access.

Practice — level up

The whole skill here is pairing a hash map with a second structure to make every operation O(1). Climb this ladder and that move becomes automatic — every rung is the same idea under a new disguise.