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.
Linked-List Node
struct Node {
int key;
int val;
Node *next;
Node(int k, int v): key(k), val(v), next(NULL) {}
};
Lookup Map
map<int, Node *> mp;
A Singly Linked-List Technique
Removing a node from a singly linked list is awkward when only that node is available. If node A has a successor B, one technique is to copy or swap B's payload into A, bypass B, and then free B:
Node *B = A->next;
A->next = B->next;
swap(A->val, B->val);
B->next = NULL;
free(B);
When keys and an external map are involved, the keys and map entries must also be updated. The complete example below applies that technique while promoting nodes.
Complete Implementation
#include <iostream>
#include <map>
#include <iterator>
#include <algorithm>
#include <cstdio>
using namespace std;
struct Node {
int key;
int val;
Node *next;
Node(int k, int v): key(k), val(v), next(NULL) {}
};
class LRUCache {
public:
LRUCache(int capacity) {
count = 0; // Current number of cached entries.
size = capacity; // Maximum capacity.
cacheList = NULL; // The list starts empty.
}
int get(int key) {
if (cacheList == NULL) {
return -1;
}
map<int, Node *>::iterator it = mp.find(key);
if (it == mp.end()) {
return -1;
} else {
Node *newNode = it->second;
pushNewNodeToFront(newNode);
return newNode->val;
}
}
void put(int key, int val) {
if (cacheList == NULL) {
cacheList = new Node(key, val);
cacheList->next = NULL;
mp[key] = cacheList;
count++;
} else {
map<int, Node *>::iterator it = mp.find(key);
if (it == mp.end()) { // This key is not currently cached.
if (count == size) { // The cache is full.
Node *p = cacheList;
Node *pre = p; // The node before the tail.
while (p->next != NULL) { // Walk to the tail.
pre = p;
p = p->next;
}
mp.erase(p->key);
count--;
if (pre == p) {
cacheList = NULL;
} else {
pre->next = NULL;
}
free(p);
}
// Insert the new node after eviction.
Node *newNode = new Node(key, val);
newNode->next = cacheList;
cacheList = newNode;
mp[key] = cacheList;
count++;
} else { // The key already exists.
Node *newNode = it->second;
newNode->val = val;
pushNewNodeToFront(newNode);
}
}
}
void pushNewNodeToFront(Node *newNode) {
if (count == 1) return;
if (newNode == cacheList) return;
Node *next = newNode->next;
if (next) {
newNode->next = next->next;
swap(newNode->key, next->key);
swap(newNode->val, next->val);
next->next = cacheList;
cacheList = next;
swap(mp[newNode->key], mp[next->key]);
} else { // The requested node is the tail.
Node *p = cacheList;
while (p->next != newNode) {
p = p->next;
}
p->next = NULL;
newNode->next = cacheList;
cacheList = newNode;
}
}
private:
int count;
int size;
Node *cacheList;
map<int, Node *> mp;
};
This version illustrates the mechanics, but its singly linked list still requires a linear walk when removing the tail. It also manages memory manually. A production implementation would normally use a doubly linked list or standard-library containers to make promotion and eviction constant-time and ownership safer.
A Shorter 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:
int cap;
list<pair<int, int>> l;
unordered_map<int, list<pair<int, int>>::iterator> m;
public:
LRUCache(int capacity): cap(capacity) {}
int get(int key) {
auto it = m.find(key);
if (it == m.end()) {
return -1;
}
l.splice(l.begin(), l, it->second);
return it->second->second;
}
void set(int key, int val) {
auto it = m.find(key);
if (it != m.end()) {
l.erase(it->second);
}
l.push_front(make_pair(key, val));
m[key] = l.begin();
if (int(m.size()) > cap) {
int k = l.rbegin()->first;
l.pop_back();
m.erase(k);
}
}
};
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, and eviction removes the node at the back along with its map entry.