A fixed-size cache that, when full, throws out the least-recently-used entry. Every get or put marks an entry as most-recently-used and slides it to the front; the one that drifts to the back is first to go. Watch the recency order shuffle — and see why it's O(1).
gets an early key to rescue it from eviction, then puts new keys until the cache overflows and evicts whatever sat untouched longest. That's the whole idea: recency of use, not insertion order, decides who stays. Manually, put A, B, C, D at capacity 4, then get(A) — A jumps to the front — then put(E): B is evicted (not A), because A was just used. Real LRU caches pair a hash map (O(1) lookup) with a doubly-linked list (O(1) move-to-front and evict-tail); this uses a JS Map, which keeps insertion order, and re-inserts on access to reorder.