Skip to content
The Chat Archive
gemini-2.5-flash-preview-04-17· Google LMArena Human Preference 140K

Write an LRU cache

  1. User

    Write an LRU cache

  2. Assistant

    Okay, here is a Python implementation of an LRU (Least Recently Used) cache using a combination of a dictionary and a doubly linked list.

    The dictionary provides O(1) average time complexity for get and put operations (to find the node), and the doubly linked list provides O(1) time complexity for reordering nodes (moving to head, removing from tail).

    class Node:
        """
        A node for the doubly linked list to store key-value pairs
        and maintain the order of usage.
        """
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.prev = None # Pointer to the previous node
            self.next = None # Pointer to the next node
    
    class LRUCache:
        """
        Implements a Least Recently Used (LRU) cache.
        """
        def __init__(self, capacity: int):
            """
            Initializes the LRU cache with a given capacity.
    
            Args:
                capacity: The maximum number of key-value pairs the cache can hold.
            """
            self.capacity = capacity
            self.cache = {}  # Dictionary to store key -> node mapping
            
            # Dummy head and tail nodes for the doubly linked list.
            # This simplifies insertion and deletion logic at the ends.
            self.head = Node(0, 0)
            self.tail = Node(0, 0)
            
            # Link the dummy head and tail initially
            self.head.next = self.tail
            self.tail.prev = self.head
    
        def _add_node(self, node: Node):
            """
            Helper function to add a node right after the dummy head
            (making it the most recently used).
            """
            node.prev = self.head
            node.next = self.head.next
            self.head.next.prev = node
            self.head.next = node
    
        def _remove_node(self, node: Node):
            """
            Helper function to remove a node from the doubly linked list.
            """
            prev_node = node.prev
            next_node = node.next
            prev_node.next = next_node
            next_node.prev = prev_node
    
        def _move_to_head(self, node: Node):
            """
            Helper function to move an existing node to the head
            (marking it as most recently used).
            """
            self._remove_node(node)
            self._add_node(node)
    
        def _pop_tail(self) -> int:
            """
            Helper function to remove the node just before the dummy tail
            (this is the least recently used node) and return its key.
            """
            lru_node = self.tail.prev
            self._remove_node(lru_node)
            return lru_node.key
    
        def get(self, key: int) -> int:
            """
            Retrieves the value for a given key.
            If the key exists, move the corresponding node to the head
            and return its value. Otherwise, return -1.
    
            Args:
                key: The key to retrieve.
    
            Returns:
                The value associated with the key, or -1 if the key is not found.
            """
            if key in self.cache:
                node = self.cache[key]
                self._move_to_head(node)
                return node.value
            else:
                return -1 # Key not found
    
        def put(self, key: int, value: int) -> None:
            """
            Adds or updates a key-value pair in the cache.
            If the key exists, update its value and move the node to the head.
            If the key does not exist:
            - Create a new node and add it to the head.
            - If the cache exceeds capacity, remove the least recently used node
              (from the tail) from both the list and the dictionary.
    
            Args:
                key: The key to add or update.
                value: The value for the key.
            """
            if key in self.cache:
                # Key already exists, update value and move to head
                node = self.cache[key]
                node.value = value
                self._move_to_head(node)
            else:
                # Key does not exist, add new node
                new_node = Node(key, value)
                self.cache[key] = new_node
                self._add_node(new_node)
    
                # Check if capacity is exceeded
                if len(self.cache) > self.capacity:
                    # Remove the least recently used item (from the tail)
                    lru_key = self._pop_tail()
                    del self.cache[lru_key]
    
    # Example Usage:
    # lru = LRUCache(2)
    # lru.put(1, 1) # cache is {1:1}
    # lru.put(2, 2) # cache is {1:1, 2:2}
    # print(lru.get(1)) # returns 1; cache is {2:2, 1:1} (1 is now MRU)
    # lru.put(3, 3) # evicts key 2; cache is {1:1, 3:3}
    # print(lru.get(2)) # returns -1 (not found)
    # lru.put(4, 4) # evicts key 1; cache is {3:3, 4:4}
    # print(lru.get(1)) # returns -1 (not found)
    # print(lru.get(3)) # returns 3; cache is {4:4, 3:3} (3 is now MRU)
    # print(lru.get(4)) # returns 4; cache is {3:3, 4:4} (4 is now MRU)
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.