Pattern visualizer
LRU Cache
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. 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]..
Hash map for O(1) lookup, doubly linked list for O(1) reordering
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].
1FUNCTION get(key)2 IF key NOT IN map RETURN -13 node <- map[key]; MOVE node TO FRONT4 RETURN node.value5FUNCTION put(key, value)6 IF key IN map7 map[key].value <- value8 MOVE map[key] TO FRONT9 ELSE10 IF SIZE(map) = capacity11 lru <- tail.prev12 UNLINK lru; REMOVE lru.key FROM map13 node <- NEW NODE(key, value)14 INSERT node AT FRONT; map[key] <- node
← / → step · space play · Home restart