What Is an LRU Cache?

An LRU (Least Recently Used) Cache is a data structure that stores a limited number of items, prioritizing those accessed most recently. It's crucial for optimizing performance in systems where frequently accessed data needs to be retrieved quickly without repeatedly fetching it from a slower source.

How an LRU Cache Works

An LRU Cache operates by combining two core data structures: a hash map and a doubly linked list. This combination allows for both fast lookups and efficient reordering of items based on their usage.

The Doubly Linked List for Ordering

The doubly linked list maintains the order of items by their recency of use. The head of the list represents the most recently used item, while the tail represents the least recently used item. When an item is accessed, it is moved to the head of this list, signifying its recent use. This operation is efficient because only pointers need to be updated.

The Hash Map for Instant Access

The hash map stores key-value pairs, where the key is the identifier for an item and the value is a reference (pointer) to its corresponding node in the doubly linked list. This allows for `O(1)` average time complexity for retrieving any item directly, without traversing the linked list.

Accessing and Updating Items

When an item is accessed: 1. The hash map is used to quickly locate the item's node in the linked list. 2. If found, the node is removed from its current position and moved to the head of the linked list. 3. If not found, and the cache has capacity, the new item is added to the head of the linked list and its key-node mapping is added to the hash map.

Eviction Logic

When the cache reaches its maximum capacity and a new item needs to be added, the LRU policy dictates that the least recently used item must be evicted. This is achieved by: 1. Removing the node at the tail of the doubly linked list (which is the least recently used item). 2. Removing its corresponding entry from the hash map. 3. Adding the new item to the head of the linked list and its key-node mapping to the hash map.

function put(key, value):
  node = map.get(key)
  if node exists:
    node.value = value
    list.moveToHead(node)
  else:
    if list.size == capacity:
      tailNode = list.popTail()
      map.remove(tailNode.key)
    newNode = createNode(key, value)
    list.pushHead(newNode)
    map.put(key, newNode)

function get(key):
  node = map.get(key)
  if node exists:
    list.moveToHead(node)
    return node.value
  return null

Key Takeaways

• An LRU Cache stores frequently accessed data for quick retrieval.
• It combines a hash map for `O(1)` lookups and a doubly linked list for `O(1)` reordering.
• Accessed items are moved to the head of the linked list to mark them as recently used.
• When full, the item at the tail (least recently used) is evicted to make space for new items.
• This design ensures fast access, updates, and efficient memory management.