What data structure is typically used for implementing a LRU cache?

A Least Recently Used (LRU) cache efficiently manages the storage of limited data by evicting the least recently accessed items when space is needed for new entries. The correct combination of data structures for implementing an LRU cache is a hash map paired with a doubly linked list.

The hash map serves as an efficient lookup table, allowing for O(1) time complexity when checking if an item is already in the cache. It maps keys (which represent the data) to their corresponding nodes in the doubly linked list. This allows for quick access and retrieval of the cache items.

The doubly linked list is used to maintain the order of entries based on their access time. When an item is accessed, it can be easily moved to the front of the list to signify that it is the most recently used. If the cache reaches its capacity and a new entry is added, the last node in the list (which represents the least recently used item) can be removed effectively. The linked nature of the list allows adding and removing nodes to be done in constant time as well.

Other options do not provide the same efficiencies. For example, an array and a queue would offer poor performance due to the need for shifting elements when items are added or