LRU Cache Design

DSA · Advanced

Definition

An LRU cache evicts the least recently used item when full, using a hash map plus ordered list.

A top system-design-meets-DSA interview question.

Diagram

Flowchart

Example: OrderedDict LRU

from collections import OrderedDict
c, cap = OrderedDict(), 2
def put(k, v):
    c[k] = v; c.move_to_end(k)
    if len(c) > cap: c.popitem(last=False)
put(1, 1); put(2, 2); c.move_to_end(1); put(3, 3)
print(list(c))

Output: [1, 3]

Complexity

get/put O(1)

Key points

Manual version: dict + doubly linked list
Dummy head/tail simplify edge cases

Interview questions

Why a doubly linked list?

It removes any node in O(1) when you have a pointer to it.