LRU Cache

hard

Implement an LRU Cache with O(1) get and put using a doubly linked list and hash map

LRU Cache

Key Insight

Doubly linked list orders by recency; hash map gives O(1) lookup — together they make O(1) LRU

Step 1Setup Empty Cache
Capacity: 2Map: {}H ↔ T (sentinels)
head
H
tail
T
null

Capacity = 2. Doubly linked list with head/tail sentinels. Hash map is empty.

1 / 7
Practice the Code

Step-by-Step Walkthrough: LRU Cache

Doubly linked list orders by recency; hash map gives O(1) lookup — together they make O(1) LRU

  1. Setup Empty Cache

    Capacity = 2. Doubly linked list with head/tail sentinels. Hash map is empty.

  2. put(1, 1)

    Insert key=1. Add node after head sentinel. Map: {1→node}.

  3. put(2, 2)

    Insert key=2. Add after head (most recent). Map: {1→node, 2→node}.

  4. get(1) → Move to Front

    Key 1 found via map. Remove from current position, re-insert after head.

  5. put(3, 3) — Evict LRU

    Cache full. Evict LRU (node before tail = key 2). Insert key 3 after head.

  6. get(2) → -1

    Key 2 not in map (was evicted). Return -1.

  7. Final State

    Cache holds keys 3 and 1. Key 3 is most recent, key 1 is LRU.