Walkthrough: Design an LRU Cache

Why one data structure isn't enough

An LRU cache needs two things in O(1): look up a key, and know which entry was used least recently. A HashMap gives O(1) lookup but no ordering. A list gives ordering but O(n) lookup. Neither alone works — so we combine them.

interface Cache<K, V> {
  V get(K key);              // O(1), marks key as most-recently-used
  void put(K key, V val);    // O(1), evicts least-recently-used when full
}

The whole trick is recognising that "most recently used" is an ordering requirement and "get by key" is a lookup requirement, and no single container does both in O(1).

<!--STEP-->

HashMap + doubly linked list

Keep a HashMap from key → node, plus a doubly linked list ordering nodes from most- to least-recently-used. The map finds a node in O(1); the list lets us move or drop it in O(1).

class Node { int key, val; Node prev, next; Node(int k, int v) { key = k; val = v; } }

private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0), tail = new Node(0, 0);  // sentinels
private final int capacity;

LruCache(int capacity) {
  this.capacity = capacity;
  head.next = tail; tail.prev = head;      // head = most recent, tail = least recent
}

private void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
private void addFront(Node n) {
  n.next = head.next; n.prev = head;
  head.next.prev = n; head.next = n;
}

The list is doubly linked for a reason: to unlink a node in O(1) you must reach its predecessor instantly. A singly linked list would force an O(n) scan to find prev. Sentinel head/tail nodes remove every null-pointer edge case.

<!--STEP-->

get: fetch, then promote

public int get(int key) {
  Node n = map.get(key);
  if (n == null) return -1;
  remove(n);        // unlink from current position
  addFront(n);      // reinsert as most-recently-used
  return n.val;
}

A hit isn't just a read — it's a usage event. Touching a key makes it the most recently used, so we splice its node to the front. Because both remove and addFront are pointer swaps, the whole promotion is O(1).

<!--STEP-->

put: upsert, then evict the tail

public void put(int key, int val) {
  Node n = map.get(key);
  if (n != null) { n.val = val; remove(n); addFront(n); return; }
  if (map.size() == capacity) {          // full → drop least recent
    Node lru = tail.prev;
    remove(lru);
    map.remove(lru.key);
  }
  Node fresh = new Node(key, val);
  map.put(key, fresh);
  addFront(fresh);
}

Eviction always targets tail.prev — the node just before the tail sentinel — because that is, by construction, the least-recently-used entry. It must be removed from both the list and the map, or the map leaks a dangling key.

<!--STEP-->

Trade-offs and the shortcut

The hand-rolled map+list is what interviewers want to see. In production you'd often reach for LinkedHashMap in access-order — the same idea, packaged:

class LruCache<K, V> extends LinkedHashMap<K, V> {
  private final int cap;
  LruCache(int cap) { super(16, 0.75f, true /* accessOrder */); this.cap = cap; }
  protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > cap; }
}

Neither version is thread-safe. Under concurrency you'd wrap operations in a lock or shard the cache — but a single global lock serialises every get, so high-read workloads favour sharding.

Practice it for real: the LRU Cache problem in the ladder checks these exact get/put/eviction behaviours against hidden tests.