Design an LRU Cache

Requirements: Design and implement a Least Recently Used (LRU) cache supporting get(key) and put(key, value) in O(1) time, with a fixed capacity; when the capacity is exceeded, evict the least recently used entry.

Design: Combine a hash map (key -> node pointer) with a doubly linked list ordered by recency (most-recently-used at head, least-recently-used at tail). get moves the accessed node to the head and returns its value (O(1) via the map + list splice); put inserts/updates a node at the head, evicting the tail node if capacity is exceeded. Discuss thread-safety (locking) if asked for a concurrent variant, and trade-offs versus LFU (Least Frequently Used) caches.