A cache is a just small storage that enables fast access to users. The size of a cache is small (fixed mostly), which lets the user read data from a cache is very little time rather than reading it from something else (like a hard disk).

A Least Recently Used (LRU) Cache organizes items in order of use, allowing you to quickly identify which item hasn't been used for the longest amount of time and if the size overflows it deletes the least recently used item.

In this article, we will look into the implementation of LRU Cache, with the use of the data structures i.e. hashmap and doubly linked list. This article assumes the basic knowledge of these data structures, if you lack that refer to this link ( Link ) before going through this article.

Objective: Design and accomplish a data structure for Least Recently Used (LRU) cache. Here we are given the task to make a class called LRU cache which has a fixed size and will store data and consists of two functions get and set which are both expected O(1).

get(x): Returns the value of the key x if the key subsists in the cache otherwise returns -1.

set(x,y): inserts the value if the key x is not previously present. If the cache reaches its capacity it should remove the least recently used item before inserting the new item. In the constructor of the class, the size of the cache should be initialized.

Syntax	Description	Need	Data Structure
get(x)	O(1)	Fast LookUps	HashMap
set(x,y)	O(1)	Fast Removals	Doubly Linked-List

Why HashMap?

Since for implementing the get(x) function we only need to return the value for the key provided in the argument (i.e x) in O(1) time. So for storing the key-value pairs and accessing the values in O(1) time, the best suitable data structure will be a hashmap (Fast Lookups).

So we will build a hashmap in the LRU class set function and will simply return the value if the key is present in the HashMap or return -1.

Why are we using Doubly Linked List?

Variable Size:- Since we need a linear data structure having a variable size. So a linked list will suit well, where we can add elements at any point in O(1) time.

Fast Removal:- If we have instant access to a doubly-linked list node, we can delete that node in constant time with the help of the previous and next pointers, while in a singly linked list we don't have access to the previous pointer so forgetting that we have to travel throughout the list which costs O(N) time.

Application:- The doubly linked list will store the element from the front to the back according to the use of the elements. The first element shows the most recently used element while the last shows the least frequently used element.

Solution Method:-

• get(x):- here we handle two cases:-

Case 1: If the element is present, then we first remove the key from the linked list and insert it in the front, and then we just return the value of the corresponding value from the hashMap.

Case 2: If the element is not present in the hashmap just return -1.

• set(x,y):- Looking into the complexities for the set function we need to ensure 3 cases for every insertion in the function:-

Case 1: If the current size of the cache is less than the maximum capacity of the cache.

• Insert the key-value pair in the hashmap.
• Increase the current size.
• Put the key in front of the associated doubly linked list.

Case 2: If the size of the cache already has reached its maximum capacity then we need to delete the least recently used key-value pair.

• Remove the last element of the list, which is the least recently used key.
• Remove the corresponding key-value pair from the hashmap.
• Insert the new key-value pair in the hashmap and put it in the front of the list.

Case 3: If the element’s key is already present in the hashmap.

• Update the value of the corresponding key in the hashmap.
• Remove the key from the list.
• Add the key to the front of the list, since it’s the most recently used cache.

Implementation in Java:-

We first build the helper classes i.e. Doubly linked list and Node class, and then we will code the main LRU Class.

Node Class:-

The class would have one parameter consisting of data(key) and two pointers prev and next so as to be a part of a doubly linked list.

class Node{
    int data;          // Key data
    Node next;      // next node pointer
    Node prev;       // previous node pointer
    public Node(int d){
        data=d;
        next=null;
        prev=null;
    }
}

Doubly Linked List Class

class dll{
     Node tail;    //end pointer
     Node head;  //head pointer
     public dll(){       //Initialisation of tail and head to null
         tail=null;
         head=null;
     }
// insertStart() method puts the key d in the front of the list
 public  void insertStart(int d){
         if(head==null){
             tail=new Node(d);
             head=tail;
         }
         else{

             head.prev=new Node(d);
             head.prev.next=head;
             head=head.prev;
         }
     }
// removeEnd() method removes the last element at constant time.
     public  int removeEnd(){
         int temp=tail.data;
         tail=tail.prev;
         if(tail!=null) tail.next=null;
         else head=tail;
         return(temp);
     }


 public  void remove(Node temp){

// remove(d) function first find the node with data d and then delete in 
// constant time, since the size of the list is fixed searching will yield O(1).

            if(temp!=null){
             if(temp==head){
                 head=head.next;
                 if(head!=null) head.prev=null;
                 else tail=null;
             }
             else if(temp==tail){
                 removeEnd();
             }
             else{
                 temp.prev.next=temp.next;
                 temp.next.prev=temp.prev;

             }
         }

     }
  }

LRU Cache Class Code in Java:-

class LRUCache
{
    // constructor for cache
    int cursize;
    int maxSize;
    HashMap<Integer,Integer> map; 
    HashMap<Integer,Node> check;
    dll que; 

    LRUCache(int cap)
    {
        // Initialize the cache capacity with the given
        // cap
        cursize=0;
        maxSize= cap;
        this.map = new HashMap<Integer,Integer>(); 
        this.que=new dll();
    }

 // this function return the value corresponding to a key if present else  /      // -1
     int get(int key)
    {
        if(this.map.containsKey(key)){    //checking if key is present or not
            this.que.remove(check.get(key));            // removing the key from queue
            this.que.insertStart(key);       // putting the key in front
    this.check.put(key,this.que.head);
            return(this.map.get(key));
        }
        return(-1);
    }

    // storing key, value pair
     void set(int key, int value)
    {
        if(this.map.containsKey(key)){  // if the key is already present
            this.map.put(key,value);       // updating value for that key
           this.que.remove(check.get(key));     // removing the key from list
            this.que.insertStart(key);       // inserting it in front
           this.check.put(key,this.que.head); 
return;
        }
if(cursize<maxSize){            // if size is less than maxsize 
                                 //simply insert elements
         this.map.put(key,value);
         cursize++;
         this.que.insertStart(key);               // put the key in front
this.check.put(key,this.q.head);        
}
        else{
     // If the size is full remove the last element of the list which is the LRU
            int p=this.que.removeEnd();
            this.check.remove(p);
            this.map.remove(p);
            this.que.insertStart(key);
            this.check.put(key,this.que.head);
            this.map.put(key,value);
        }
    }
}

Explanation with Example:-

Input :-

Max capacity = 2
set(1, 4) set(2, 7) get(2) // returns 7 get(1) //returns 4 get(5) //returns -1 set(7, 21) //this will remove key = 2 as LRU is full and key=2 is least recently used. get(2) //returns -1

The output of the Cache:- 7 4 -1 -1.

Explanation:

• Max Capacity = 2 ; This will initialise the LRU Cache with maxSize=2 and cursize = 0 and will also initialise the hashmap (map) and dll(que). cursize=0 map->null que-> null

• set(1,4): Since the key is not present in map, and the cursize(0) {1,4} que-> 1

• set(2,7): Since the key is not present in map, and the cursize(1) {1,4} , {2,7} que-> 2 , 1

• get(2): Since the map contains the key=2, it will first remove the key from the que and then insert it in front and then return the corresponding value. Returns -> 7 map-> {1,4} , {2,7} que-> 2 , 1

• get(1): Since the map contains the key=1, it will first remove the key from the que and then insert it in front and then return the corresponding value. Returns -> 4 map-> {1,4} , {2,7} que-> 1 , 2

• get(5): Since the map doesn’t contain any key=5, the function will simply return -1.
  Returns -> -1 map-> {1,4} , {2,7} que-> 1 , 2

• set(7,21) : Since the key is not present in map but the (cursize(2)=maxSize(2)), Thus the function will first remove the end key from the que and then remove the corresponding key-value pair from the map. After removal, the new key-value pair is added to the map and the key is put in front of que.

  cursive=2 map-> {7,21} , {1,4} que-> 7 , 1

• get(2) : Since now the map doesn’t contain any key=2, the function will simply return -1. Returns -> -1 map-> {7,21} , {1,4} que-> 7 , 1.

Thus the output: 7 4 -1 -1.