How do LRU and LFU eviction policies actually work, and when would you pick one over the other?

#Why Eviction Policies Exist at All

A cache is finite by definition — that's what makes it fast, and it's also what forces a decision the moment it fills up: when a new entry needs room, which existing entry gets thrown away? Get the answer right and the cache keeps absorbing most of your traffic; get it wrong and you're paying the memory cost of caching without getting the hit-rate benefit, because you keep evicting things right before they were about to be reused. LRU and LFU are the two policies that come up constantly in interviews, and they optimize for two genuinely different signals.

#LRU: Least Recently Used

LRU's bet is on recency: whatever was touched most recently is the most likely thing to be touched again soon (this is "temporal locality," and it holds surprisingly often for real workloads — a user browsing a product page is likely to hit related pages in the next few seconds, not five hours later). The classic implementation pairs a hash map (for O(1) lookup) with a doubly linked list (to track recency order): the front of the list is the most recently used item, the back is the least recently used, and every access moves that item to the front. When the cache is full, the item at the back gets evicted — no scanning required, because it's already sitting at the exact spot that needs to be removed.

class DLLNode<K, V> {
  key: K;
  value: V;
  prev: DLLNode<K, V> | null = null;
  next: DLLNode<K, V> | null = null;

  constructor(key: K, value: V) {
    this.key = key;
    this.value = value;
  }
}

class LRUCache<K, V> {
  private capacity: number;
  private map = new Map<K, DLLNode<K, V>>();
  // Sentinel nodes: head.next is the most recently used entry,
  // tail.prev is the least recently used entry.
  private head = new DLLNode<K, V>(null as unknown as K, null as unknown as V);
  private tail = new DLLNode<K, V>(null as unknown as K, null as unknown as V);

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

  private detach(node: DLLNode<K, V>): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private attachToFront(node: DLLNode<K, V>): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }

  get(key: K): V | undefined {
    const node = this.map.get(key);
    if (!node) return undefined;

    this.detach(node);
    this.attachToFront(node);
    return node.value;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.detach(existing);
      this.attachToFront(existing);
      return;
    }

    if (this.map.size >= this.capacity) {
      const leastRecentlyUsed = this.tail.prev!;
      this.detach(leastRecentlyUsed);
      this.map.delete(leastRecentlyUsed.key);
    }

    const node = new DLLNode(key, value);
    this.map.set(key, node);
    this.attachToFront(node);
  }
}

Both get and put are O(1): the map gives instant access to the node, and detaching/re-attaching a node in a doubly linked list is a fixed number of pointer updates regardless of list size — no shifting, no scanning.

#LFU: Least Frequently Used

LFU bets on a different signal: total access count rather than recency. An item accessed 500 times stays, even if its last access was an hour ago; an item accessed once stays out of the way even if it was touched thirty seconds ago. The common O(1) implementation keeps a hash map from key to node (as before), plus a second structure: a map from frequency count to a doubly linked list of all keys currently at that frequency, together with a running minFrequency pointer. On every access, a key's node moves from its current frequency bucket to the frequency + 1 bucket (inserted at the front of that bucket, so ties within the same frequency still break by recency); eviction removes the back of the minFrequency bucket, and minFrequency is bumped whenever that bucket empties out.

#Where Each One Breaks

LRU's weakness shows up under scan pollution: a single one-time sweep over a large dataset — a batch export, an analytics job doing a full table scan — touches every row exactly once, and under pure LRU those one-off reads push every genuinely hot item out of the cache, even though none of the scanned rows will be read again. This is exactly why production databases rarely ship plain LRU for their buffer pools: PostgreSQL? uses a clock-sweep algorithm, and many systems use segmented or "LRU-K" variants specifically to make a single touch insufficient to earn the top-priority spot.

LFU's weakness is the mirror image: stale popularity. An item that was accessed constantly last week but hasn't been touched since keeps a high frequency count and can refuse to be evicted even though it's now completely cold — meanwhile, a newly popular item starts at frequency 1 and gets evicted before it has a chance to prove itself. Production LFU implementations typically add aging or decay — periodically halving all frequency counts, or weighting recent accesses more heavily than old ones — specifically to fix this.

#Comparing the Two

Java engineers can also get a working LRU cache almost for free from the standard library: LinkedHashMap supports an accessOrder constructor flag and an overridable removeEldestEntry hook, which together implement the same recency-ordering behavior without hand-rolling the linked list. It's a perfectly good production shortcut — just don't offer it as your first answer in an interview that's explicitly asking you to explain how LRU works, since it hides the exact mechanism the question is probing for.