Implement LRU Cache

Home/

Blog/

Implement LRU Cache

2 mins read

Oct 15, 2025

Content

Problem Statement

Hint

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown

// simple single threaded LRUCache
class LRUCache { 
 unordered_map<int, ListNode*> cache; 
 // each entry in linked list is <key, value>
 LinkedList cache_vals;
 int capacity; // total capacity
 
public:
 LRUCache(int capacity) {
 this->capacity = capacity;
 }
 
 ~LRUCache() {
 for (auto& t : cache) {
 delete t.second;
 }
 }
 
 int get(int key) {
 //TODO: Write - Your - Code
 return -1;
 }
 void set(int key, int value) {
 //TODO: Write - Your - Code
 } 
 
 string print() {
 string result = "";
 for (auto& x : cache) {
 result += "(" + std::to_string(x.first) + "," + std::to_string(x.second->value) + "),";
 }
 return result;
 }
};

// Linked list operations
// void add_at_tail(int val)
// void delete_node(ListNode* node)
// void delete_from_head()
// void delete_from_tail()
// ListNode* get_head()
// void set_head(ListNode* node)
// ListNode* get_tail()
// void set_tail(ListNode* node)
// simple single threaded LRUCache
class LRUCache {
 unordered_set<int> cache;
 // each entry in linked list is the value of the element
 LinkedList cache_vals;
 int capacity; // total capacity
public:
 LRUCache(int capacity) {
 this->capacity = capacity;
 }
 
 ~LRUCache() {
 cache.clear();
 }
 ListNode* get(int val) {
 auto p = cache.find(val);
 if (p == cache.end()) {
 return nullptr;
 }
 else{
 ListNode* i = cache_vals.get_head();
 while(i != nullptr){
 if (i->value == val){
 return i;
 }
 i = i->next;
 }
 }
 }
 void set(int value) {
 ListNode* check = get(value);
 if(check == nullptr){
 if(cache.size() >= capacity){
 cache_vals.add_at_tail(value);
 int head_val = cache_vals.get_head()->value;
 cache.erase(head_val);
 cache_vals.delete_from_head();
 }
 else{
 cache_vals.add_at_tail(value);
 cache.insert(value);
 }
 }
 else{
 if(check == cache_vals.get_tail()){
 return;
 }
 if(check == cache_vals.get_head()){
 cache_vals.add_at_tail(check->value);
 cache_vals.delete_from_head();
 return;
 }
 if(check->prev != nullptr){
 check->prev->next = check->next;
 }
 if(check->next != nullptr){
 check->next->prev = check->prev;
 }
 cache_vals.add_at_tail(check->value);
 delete check;
 }
 }
 void print() {
 ListNode* i = cache_vals.get_head();
 while(i != nullptr){
 cout << i->value << ", ";
 i = i ->next;
 }
 cout << endl;
 }
};
int main(int argc, char const *argv[])
{
 LRUCache cache(4);
 cache.set(1);
 cache.print();
 cache.set(2);
 cache.print();
 cache.set(3);
 cache.print();
 cache.set(4);
 cache.print();
 cache.set(5);
 cache.print();
 cache.set(2);
 cache.print();
 return 0;
}

Solution Explanation#

Runtime Complexity#

get (hashset): O(1) in the average case, O(n) in the worst case

set (hashset): Constant, O(1)

deletion at head when adding a new element (linked list): Constant, O(1)

search for deleting and adding to tail (linked list): O(n)

Complexity: O(n)

Memory Complexity#

Linear, O(n) where n is the size of cache.

Solution Breakdown#

Caching is a technique to store data in a faster storage (usually RAM) to serve future requests faster. Below are some common examples where cache is used:

A processor cache is used to read data faster from main memory (RAM).
Cache in RAM can be used to store part of disk data in RAM and serve future requests faster.
Network responses can be cached in RAM to avoid too many network calls.

However, cache store is usually not big enough to store the full data set. So we need to evict data from the cache whenever it becomes full. There are a number of caching algorithms to implement a cache eviction policy. LRU is very simple and a commonly used algorithm. The core concept of the LRU algorithm is to evict the oldest data from the cache to accommodate more data.

To implement an LRU cache we use two data structures: a hashmap and a doubly linked list. A doubly linked list helps in maintaining the eviction order and a hashmap helps with O(1) lookup of cached keys. Here goes the algorithm for LRU cache.