LRU Cache

Tags

LRU Cache

Category

Linked Lists

Difficulty

Hard

Problem Statement

Implement a Least Recently Used (LRU) Cache that supports two operations in O(1) time:

  • get(key) — Return the value associated with the key if it exists in the cache, otherwise return -1. Accessing a key makes it the most recently used.
  • put(key, value) — Insert or update the key-value pair. If the cache exceeds its capacity after insertion, evict the least recently used item.

The cache has a fixed maximum capacity specified at initialization.

Intuition

To achieve O(1) for both get and put, we need two data structures working together. A hash map provides O(1) lookup by key. A doubly linked list maintains the usage order, with the most recently used item at the head and the least recently used at the tail. The hash map stores pointers to linked list nodes, enabling O(1) removal and reinsertion of any node.

Approach

  1. Maintain a hash map mapping keys to doubly linked list nodes.
  2. Maintain a doubly linked list with sentinel head and tail nodes to simplify edge cases.
  3. On get(key):
    • If the key is not in the hash map, return -1.
    • Otherwise, move the corresponding node to the head of the list (most recently used) and return its value.
  4. On put(key, value):
    • If the key already exists, update its value and move it to the head.
    • If the key does not exist, create a new node, add it to the head of the list, and insert it into the hash map.
    • If the cache size exceeds capacity, remove the node just before the tail sentinel (least recently used) and remove its key from the hash map.

Pseudocode

class LRUCache:
    constructor(capacity):
        this.capacity = capacity
        this.map = new HashMap()
        this.head = new DummyNode()  // sentinel
        this.tail = new DummyNode()  // sentinel
        this.head.next = this.tail
        this.tail.prev = this.head

    function get(key):
        if key not in map:
            return -1
        node = map[key]
        moveToHead(node)
        return node.value

    function put(key, value):
        if key in map:
            node = map[key]
            node.value = value
            moveToHead(node)
        else:
            node = new Node(key, value)
            map[key] = node
            addToHead(node)
            if map.size > capacity:
                lru = tail.prev
                removeNode(lru)
                delete map[lru.key]

    function addToHead(node):
        node.next = head.next
        node.prev = head
        head.next.prev = node
        head.next = node

    function removeNode(node):
        node.prev.next = node.next
        node.next.prev = node.prev

    function moveToHead(node):
        removeNode(node)
        addToHead(node)

Time & Space Complexity

  • Time: O(1) for both get and put operations. Hash map lookup, linked list insertion, and linked list removal are all constant time.
  • Space: O(capacity) for storing up to capacity key-value pairs in both the hash map and the linked list.

Key Insights

  • Sentinel (dummy) head and tail nodes eliminate null checks and special cases for empty lists, first insertions, and last removals.
  • Storing the key inside each linked list node is necessary so that when evicting the LRU node, we can also remove its entry from the hash map.
  • The doubly linked list is essential (not singly linked) because node removal requires updating both the previous and next pointers in O(1).
  • The hash map and linked list together form a "linked hash map" — a common pattern in systems programming.
  • This data structure is widely used in operating systems (page replacement), databases (buffer pools), and web caching.

System Design Application

The LRU Cache algorithm is the named eviction mechanism in Distributed-Cache. When a distributed cache reaches capacity, the LRU eviction policy (implemented as a doubly linked list + hash map — this note) removes the entry least recently accessed. See Distributed-Cache for the infrastructure context: TTL-based expiry, cache stampede mitigation, and write-through vs cache-aside strategies.

Edge Cases

  • Capacity of 1 — every put of a new key evicts the existing item.
  • Getting a key that was just evicted — returns -1.
  • Putting the same key multiple times — updates the value and refreshes its position.
  • Capacity is very large — the cache never evicts, behaving like a regular hash map.
  • Interleaving many gets and puts — the ordering is maintained correctly through consistent move-to-head operations.

Linked mentions