LLD · Data structure

LRU Cache

Design a cache with fixed capacity where get and put run in O(1) time. Evict the least recently used item when full.

Simple summary: A hash map finds an item quickly. A doubly linked list remembers usage order. Every successful read or write moves the item to the front, while eviction removes the item at the back.

1. Requirements

get(key) — return value or -1 if missing; mark key as recently used.
put(key, value) — insert/update; evict LRU if over capacity.
Both operations must take O(1) average time.
Capacity is fixed and must be greater than zero.

2. Data structures

Hash map — key → node reference (O(1) lookup).
Doubly linked list — order of use; head = most recent, tail = LRU.

A singly linked list cannot remove an arbitrary node without finding its previous node. A doubly linked node already points to both neighbors, so removal takes O(1) time.

3. Class design

class Node { key value prev next } class LRUCache { capacity map // key → Node head // dummy: most-recent side tail // dummy: least-recent side get(key) put(key, value) remove(node) addAfterHead(node) moveToFront(node) }

Dummy head and tail nodes remove special cases for an empty list or a one-item list.

4. List helpers

remove(node): node.prev.next = node.next node.next.prev = node.prev addAfterHead(node): node.prev = head node.next = head.next head.next.prev = node head.next = node moveToFront(node): remove(node) addAfterHead(node)

5. Cache operations

get(key): if key not in map: return -1 node = map[key] moveToFront(node) return node.value put(key, value): if key in map: node = map[key] node.value = value moveToFront(node) return node = new Node(key, value) map[key] = node addAfterHead(node) if map.size > capacity: lru = tail.prev remove(lru) delete map[lru.key]

6. Walkthrough (capacity 2)

put(1,1) → cache {1} list: [1] put(2,2) → cache {1,2} list: [2,1] (2 most recent) get(1) → returns 1 list: [1,2] (1 touched → front) put(3,3) → evict key 2 (LRU) list: [3,1] get(2) → -1 (evicted) get(1) → returns 1 list: [1,3] put(1,9) → update key 1 list: [1:9,3]

7. Complexity and edge cases

Operation	Cost	Why
`get`	O(1) average	One map lookup and constant-time list moves
`put`	O(1) average	Map update, list insert, and at most one eviction
Storage	O(capacity)	One map entry and one node per cached key

Reject zero or negative capacity in the constructor.
Updating a key must not create a second node.
A missing get must not change usage order.
For thread safety, guard both the map and list with the same lock.

8. Interview talking points

The map provides lookup; the list maintains usage order.
Use dummy head/tail nodes to simplify edge cases.
Keep pointer changes in small helper methods so each operation has one owner.

Quick revision

LRU = evict least recently used when full.
Hash map + doubly linked list → O(1) get/put.
Read or update: Move the node to the front.
Insert: Add a new node after the dummy head.
Evict: Remove tail.prev when capacity is exceeded.
Space: O(capacity).