Implementing an LRU Cache

Background: Least Recently Used Eviction

When a CPU needs data, it generally looks in memory before accessing slower storage. As memory fills, the system needs a policy for deciding which existing page to replace. Operating-systems courses commonly introduce OPT, FIFO, LRU, Clock, and LFU. LRU is one of the most frequently used and discussed policies, so this article focuses on its behavior and implementation. It is still worth learning the alternatives: understanding the broader design space matters more than memorizing one interview algorithm.

What is LRU?

LRU stands for Least Recently Used. It evicts the item that has gone unused for the longest time. A small example makes the idea concrete:

Reference sequence: 4 3 4 2 3 1 4 2
Cache capacity: 3 entries

Load 4: 4
Load 3: 3 4
Load 4: 4 3
Load 2: 2 4 3
Load 3: 3 2 4
Load 1: 1 3 2  (4 is the least recently used, so it is evicted)
Load 4: 4 1 3
Load 2: 2 4 1

The leftmost item is the most recently used. Accessing an existing item moves it to the front. Inserting a missing item into a full cache removes the item at the back before placing the new one at the front.

Required Operations

• Set the cache capacity during initialization.
• Insert a value into the cache.
• Read a value from the cache.
  • If the value already exists, move it to the front.
  • If it does not exist and the cache is full, remove the last node and insert the new node at the front.
• Because both reads and writes need to promote a node, isolate that behavior in a reusable operation.

Data Structures

A linked list provides ordering, but a linked list alone requires a linear scan to find an arbitrary key. A map adds fast lookup, so the implementation combines a linked list with a map.

Why a Doubly Linked List Matters

A singly linked list can insert at the front cheaply, but it cannot remove an arbitrary node or the tail in constant time without also tracking predecessors. Tricks that swap a node's payload with its successor make an external key-to-node map fragile: the physical node no longer represents the same key after the swap.

An LRU cache needs to promote arbitrary entries and evict the tail, so a doubly linked list is the direct fit. In C++, std::list supplies that structure and owns its nodes safely.

Complete STL Implementation

std::list supports constant-time removal and insertion when an iterator is available. Combining it with an unordered_map gives average constant-time lookup, promotion, insertion, and eviction:

#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;

class LRUCache {
private:
    using Entry = pair<int, int>;
    using RecencyList = list<Entry>;

    size_t capacity;
    RecencyList recency;
    unordered_map<int, RecencyList::iterator> entries;

public:
    explicit LRUCache(size_t capacity): capacity(capacity) {}

    int get(int key) {
        auto found = entries.find(key);
        if (found == entries.end()) {
            return -1;
        }

        recency.splice(recency.begin(), recency, found->second);
        return found->second->second;
    }

    void put(int key, int value) {
        if (capacity == 0) {
            return;
        }

        auto found = entries.find(key);
        if (found != entries.end()) {
            found->second->second = value;
            recency.splice(recency.begin(), recency, found->second);
            return;
        }

        recency.emplace_front(key, value);
        entries[key] = recency.begin();

        if (entries.size() > capacity) {
            const int evictedKey = recency.back().first;
            entries.erase(evictedKey);
            recency.pop_back();
        }
    }
};

Here, the list records recency while the hash map points directly to each list node. splice moves an existing node to the front without reallocating it or invalidating its iterator. Insertion and eviction update both structures together, and a zero-capacity cache remains empty.

The implementation assumes -1 is an acceptable miss sentinel. A reusable cache would normally return std::optional<int> so every integer remains a valid stored value.