How would you implement an LRU (Least Recently Used) cache?

An LRU cache can be efficiently implemented using a combination of a hash map and a doubly linked list. The hash map provides O(1) access to cache entries, while the doubly linked list maintains the order of usage with most recently used at the head. On access, move the node to the head; on insertion when full, remove the tail node. This gives O(1) for both get and put operations.