Designing an LRU Cache

An LRU (Least Recently Used) Cache is a data structure that stores frequently accessed data in a limited-capacity memory region to improve performance. It addresses the problem of what to evict when the cache is full by always removing the item that has not been used for the longest time.

How an LRU Cache Works

At its core, an LRU Cache combines two fundamental data structures: a hash map and a doubly linked list. This combination allows for both fast lookups and efficient management of item recency.

Hash Map for Fast Lookups

The hash map provides `O(1)` average-time complexity for retrieving cache items by their key. Each key in the hash map points directly to a corresponding node in the doubly linked list. This ensures that checking for an item's existence or accessing its value is extremely fast.

Doubly Linked List for Order

The doubly linked list maintains the order of items based on 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 the list, signifying that it is now the most recently used. This operation also takes `O(1)` time because the linked list allows for constant-time insertion and deletion of nodes given a pointer to the node.

Eviction Logic

When the cache reaches its maximum capacity and a new item needs to be added, the LRU Cache must evict an existing item. The item at the tail of the doubly linked list is the least recently used, making it the prime candidate for eviction. The eviction process involves:

1. Identifying the item at the tail of the linked list. 2. Removing this item from the hash map using its key. 3. Removing the corresponding node from the doubly linked list.

This entire eviction process also operates in `O(1)` time.

function get(key):
  if key not in cache_map:
    return -1
  node = cache_map[key]
  move_to_front(node, lru_list)
  return node.value

function put(key, value):
  if key in cache_map:
    node = cache_map[key]
    node.value = value
    move_to_front(node, lru_list)
  else:
    if lru_list.size == capacity:
      lru_node = lru_list.tail
      remove_node(lru_node, lru_list)
      delete cache_map[lru_node.key]
    new_node = create_node(key, value)
    add_to_front(new_node, lru_list)
    cache_map[key] = new_node

Key takeaways

• An LRU Cache optimizes data access by storing frequently used items.
• It combines a hash map for `O(1)` lookups and a doubly linked list for `O(1)` order maintenance.
• Accessed items are moved to the front (head) of the linked list.
• When full, the least recently used item (tail of the linked list) is evicted.
• All core operations (get, put, eviction) achieve `O(1)` average-time complexity.