How does the LRU cache design problem work?

A Least Recently Used cache stores key-value pairs with a capacity limit, evicting the least recently accessed item when full. It requires O of one time for both get and put operations. The key insight is combining a hash map for O of one key lookups with a doubly linked list for O of one removal and insertion. The hash map maps keys to linked list nodes. The linked list orders nodes by recency with the most recent at the head. On get, move the accessed node to the head. On put, add a new node at the head and evict the tail node if capacity is exceeded. Both operations are constant time.