LRU Cache
A hash map finds the entry; a doubly linked list keeps them ordered by recency.
Approach
Map each key to a node so lookups are O(1), and thread those nodes through a doubly linked list whose head is the most recently used. Every get and put moves its node to the head; when you exceed capacity, evict the tail. Dummy head and tail nodes remove every null check from the unlink/insert code, and an ordered map (Python's OrderedDict, JavaScript's Map) gives you the same ordering for free.
Time complexity
O(1) per operation
Space complexity
O(capacity)
Common mistake
Reaching for a singly linked list — without a back pointer you can't unlink a node in O(1), which quietly makes every eviction a scan.
See it run, step by step
Generate an interactive lesson for LRU Cache — trace every variable and watch the algorithm execute until it clicks.
Create a lesson with this problem