Naive LRU: List Scan

Simplest LRU: store entries in a list, ordered most-recent-first.

Works! But:

• get: O(n) — scan the list
• put: O(n) — same
• Insert at front of a list: O(n) for arrays

For a million-entry cache, every operation is a million-comparison search. Unusable.

Real LRU achieves O(1) per operation. Trick: combine a hash map (O(1) lookup) with a doubly-linked list (O(1) move-to-front).