LRU Cache

An LRU (Least Recently Used) cache is a fundamental data structure that stores a limited number of items, evicting the least recently used item when the cache is full and a new item needs to be added. This mechanism is crucial for optimizing performance in systems where frequently accessed data should be quickly available, avoiding costly re-computation or data retrieval.

How it Works

Unlike a simple array-based cache that might take O(n) time to find or evict items, an LRU cache achieves O(1) average time complexity for both `get` and `put` operations by combining two data structures: a Hash Map and a Doubly Linked List.

• Hash Map (or Dictionary): This allows for O(1) average time lookups to quickly determine if an item exists in the cache and to retrieve its corresponding node in the linked list.
• Doubly Linked List: This maintains the order of usage. The head of the list represents the Most Recently Used (MRU) item, and the tail represents the Least Recently Used (LRU) item. Because it's a doubly linked list, nodes can be moved or removed in O(1) time.

Cache Operations

Let's trace the core operations:

`put(key, value)`

1. Check Existence: Use the hash map to see if `key` is already in the cache. If it is, remove the old entry and its corresponding node from the linked list. 2. Check Capacity: If the cache is full (i.e., `len(map) == capacity`), evict the LRU item by removing the node at the tail of the doubly linked list and deleting its entry from the hash map. 3. Insert New Item: Create a new node for `(key, value)`, insert it at the head (MRU position) of the doubly linked list, and add `key` to the hash map, pointing to this new node.

`get(key)`

1. Check Existence: Use the hash map to find `key`. If it's not present, the item is not in the cache. 2. Update Usage: If `key` is found, retrieve its value and, crucially, move its corresponding node to the head (MRU position) of the doubly linked list. This marks it as recently used.

Pseudocode

def lru_op(cache, op, key, val=None):
    if op == "put":
        if key in cache.map:
            cache.remove(cache.map[key])
        elif len(cache.map) == cache.cap:
            cache.evict_lru()
        cache.insert_mru(key, val)
    elif op == "get":
        if key in cache.map:
            cache.make_mru(key)
            return cache.map[key].val
        return -1

Key Takeaways

• An LRU cache efficiently manages limited memory by evicting the least recently used items.
• It combines a hash map for O(1) average time lookups and a doubly linked list for O(1) time ordering.
• `get` operations update an item's recency by moving it to the MRU position.
• `put` operations handle both updates and insertions, evicting the LRU item if the cache is full.
• This design ensures constant time complexity for both core operations, making it highly performant.