We need a cache that stores key-value pairs but has a fixed size limit. When the cache is full and we insert a new key, we evict the entry that has gone unused for the longest time. Both get and put count as using a key.

The hard part is the O(1) requirement. A hash map gives O(1) lookup and insertion, but it has no concept of ordering. A queue or list can track usage order, but finding a specific element in it takes O(n). We need a structure that does both: fast lookup and fast reordering.

The standard answer combines a hash map (for O(1) lookup by key) with a doubly-linked list (for O(1) removal and reinsertion to track recency). This combination is sometimes called a linked hash map.

Key Constraints:

Intuition

Keep all key-value pairs in a list, where each entry carries a timestamp recording when it was last used. On get, scan the list for the key. On put, scan to check whether the key exists, update or insert it, and if the cache is full, scan again to find the entry with the oldest timestamp and remove it.

This is correct, but every operation scans the entire cache. With n entries, each get and put is O(n).

Algorithm

Example Walkthrough

Code

Every operation scans the full cache, which violates the O(1) requirement. The next approach removes both scans: a hash map locates any key directly, and a doubly-linked list keeps entries in recency order so the least recently used entry is always at a known position.

Intuition

The two requirements, fast lookup and fast recency tracking, map onto two structures. A hash map gives O(1) lookup. A doubly-linked list gives O(1) insertion and removal when we already hold a pointer to the node. Combining them covers every operation.

Maintain a doubly-linked list where nodes are ordered by recency: the most recently used node sits right after the head, and the least recently used sits right before the tail. The hash map maps each key to its node in that list. To use a key, we find its node through the map in O(1), unlink it from its current position in O(1), and reinsert it at the front in O(1). To evict, we remove the node right before the tail in O(1).

This ordering stays correct because every access (whether a get, an update, or an insert) moves the touched node to the front. A node drifts toward the tail only when other nodes are touched after it, so the node at the tail is always the one untouched for the longest time, which is the LRU entry by definition.

Dummy head and tail sentinel nodes remove the empty-list edge cases. With them, every real node always has a non-null prev and next, so removeNode and addToFront are the same four pointer assignments every time, with no null checks for inserting into an empty list or removing the last element.

Algorithm

Example Walkthrough

Code

Approach 2 is O(1) per operation, which is optimal. It does require writing the doubly-linked list by hand. The next approach reaches the same complexity using ordered containers from the standard library, trading the manual pointer code for built-in structures.

Intuition

Several languages ship a structure that combines a hash map with insertion-order tracking, which is the same hash map plus doubly-linked list combination from Approach 2, already implemented. Java has LinkedHashMap, Python has OrderedDict, and C++ pairs std::list with an unordered_map of iterators. The code shrinks to a few lines because the standard library handles the pointer work.

Each language exposes the recency move differently. Java's LinkedHashMap with accessOrder=true moves an entry to the end on every access, and overriding removeEldestEntry evicts the oldest automatically. Python's OrderedDict.move_to_end() does it explicitly, and popitem(last=False) removes the oldest. JavaScript's and TypeScript's Map preserve insertion order, so deleting a key and re-inserting it sends it to the end, and the first key returned by the iterator is the oldest.

Algorithm

Example Walkthrough

Code