LRU Cache.

— how OrderedDict / hashmap + doubly-linked list keep get, put, and evict at O(1).

Capacity3 Operations9 PatternHash Map + Doubly-Linked List ComplexityO(1) per op

Step 0 of 0

Hash Map.

key → node pointer (O(1) lookup)

empty

Doubly-Linked List.

ordered by recency — head = most recent, tail = least recent

← HEAD (most recent) TAIL (least recent) →

empty

Action

Press NEXT to begin

A scripted sequence of put / get operations on a 3-slot LRU cache. Watch the hash map and the doubly-linked list stay in sync.

Why this pairing works.

Hash map alone gives O(1) lookup but no notion of "recency" — you can't tell which entry was used least recently.

Doubly-linked list alone gives O(1) head/tail insertion and deletion AND a clear order — but finding a specific key requires walking the list (O(n)).

Together: the hash map tells you where a node lives in O(1); the DLL lets you unlink and relink that node in O(1). Three operations stay O(1):

get(key) → look up node via the map, unlink it, splice in at the head.
put(key, val) on existing key → same as get, plus overwrite value.
put(key, val) on new key when full → drop the tail node (least recent), remove its key from the map, add the new node at head.

Python's OrderedDict implements exactly this internally — you're using a prebuilt hashmap+DLL. The manual version (Node class with prev/next pointers, sentinel head/tail) is the interview follow-up if asked to do it without stdlib.