Implement LRU Cache

Problem: Design and implement a data structure for a Least Recently Used (LRU) cache. It should support:

• get(key): return the value if the key exists, else -1, and mark the key as recently used.
• put(key, value): insert or update the value; if inserting causes the cache to exceed its capacity, evict the least recently used key first.

Both operations must run in O(1) average time.

Constraints: Capacity is a fixed positive integer set at construction time.

Example: LRUCache cache = new LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found)

Approach: Combine a HashMap (key -> node reference) with a doubly linked list that maintains usage order (most-recently-used at the head, least-recently-used at the tail). On get, move the accessed node to the head. On put, insert/update at the head, and if over capacity, remove the tail node and its map entry. Both the map lookup and the linked-list pointer updates are O(1), giving O(1) amortized time for both operations.