Which data structure combination yields O(1) time for get and put operations in an LRU cache?

• A. Binary search tree
• B. Array and hash
• C. Linked list only
• D. Hash map plus a doubly linked list

Answer: (D)

Fast access in an LRU cache relies on using a hash map to index nodes and a doubly linked list to track recency. The hash map provides O(1) lookup by key, and each entry points to a node in the doubly linked list that represents that key’s position in the usage order. The doubly linked list lets you move a node to the front (most recently used) or remove the tail (least recently used) in constant time because each node has direct access to its previous and next neighbors.

When you get a value, you fetch the node from the hash map in O(1) and then move that node to the front of the list, maintaining the recency order. When you put a new value, if the key already exists you update the value and move its node to the front; if it’s a new key, you create a node at the front. If adding it exceeds capacity, you remove the tail node (the least recently used) in O(1) and delete its key from the hash map. The combination is essential: the hash map handles instant key-based access, while the doubly linked list efficiently reorders items and supports constant-time eviction, something a single structure like a binary search tree, an array, or a singly linked list cannot provide for all operations.