LRU Cache

Design a data structure that follows the Least Recently Used (LRU) eviction policy.

Why this is worth learning

The map answers where a key lives; the doubly linked list answers which key is oldest. Neither structure alone provides both constant-time lookup and recency updates.

Before coding: one-minute experiment

At capacity 2, after Put(1,10), Put(2,20), Get(1), Put(3,30), which key is evicted?

Function signature

type LRUCache struct { /* fields */ }

func Constructor(capacity int) LRUCache
func (c *LRUCache) Get(key int) int
func (c *LRUCache) Put(key int, value int)

Inputs / outputs

• Constructor(capacity): initialize with capacity.
• Get(key): return value or -1 if not found; mark as most recently used.
• Put(key, value): insert or update; evict LRU if capacity exceeded.

Example

capacity = 2
Put(1,1)
Put(2,2)
Get(1) -> 1
Put(3,3) // evicts key 2
Get(2) -> -1

Constraints

• 1 <= capacity <= 100_000
• Up to 200_000 operations.

Core idea (near-solution)

A map answers key lookup, while an ordered slice can model recency and eviction. That baseline is correct but removing a hit from the middle of a slice costs O(n). A list allows constant-size rewiring once the node and its neighbors are known. Map each key to its list node, and give each node both Next and Prev so no predecessor scan is necessary. Move accessed nodes to the front and evict at the back. The required state is not just an order: the map and list must contain exactly the same live entries after every operation.

Invariant: most recently used item is at the front; least recently used is at the back.

Algorithm (step-by-step)

1. Get:
   • If key missing, return -1.
   • Move node to front and return its value.
2. Put:
   • If key exists, update value and move node to front.
   • Else insert new node at front and add to map.
   • If size exceeds capacity, remove tail node and delete from map.

Correctness sketch

Maintain a one-to-one correspondence between map entries and real list nodes, with the list ordered from most recently used at the front to least recently used at the back. A successful Get returns the mapped value and moves that node to the most-recent end, preserving membership while updating the required order. Put on an existing key changes its value and moves the same node, without increasing size. Put on a new key inserts one mapped node; if capacity is exceeded, remove the least-recent real node from both the list and map. Dummy endpoints make every splice uniform. Each operation therefore preserves the capacity, value, membership, and recency invariants.

Trace (hand walkthrough)

Example input:
capacity = 2
Put(1,1)
Put(2,2)
Get(1) -> 1
Put(3,3) // evicts key 2
Get(2) -> -1

Walk:
- Put(1): [1]
- Put(2): [2,1]
- Get(1)=1 -> move to front: [1,2]
- Put(3): evict 2 -> [3,1]
- Get(2)=-1 (not found)

Pitfalls to avoid

• Forgetting to update the map on insertion or eviction. A splice that moves an existing node does not need a map rewrite because its identity is unchanged.
• Not evicting the LRU item on capacity overflow.
• Breaking the list links when removing/adding nodes.

Debugging lens

Use a simple map plus recency slice as an independent model. Exercise updates of existing keys, repeated gets, misses, capacity one, and independent cache instances.

Complexity

Expected O(1) map work and O(1) pointer splicing per operation. Space: O(capacity). This is an average hash-table bound, not a strict worst-case bound or a concurrency guarantee.

Implementation notes (Go)

• Use dummy head/tail nodes to simplify insertion and removal.
• Keep a map from key to *node for O(1) access.

Contract precision

Capacity is at least one. A Get miss returns -1 and does not insert a node. Updating an existing key refreshes recency without changing size. Instances are independent; methods are not synchronized for concurrent use.

Reconstruction checkpoint

Capacity is 2. Apply Put(4,40), Put(7,70), Put(4,41), Get(9), Put(8,80). Give the final order most-recent first and explain the effect of the miss and the update.

Return to Linked List · Module quiz