🧠 LRU Cache

How It Works

An LRU (Least Recently Used) cache evicts the least-recently-used entry when full. It achieves O(1) get and put using two structures:

• Doubly linked list — maintains recency order. Head = MRU, Tail = LRU. Moving a node to the head and removing the tail are both O(1) pointer swaps.
• Hash map — maps each key directly to its list node, giving O(1) lookup without traversal.
• get(key): hash map lookup → move found node to head → return value (or -1 on miss).
• put(key, val): if key exists, update and move to head. Otherwise insert at head. If over capacity, remove tail node and its hash entry first.