Complete Tutorial on LRU Cache with Implementations

Last Updated : 29 Mar, 2024

What is LRU Cache?

Cache replacement algorithms are efficiently designed to replace the cache when the space is full. The Least Recently Used (LRU) is one of those algorithms. As the name suggests when the cache memory is full, LRU picks the data that is least recently used and removes it in order to make space for the new data. The priority of the data in the cache changes according to the need of that data i.e. if some data is fetched or updated recently then the priority of that data would be changed and assigned to the highest priority, and the priority of the data decreases if it remains unused operations after operations.

Table of Content

What is LRU Cache?
Operations on LRU Cache:
Working of LRU Cache:
Ways to Implement LRU Cache:
LRU cache implementation using Queue and Hashing:
LRU cache implementation using Doubly Linked List and Hashing:
LRU cache implementation using Deque & Hashmap:
LRU cache implementation using Stack & Hashmap:
LRU cache using Counter Implementation:
LRU cache implementation using Lazy Updates:
Complexity Analysis of LRU Cache:
Advantages of LRU cache:
Disadvantages of LRU cache:
Real-World Application of LRU Cache:

LRU algorithm is a standard problem and it may have variations as per need for example, in operating systems LRU plays a crucial role as it can be used as a page replacement algorithm in order to minimize page faults.

Operations on LRU Cache:

LRUCache (Capacity c): Initialize LRU cache with positive size capacity c.
get (key): Returns the value of Key ‘k’ if it is present in the cache otherwise it returns -1. Also updates the priority of data in the LRU cache.
put (key, value): Update the value of the key if that key exists, Otherwise, add key-value pair to the cache. If the number of keys exceeded the capacity of LRU cache then dismiss the least recently used key.

Working of LRU Cache:

Let’s suppose we have an LRU cache of capacity 3, and we would like to perform following operations:

Put (key=1, value=A) into the cache
Put (key=2, value=B) into the cache
Put (key=3, value=C) into the cache
Get (key=2) from the cache
Get (key=4) from the cache
Put (key=4, value=D) into the cache
Put (key=3, value=E) into the cache
Get (key=4) from the cache
Put (key=1, value=A) into the cache

The above operations are performed one after another as shown in the image below:

Working-of-LRU-Cache-(1)

Detailed Explanation of each operation:

Put (key 1, value A): Since LRU cache has empty capacity=3, there is no need for any replacement and we put {1 : A} at the top i.e. {1 : A} has highest priority.
Put (key 2, value B): Since LRU cache has empty capacity=2, again there is no need for any replacement, but now the {2 : B} has the highest priority and priority of {1 : A} decrease.
Put (key 3, value C): Still there is 1 empty space vacant in the cache, therefore put {3 : C} without any replacement, notice now the cache is full and the current order of priority from highest to lowest is {3:C}, {2:B}, {1:A}.
Get (key 2): Now, return value of key=2 during this operation, also since key=2 is used, now the new priority order is {2:B}, {3:C}, {1:A}
Get (key 4): Observe that key 4 is not present in the cache, we return ‘-1’ for this operation.
Put (key 4, value D): Observe that cache is FULL, now use LRU algorithm to determine which key is least recently used. Since {1:A} had the least priority, remove {1:A} from our cache and put {4:D} into the cache. Notice that the new priority order is {4:D}, {2:B}, {3:C}
Put (key 3, value E): Since key=3 was already present in the cache having value=C, so this operation won’t result in removal of any key, rather it will update the value of key=3 to ‘E’. Now, the new order of priority will become {3:E}, {4:D}, {2:B}
Get (key 4): Return the value of key=4. Now, new priority will become {4:D}, {3:E}, {2:B}
Put (key 1, value A): Since our cache is FULL, so use our LRU algorithm to determine which key was least recently used, and since {2:B} had the least priority, remove {2:B} from our cache and put {1:A} into the cache. Now, the new priority order is {1:A}, {4:D}, {3:E}

Ways to Implement LRU Cache:

LRU cache can be implemented in a variety of ways, and each programmer may choose a different approach. However, below are commonly used approaches:

LRU using Queue and Hashing
LRU using Doubly Linked List + Hashing
LRU using Deque
LRU using Stack
LRU using Counter implementation
LRU using Lazy Updates

LRU cache implementation using Queue and Hashing:

We use two data structures to implement an LRU Cache.

Queue is implemented using a doubly-linked list. The maximum size of the queue will be equal to the total number of frames available (cache size). The most recently used pages will be near the front end and the least recently used pages will be near the rear end.

A Hash with the page number as key and the address of the corresponding queue node as value.

When a page is referenced, the required page may be in the memory. If it is in the memory, we need to detach the node of the list and bring it to the front of the queue.
If the required page is not in memory, we bring that in memory. In simple words, we add a new node to the front of the queue and update the corresponding node address in the hash. If the queue is full, i.e. all the frames are full, we remove a node from the rear of the queue, and add the new node to the front of the queue.

Illustration:

Let’s Consider the operations, Refers key x with in the LRU cache: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Note: Initially no page is in the memory.

Below images shows step by step execution of the above operations on the LRU cache.

Algorithm:

Create a class LRUCache with declare a list of type int, an unordered map of type <int, list<int>>, and a variable to store the maximum size of the cache
In the refer function of LRUCache
- If this value is not present in the queue then push this value in front of the queue and remove the last value if the queue is full
- If the value is already present then remove it from the queue and push it in the front of the queue
In the display function print, the LRUCache using the queue starting from the front

Below is the implementation of the above approach:

C++

// We can use stl container list as a double 
// ended queue to store the cache keys, with 
// the descending time of reference from front 
// to back and a set container to check presence 
// of a key. But to fetch the address of the key 
// in the list using find(), it takes O(N) time. 
// This can be optimized by storing a reference 
//     (iterator) to each key in a hash map. 
#include <bits/stdc++.h> 
using namespace std; 
  
class LRUCache { 
    // store keys of cache 
    list<int> dq; 
  
    // store references of key in cache 
    unordered_map<int, list<int>::iterator> ma; 
    int csize; // maximum capacity of cache 
  
public: 
    LRUCache(int); 
    void refer(int); 
    void display(); 
}; 
  
// Declare the size 
LRUCache::LRUCache(int n) { csize = n; } 
  
// Refers key x with in the LRU cache 
void LRUCache::refer(int x) 
{ 
    // not present in cache 
    if (ma.find(x) == ma.end()) { 
        // cache is full 
        if (dq.size() == csize) { 
            // delete least recently used element 
            int last = dq.back(); 
  
            // Pops the last element 
            dq.pop_back(); 
  
            // Erase the last 
            ma.erase(last); 
        } 
    } 
  
    // present in cache 
    else
        dq.erase(ma[x]); 
  
    // update reference 
    dq.push_front(x); 
    ma[x] = dq.begin(); 
} 
  
// Function to display contents of cache 
void LRUCache::display() 
{ 
  
    // Iterate in the deque and print 
    // all the elements in it 
    for (auto it = dq.begin(); it != dq.end(); it++) 
        cout << (*it) << " "; 
  
    cout << endl; 
} 
  
// Driver Code 
int main() 
{ 
    LRUCache ca(4); 
  
    ca.refer(1); 
    ca.refer(2); 
    ca.refer(3); 
    ca.refer(1); 
    ca.refer(4); 
    ca.refer(5); 
    ca.display(); 
  
    return 0; 
} 
// This code is contributed by Satish Srinivas

C

// A C program to show implementation of LRU cache 
#include <stdio.h> 
#include <stdlib.h> 
  
// A Queue Node (Queue is implemented using Doubly Linked 
// List) 
typedef struct QNode { 
    struct QNode *prev, *next; 
    unsigned 
        pageNumber; // the page number stored in this QNode 
} QNode; 
  
// A Queue (A FIFO collection of Queue Nodes) 
typedef struct Queue { 
    unsigned count; // Number of filled frames 
    unsigned numberOfFrames; // total number of frames 
    QNode *front, *rear; 
} Queue; 
  
// A hash (Collection of pointers to Queue Nodes) 
typedef struct Hash { 
    int capacity; // how many pages can be there 
    QNode** array; // an array of queue nodes 
} Hash; 
  
// A utility function to create a new Queue Node. The queue 
// Node will store the given 'pageNumber' 
QNode* newQNode(unsigned pageNumber) 
{ 
    // Allocate memory and assign 'pageNumber' 
    QNode* temp = (QNode*)malloc(sizeof(QNode)); 
    temp->pageNumber = pageNumber; 
  
    // Initialize prev and next as NULL 
    temp->prev = temp->next = NULL; 
  
    return temp; 
} 
  
// A utility function to create an empty Queue. 
// The queue can have at most 'numberOfFrames' nodes 
Queue* createQueue(int numberOfFrames) 
{ 
    Queue* queue = (Queue*)malloc(sizeof(Queue)); 
  
    // The queue is empty 
    queue->count = 0; 
    queue->front = queue->rear = NULL; 
  
    // Number of frames that can be stored in memory 
    queue->numberOfFrames = numberOfFrames; 
  
    return queue; 
} 
  
// A utility function to create an empty Hash of given 
// capacity 
Hash* createHash(int capacity) 
{ 
    // Allocate memory for hash 
    Hash* hash = (Hash*)malloc(sizeof(Hash)); 
    hash->capacity = capacity; 
  
    // Create an array of pointers for referring queue nodes 
    hash->array 
        = (QNode**)malloc(hash->capacity * sizeof(QNode*)); 
  
    // Initialize all hash entries as empty 
    int i; 
    for (i = 0; i < hash->capacity; ++i) 
        hash->array[i] = NULL; 
  
    return hash; 
} 
  
// A function to check if there is slot available in memory 
int AreAllFramesFull(Queue* queue) 
{ 
    return queue->count == queue->numberOfFrames; 
} 
  
// A utility function to check if queue is empty 
int isQueueEmpty(Queue* queue) 
{ 
    return queue->rear == NULL; 
} 
  
// A utility function to delete a frame from queue 
void deQueue(Queue* queue) 
{ 
    if (isQueueEmpty(queue)) 
        return; 
  
    // If this is the only node in list, then change front 
    if (queue->front == queue->rear) 
        queue->front = NULL; 
  
    // Change rear and remove the previous rear 
    QNode* temp = queue->rear; 
    queue->rear = queue->rear->prev; 
  
    if (queue->rear) 
        queue->rear->next = NULL; 
  
    free(temp); 
  
    // decrement the number of full frames by 1 
    queue->count--; 
} 
  
// A function to add a page with given 'pageNumber' to both 
// queue and hash 
void Enqueue(Queue* queue, Hash* hash, unsigned pageNumber) 
{ 
    // If all frames are full, remove the page at the rear 
    if (AreAllFramesFull(queue)) { 
        // remove page from hash 
        hash->array[queue->rear->pageNumber] = NULL; 
        deQueue(queue); 
    } 
  
    // Create a new node with given page number, 
    // And add the new node to the front of queue 
    QNode* temp = newQNode(pageNumber); 
    temp->next = queue->front; 
  
    // If queue is empty, change both front and rear 
    // pointers 
    if (isQueueEmpty(queue)) 
        queue->rear = queue->front = temp; 
    else // Else change the front 
    { 
        queue->front->prev = temp; 
        queue->front = temp; 
    } 
  
    // Add page entry to hash also 
    hash->array[pageNumber] = temp; 
  
    // increment number of full frames 
    queue->count++; 
} 
  
// This function is called when a page with given 
// 'pageNumber' is referenced from cache (or memory). There 
// are two cases: 
// 1. Frame is not there in memory, we bring it in memory 
// and add to the front of queue 
// 2. Frame is there in memory, we move the frame to front 
// of queue 
void ReferencePage(Queue* queue, Hash* hash, 
                   unsigned pageNumber) 
{ 
    QNode* reqPage = hash->array[pageNumber]; 
  
    // the page is not in cache, bring it 
    if (reqPage == NULL) 
        Enqueue(queue, hash, pageNumber); 
  
    // page is there and not at front, change pointer 
    else if (reqPage != queue->front) { 
        // Unlink rquested page from its current location 
        // in queue. 
        reqPage->prev->next = reqPage->next; 
        if (reqPage->next) 
            reqPage->next->prev = reqPage->prev; 
  
        // If the requested page is rear, then change rear 
        // as this node will be moved to front 
        if (reqPage == queue->rear) { 
            queue->rear = reqPage->prev; 
            queue->rear->next = NULL; 
        } 
  
        // Put the requested page before current front 
        reqPage->next = queue->front; 
        reqPage->prev = NULL; 
  
        // Change prev of current front 
        reqPage->next->prev = reqPage; 
  
        // Change front to the requested page 
        queue->front = reqPage; 
    } 
} 
  
// Driver code 
int main() 
{ 
    // Let cache can hold 4 pages 
    Queue* q = createQueue(4); 
  
    // Let 10 different pages can be requested (pages to be 
    // referenced are numbered from 0 to 9 
    Hash* hash = createHash(10); 
  
    // Let us refer pages 1, 2, 3, 1, 4, 5 
    ReferencePage(q, hash, 1); 
    ReferencePage(q, hash, 2); 
    ReferencePage(q, hash, 3); 
    ReferencePage(q, hash, 1); 
    ReferencePage(q, hash, 4); 
    ReferencePage(q, hash, 5); 
  
    // Let us print cache frames after the above referenced 
    // pages 
    printf("%d ", q->front->pageNumber); 
    printf("%d ", q->front->next->pageNumber); 
    printf("%d ", q->front->next->next->pageNumber); 
    printf("%d ", q->front->next->next->next->pageNumber); 
  
    return 0; 
}

Java

/* We can use Java inbuilt Deque as a double 
   ended queue to store the cache keys, with 
   the descending time of reference from front 
   to back and a set container to check presence 
   of a key. But remove a key from the Deque using 
   remove(), it takes O(N) time. This can be 
   optimized by storing a reference (iterator) to 
   each key in a hash map. */
import java.util.Deque; 
import java.util.HashSet; 
import java.util.Iterator; 
import java.util.LinkedList; 
  
public class LRUCache { 
  
    // store keys of cache 
    private Deque<Integer> doublyQueue; 
  
    // store references of key in cache 
    private HashSet<Integer> hashSet; 
  
    // maximum capacity of cache 
    private final int CACHE_SIZE; 
  
    LRUCache(int capacity) 
    { 
        doublyQueue = new LinkedList<>(); 
        hashSet = new HashSet<>(); 
        CACHE_SIZE = capacity; 
    } 
  
    /* Refer the page within the LRU cache */
    public void refer(int page) 
    { 
        if (!hashSet.contains(page)) { 
            if (doublyQueue.size() == CACHE_SIZE) { 
                int last = doublyQueue.removeLast(); 
                hashSet.remove(last); 
            } 
        } 
        else { /* The found page may not be always the last 
                element, even if it's an intermediate 
                element that needs to be removed and added 
                to the start of the Queue */
            doublyQueue.remove(page); 
        } 
        doublyQueue.push(page); 
        hashSet.add(page); 
    } 
  
    // display contents of cache 
    public void display() 
    { 
        Iterator<Integer> itr = doublyQueue.iterator(); 
        while (itr.hasNext()) { 
            System.out.print(itr.next() + " "); 
        } 
    } 
  
      // Driver code 
    public static void main(String[] args) 
    { 
        LRUCache cache = new LRUCache(4); 
        cache.refer(1); 
        cache.refer(2); 
        cache.refer(3); 
        cache.refer(1); 
        cache.refer(4); 
        cache.refer(5); 
        cache.display(); 
    } 
} 
// This code is contributed by Niraj Kumar

Python3

# We can use stl container list as a double 
# ended queue to store the cache keys, with 
# the descending time of reference from front 
# to back and a set container to check presence 
# of a key. But to fetch the address of the key 
# in the list using find(), it takes O(N) time. 
# This can be optimized by storing a reference 
# (iterator) to each key in a hash map. 
class LRUCache: 
    # store keys of cache 
    def __init__(self, n): 
        self.csize = n 
        self.dq = [] 
        self.ma = {} 
  
  
    # Refers key x with in the LRU cache 
    def refer(self, x): 
          
        #  not present in cache 
        if x not in self.ma.keys(): 
            # cache is full 
            if len(self.dq) == self.csize: 
                # delete least recently used element 
                last = self.dq[-1] 
  
                # Pops the last element 
                ele = self.dq.pop(); 
  
                # Erase the last 
                del self.ma[last] 
  
        # present in cache 
        else: 
            del self.dq[self.ma[x]] 
  
        # update reference 
        self.dq.insert(0, x) 
        self.ma[x] = 0; 
  
    # Function to display contents of cache 
    def display(self): 
  
        # Iterate in the deque and print 
        # all the elements in it 
        print(self.dq) 
  
# Driver Code 
ca = LRUCache(4) 
  
ca.refer(1) 
ca.refer(2) 
ca.refer(3) 
ca.refer(1) 
ca.refer(4) 
ca.refer(5) 
ca.display() 
# This code is contributed by Satish Srinivas 

C#

// C# program to implement the approach 
  
using System; 
using System.Collections.Generic; 
  
class LRUCache { 
    // store keys of cache 
    private List<int> doublyQueue; 
  
    // store references of key in cache 
    private HashSet<int> hashSet; 
  
    // maximum capacity of cache 
    private int CACHE_SIZE; 
  
    public LRUCache(int capacity) 
    { 
        doublyQueue = new List<int>(); 
        hashSet = new HashSet<int>(); 
        CACHE_SIZE = capacity; 
    } 
  
    /* Refer the page within the LRU cache */
    public void Refer(int page) 
    { 
        if (!hashSet.Contains(page)) { 
            if (doublyQueue.Count == CACHE_SIZE) { 
                int last 
                    = doublyQueue[doublyQueue.Count - 1]; 
                doublyQueue.RemoveAt(doublyQueue.Count - 1); 
                hashSet.Remove(last); 
            } 
        } 
        else { 
            /* The found page may not be always the last 
               element, even if it's an intermediate 
               element that needs to be removed and added 
               to the start of the Queue */
            doublyQueue.Remove(page); 
        } 
        doublyQueue.Insert(0, page); 
        hashSet.Add(page); 
    } 
  
    // display contents of cache 
    public void Display() 
    { 
        foreach(int page in doublyQueue) 
        { 
            Console.Write(page + " "); 
        } 
    } 
  
    // Driver code 
    static void Main(string[] args) 
    { 
        LRUCache cache = new LRUCache(4); 
        cache.Refer(1); 
        cache.Refer(2); 
        cache.Refer(3); 
        cache.Refer(1); 
        cache.Refer(4); 
        cache.Refer(5); 
        cache.Display(); 
    } 
} 
  
// This code is contributed by phasing17

Javascript

// JS code to implement the approach 
class LRUCache { 
  constructor(n) { 
    this.csize = n; 
    this.dq = []; 
    this.ma = new Map(); 
  } 
  
  refer(x) { 
    if (!this.ma.has(x)) { 
      if (this.dq.length === this.csize) { 
        const last = this.dq[this.dq.length - 1]; 
        this.dq.pop(); 
        this.ma.delete(last); 
      } 
    } else { 
      this.dq.splice(this.dq.indexOf(x), 1); 
    } 
  
    this.dq.unshift(x); 
    this.ma.set(x, 0); 
  } 
  
  display() { 
    console.log(this.dq); 
  } 
} 
  
const cache = new LRUCache(4); 
  
cache.refer(1); 
cache.refer(2); 
cache.refer(3); 
cache.refer(1); 
cache.refer(4); 
cache.refer(5); 
cache.display(); 
  
// This code is contributed by phasing17

LRU cache implementation using Doubly Linked List and Hashing:

The idea is very basic, i.e. keep inserting the elements at the head.

if the element is not present in the list then add it to the head of the list

if the element is present in the list then move the element to the head and shift the remaining element of the list

Note that the priority of the node will depend upon the distance of that node from the Head, the closest the node is to the head, higher the priority it has. So when the Cache size is full and we need to remove some element, we remove the element adjacent to the tail of the doubly linked list.

LRU cache implementation using Deque & Hashmap:

Deque data structure allows insertion and deletion from front as well as end, this property allows the implementation of LRU possible as Front element can represent high priority element while the end element can be the low priority element i.e. Least Recently used.

Working:

Get Operation: Checks if the key exist in the cache’s hash map and follow the below cases on the deque:

If key is found:

The item is considered as recently used, so it is moved to the front of the deque.

The value associated with the key is returned as the result of the get operation.

If key is not found:

return -1 to indicate no such key is present.

Put Operation: First check if the key already exists in the cache’s hash map and follow the below cases on the deque

If key exists:

The value associated with the key is updated.

The item is moved to the front of the deque since it’s now the most recently used.

If key does not exist:

If the cache is full, it means a new item needs to be inserted, and the least recently used item must be evicted. This is done by removing the item from the end of the deque and the corresponding entry from the hash map.

The new key-value pair is then inserted into both the hash map and the front of the deque to signify that it’s the most recently used item

LRU cache implementation using Stack & Hashmap:

Implementing an LRU (Least Recently Used) cache using a stack data structure and hashing can be a bit tricky because a simple stack doesn’t provide efficient access to the least recently used item. However, you can combine a stack with a hash map to achieve this efficiently. Here’s a high-level approach to implement it:

Use a Hash Map: The hash map will store the key-value pairs of the cache. The keys will map to the corresponding nodes in the stack.

Use a Stack: The stack will maintain the order of keys based on their usage. The least recently used item will be at the bottom of the stack, and the most recently used item will be at the top

This approach is not that efficient and hence not used often.

LRU cache using Counter Implementation:

Each block in the cache will have its own LRU Counter where the value of the counter belongs to {0 to n-1}, here ‘n‘ represents the size of the cache. The block that is changed during block replacement becomes the MRU block, and as a result, its counter value is changed to n – 1. The counter values greater than the accessed block’s counter value are decremented by one. The remaining blocks are unaltered.

Value of Conter	Priority	Used status
0	Low	Least Recently used
n-1	High	Most Recently used

LRU cache implementation using Lazy Updates:

Implementing an LRU (Least Recently Used) cache using lazy updates is a common technique to improve the efficiency of the cache’s operations. Lazy updates involve tracking the order in which items are accessed without immediately updating the entire data structure. When a cache miss occurs, you can then decide whether or not to perform a full update based on some criteria.

Complexity Analysis of LRU Cache:

Time Complexity:
- Put() operation: O(1) i.e. time required to insert or update new key-value pair is constant
- Get() operation: O(1) i.e. time required to get the value of a key is constant
Auxiliary Space: O(N) where N is the capacity of the Cache.

Advantages of LRU cache:

Fast Access: It takes O(1) time to access the data from the LRU cache.
Fast Update: It takes O(1) time to update a key-value pair in the LRU cache.
Fast removal of Least recently used data: It takes O(1) delete that which has not been recently used.
No thrashing: LRU is less susceptible to thrashing compared to FIFO because it considers the usage history of pages. It can detect which pages are being used frequently and prioritize them for memory allocation, reducing the number of page faults and disk I/O operations.

Disadvantages of LRU cache:

It requires large cache size to increase efficiency.
It requires additional Data Structure to be implemented.
Hardware assistance is high.
In LRU error detection is difficult as compared to other algorithms.
It has limited acceptability.

Real-World Application of LRU Cache:

In Database Systems for fast query results.
In Operating Systems to minimize page faults.
Text Editors and IDEs to store frequently used files or code snippets
Network routers and switches use LRU to increase the efficiency of computer network
In compiler optimizations
Text Prediction and autocompletion tools

Suggest improvement

How to efficiently implement k Queues in a single array?

Detect cycle in an undirected graph using BFS

Share your thoughts in the comments

Queue implementation in different languages

Some question related to Queue implementation

Easy problems on Queue

Intermediate problems on Queue

Hard problems on Queue