DSA Tracker

Visualize

LRU Cache

Hash map for O(1) lookup, doubly linked list for O(1) reordering

time O(1) per get / putspace O(capacity)

A hash map answers 'is this key here?' in O(1) but has no idea which key was touched longest ago. A list remembers order but finds a key in O(n). Put them together: the map stores key -> node, and the node lives in a doubly linked list ordered by recency. Because every node knows both its neighbours, it can be unlinked and re-inserted at the front in O(1) — no scan. Every get and every put moves the touched node to the front, so the node just before tail is always the least recently used, and eviction is a single unlink plus a map delete. Nodes must store their key, or eviction cannot find the map entry to remove.

Details

Animated on: LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4). Each cell is key:value, read most recently used (MRU) to least recently used (LRU). Answer: [null,null,1,null,-1,null,-1,3,4].

Problem:LRU CacheMedium

Hash map for O(1) lookup, doubly linked list for O(1) reordering

step 1 / 12

1:1
[0]
·
[1]

put(1,1): a new node holding BOTH key and value is inserted right after head and registered in the map (size 1 of 2). The node must carry its key so a future eviction can find its map entry. Order is [1].

  • MRU=0· arr[0] = 1:1
  • LRU=0· arr[0] = 1:1
Pseudocode
1FUNCTION get(key)
2  IF key NOT IN map RETURN -1
3  node <- map[key]; MOVE node TO FRONT
4  RETURN node.value
5FUNCTION put(key, value)
6  IF key IN map
7    map[key].value <- value
8    MOVE map[key] TO FRONT
9  ELSE
10    IF SIZE(map) = capacity
11      lru <- tail.prev
12      UNLINK lru; REMOVE lru.key FROM map
13    node <- NEW NODE(key, value)
14    INSERT node AT FRONT; map[key] <- node

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. put(1,1): a new node holding BOTH key and value is inserted right after head and registered in the map (size 1 of 2). The node must carry its key so a future eviction can find its map entry. Order is [1].
  2. put(2,2): a new node holding BOTH key and value is inserted right after head and registered in the map (size 2 of 2). The node must carry its key so a future eviction can find its map entry. Order is [2 -> 1].
  3. get(1) -> 1. A read counts as a use, so key 1 is unlinked from slot 1 and re-inserted right after head: it is now the MRU and safe from the next eviction. The doubly linked prev/next pointers make that unlink O(1). Order is [1 -> 2].
  4. put(3,3): key 3 is new but the cache already holds 2 of 2. The node just before tail is the least recently used — key 2 — so it is unlinked AND its key is deleted from the map. Forgetting the map delete leaves a dangling entry that would later return a freed node.
  5. put(3,3): a new node holding BOTH key and value is inserted right after head and registered in the map (size 2 of 2). The node must carry its key so a future eviction can find its map entry. Order is [3 -> 1].
  6. get(2): the map has no entry for key 2, so the answer is -1 without touching the list. The map is what makes the lookup O(1) — walking the list to check would be O(n). Order stays [3 -> 1].
  7. put(4,4): key 4 is new but the cache already holds 2 of 2. The node just before tail is the least recently used — key 1 — so it is unlinked AND its key is deleted from the map. Forgetting the map delete leaves a dangling entry that would later return a freed node.
  8. put(4,4): a new node holding BOTH key and value is inserted right after head and registered in the map (size 2 of 2). The node must carry its key so a future eviction can find its map entry. Order is [4 -> 3].
  9. get(1): the map has no entry for key 1, so the answer is -1 without touching the list. The map is what makes the lookup O(1) — walking the list to check would be O(n). Order stays [4 -> 3].
  10. get(3) -> 3. A read counts as a use, so key 3 is unlinked from slot 1 and re-inserted right after head: it is now the MRU and safe from the next eviction. The doubly linked prev/next pointers make that unlink O(1). Order is [3 -> 4].
  11. get(4) -> 4. A read counts as a use, so key 4 is unlinked from slot 1 and re-inserted right after head: it is now the MRU and safe from the next eviction. The doubly linked prev/next pointers make that unlink O(1). Order is [4 -> 3].
  12. All 9 operations done. Final order [4 -> 3]; every get answered in O(1) because the map found the node and the doubly linked list moved it without a scan. get results in sequence: [1, -1, -1, 3, 4].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve LRU Cache in the editorAll Linked List problemsBack to roadmap