LRU Cache

Problem

Design a data structure that follows the Least Recently Used cache eviction policy. Implement get(key) (return value or -1) and put(key, value) (insert or update, evicting LRU if capacity exceeded). Both operations must run in O(1) time.

LRUCache(2)        # capacity = 2
put(1, 1)          # cache: {1:1}
put(2, 2)          # cache: {1:1, 2:2}
get(1)   → 1       # cache: {2:2, 1:1}  (1 is now MRU)
put(3, 3)          # evict key 2;  cache: {1:1, 3:3}
get(2)   → -1      # key 2 was evicted
put(4, 4)          # evict key 1;  cache: {3:3, 4:4}
get(1)   → -1
get(3)   → 3
get(4)   → 4

Solution

Approach: Hash map for lookup, doubly linked list for ordering.

The two operations need two different powers, so use two structures. A hash map from key to node gives O(1) lookup. A doubly linked list ordered by recency gives O(1) reordering: most recently used sits just after a dummy head, least recently used just before a dummy tail. The list must be doubly linked because removing an arbitrary node in O(1) needs its predecessor, and .prev supplies that without traversal. The two sentinels mean _remove and _insert_front never hit a None neighbor, so there is no empty-list or single-node special case. _remove unlinks a node with node.prev.next = node.next; node.next.prev = node.prev; _insert_front splices it in right after head.

get looks the key up, and on a hit removes the node and reinserts it at the front to mark it most recent, returning its value (or -1 on a miss). put has two branches. If the key exists, overwrite its value and promote it to the front. If it is new and the cache is already at capacity, evict first: tail.prev is the LRU node, so unlink it and - critically - del self.map[lru.key]. This is why each node stores its own key: eviction starts from the list side and must reach back into the map. Then build the new node, register it in the map, and insert at the front.

Edge cases: Eviction only fires when len(self.map) == self.capacity on a new key; updating an existing key never evicts. A miss on get returns -1 and leaves the list untouched.

Complexity: O(1) time per get/put - hash lookup plus constant relinking; O(capacity) space.