LRU Caching Implementation

In this blog we will see the implementation of LRU(Least recently used) cache.
I have explained 3 different implementations with code. Programming logic in Java is provided along with the inline comments which explains every block of code.

The first implementation is using a double linked list

The 2nd implementation is using double linked list and a HashSet

The 3rd implementation is using a LinkedHashSet

Some important points about the Data Structures that we are going to use :

Double linked list :

1. We can traverse the list both in forward and backward direction
2. We can insert and delete elements from the list from both ends.
3. To delete/find any element it will take O(n) worst case time complexity

HashSet

1. We can find and delete any element in O(1) time complexity.
2. Order of elements is not maintained

LinkedHashSet

1. We can traverse the list both in forward and backward direction.
2. Maintains the order of elements.
3. We can find and delete any element in O(1) time complexity.

What is LRU ? Least Recently Used

An LRU implementation of caching mechanism, organizes items in their order of use. The recently used item will be at the top, and the least recently used item will be at the end.

Say that you have a rack of books, the books you used recently will be at the top, while the books which you haven’t looked at recently, will be at the end of the queue. So this is what an LRU is.

Implementation using Doubly Linked List :

In this implementation, we insert an element at the beginning of the queue (linkedlist works as a queue in our program). If the element is already present, we remove it from the queue and insert it at the beginning because this element is recently used. If we are trying to insert an element and the size of the queue is full, then we remove the last element, and add the element at the beginning.

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * This program uses a Deque
 * so that inserrion and deletion can be
 * done from both ends
 * We will use LinkedList as the implementation class
 */
public class LRUCache {

    Deque cache; // a double ended queue to store cache values
    Integer cache_size; // to find the number of elements in cache

    public static void main(String args[]) {
       //// we are taking 4 as capacity
        LRUCache lruCache = new LRUCache(4); 
        lruCache.put(1);
        // 1
        lruCache.put(2);
        // 2 -> 1
        lruCache.put(3);
        // 3 -> 2 -> 1
        lruCache.put(4);
        // 4 -> 3 -> 2 -> 1
        lruCache.put(2);
        // first 2 is removed because it is found
        // 4 -> 3 -> 1
        // 2 is the most recently used so 
        //it must exist on top of a queue
        // 2 -> 4 -> 3 -> 1
        lruCache.put(5);
        // size of queue = 4, so remove last element which is 1
        // 2 -> 4 -> 3
        // 5 -> 2 -> 4 -> 3
        lruCache.print();// should  print 5 2 4 3
    }

    LRUCache(Integer capacity) {
     cache = new LinkedList<Integer>();
     cache_size = capacity;
    }

    // inserts element to queue
    void put(int num) {
        // checks if element exists, if yes
        // deletes the element and returns true
        // or else returns false
        boolean elementExists = cache.removeFirstOccurrence(num);
        if(!elementExists) {
            // if element does not exist

            // and capacity of queue = number of elements in queue
            // then remove the least recently used element
            // which is the last element on queue
            if(cache_size == cache.size()) {
                cache.removeLast();
            }
        }
        // just add the element at the beginning of a queue
        cache.addFirst(num);
    }

    // prints the content of the queue
    void print() {
        Iterator iterate = cache.iterator();
        while(iterate.hasNext()) {
            System.out.println(iterate.next());
        }
    }

}

Implementation using Doubly Linked List and a HashSet :

We already achieved this using the Doubly linked list above. So why a HashSet ?

A HashSet is used so that we can manage the time complexity effectively.This particular statement is executed in O(1) worst case. Correct ?

hashSet.contains(number)

So instead of trying to find an element directly in linkedlist which takes O(n) worst case time complexity, we will first see if it exists in the linkedlist by maintaining all the elements in HashSet as well. If the element exists in a hashset, only then we will try and remove it from linked list.

package com.mycompany.app.LRUCache;

import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;


/**
 * This program would use double ended queue i.e.Deque
 * We will use Linked list as the implementation details,
 * as Deque is an interface
 * We will also use a HashSet.  Why ?
 * To decrease the time complexity of the program. How ?
 * To find an element if it exists in linkedlist, it takes O(n)
 * as worst case time complexity.
 * So before actually finding an element
 * we will also maintain a hashset which has O(1) time complexity
 * to find any element. Hence before deleting any element 
 * from  linkedlist
 * we will check if the item actually exists in the list
 * by maintaining a hashset
 * We do increase the space complexity, however less
 * time complexity makes up for it
 *
 */
public class LRUCacheWithHashSet {
    Deque cache; // a double ended queue to store cache values
    Integer cache_size; // to find the number of elements in cache
    HashSet hashSet; // used so that time complexity is less
    public static void main(String args[]) {
        LRUCacheWithHashSet lruCacheWithHashSet = 
          new LRUCacheWithHashSet(4); // we are taking 4 as capacity
        lruCacheWithHashSet.put(1);
        // 1
        lruCacheWithHashSet.put(2);
        // 2 -> 1
        lruCacheWithHashSet.put(3);
        // 3 -> 2 -> 1
        lruCacheWithHashSet.put(4);
        // 4 -> 3 -> 2 -> 1
        lruCacheWithHashSet.put(2);
        // first 2 is removed because it is found
        // 4 -> 3 -> 1
        // 2 is the most recently used 
        //so it must exist on top of a queue
        // 2 -> 4 -> 3 -> 1
        lruCacheWithHashSet.put(5);
        // size of queue = 4, so remove last element which is 1
        // 2 -> 4 -> 3
        // add 5 at the beginning of queue
        // 5 -> 2 -> 4 -> 3
        lruCacheWithHashSet.print();// should  print 5 2 4 3
    }

    LRUCacheWithHashSet(Integer capacity) {
        cache = new LinkedList<Integer>();
        hashSet = new HashSet<Integer>(capacity);
        cache_size = capacity;
    }

    // inserts element to queue
    void put(int num) {
        // checks if element exists, if yes in hashset
        // if yes remove from list
        // or else 
        // check if the capacity = number of elements in list
        // if yes remove least recently used element 
        // i.e last element
        if(hashSet.contains(num)) {
            cache.removeFirstOccurrence(num);
        } else {
            if(cache_size == cache.size()) {
                cache.removeLast();
            }
        }
        // just add the element at the beginning of a queue
        hashSet.add(num);
        cache.addFirst(num);
    }

    // prints the content of the queue
    void print() {
        Iterator iterate = cache.iterator();
        while(iterate.hasNext()) {
            System.out.println(iterate.next());
        }
    }

}

Implementation using LinkedHashSet :

A LinkedHashSet can find/delete any element in O(1) time, and this data structure also maintains the order of inserted elements. This is similar to using LinkedList and HashSet together. In the above implementation, we used 2 data structures, with this implementation, the same can be achieved using just 1 Data Structure.

package com.mycompany.app.LRUCache;

import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;

/**
 * Here we will be using LinkedHashSet as the implementation detail
 * We can directly find an element on LinkedHashSet in O(1)
 * So that will save time while deleting any element
 * as we will not traverse the entire hashset
 */
public class LRUCacheWithLinkedHashSet {

    Set cache; // We will use a set
    Integer cache_size; // number of elements in the Set

    public static void main(String args[]) {
        LRUCacheWithHashSet lruCacheWithHashSet = 
            new LRUCacheWithHashSet(4);
        lruCacheWithHashSet.put(1);
        lruCacheWithHashSet.put(2);
        lruCacheWithHashSet.put(3);
        lruCacheWithHashSet.put(4);
        lruCacheWithHashSet.put(2);
        lruCacheWithHashSet.put(5);

        lruCacheWithHashSet.print(); // should print 5 2 4 3
    }

    LRUCacheWithLinkedHashSet(int capacity) {
      cache = new LinkedHashSet<Integer>();
      cache_size = capacity;
    }

    void put(int num) {
        if(cache.contains(num)) {
            cache.remove(num);
        }
        if(cache.size() == cache_size) {
            Integer value = (Integer) cache.iterator().next();
            System.out.println(value);
            cache.remove(value);
        }
        cache.add(num);
    }

    void print() {
        Iterator iterate = cache.iterator();
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
        }
    }
}

Conclusion :
Hope the article was clear and self explanatory on the implementation of LRU. Please reach out to me for any freelancing work.