LRU and MRU Cache Implementation

Modern Operating system keeps recently used files in the cache. but the size of the computer cache is limited. so the operating system has to manage cache memory so that it can store new files and remove unwanted or least-used files. The primary candidate for removal is the file that has not been used recently. the algorithm used to manage cache memory is LRU or Least Recently Used and the file on top of the cache is MRU or Most Recently Used.

LRU and MRU are cache eviction policy that removes the least or most recently used cached data as per requirement

The LRU is an acronym for Least Recently Used Cache and MRU is the acronym for Most Recently Used. The Recently Used cache which just gets inserted in the cache or reused is MRU, and if it was not used for a while or used very lately, then is known as LRU Cache.

A Cache has 2 important methods, put to insert key and value in cache and get to retrieve the key from the cache. let's understand both.

Cache Put

put method is used to insert keys and values in the cache. at the time of insertion, there can be 2 scenarios.

The key is present in the cache

if the Cache contains the key, then do nothing.
check if the key present in the Cache has the same value, else update if the key is not present in the Cache and return.

The key is not present in the cache

Cache doesn't contain the key, so now we need to add the key in the Doubly linked list at the rightmost end, and make it mostRecentlyUsed.
add the new Node at the right-most end of the Linked List as the next of mostRecentlyUsed, the new Node will become the mostRecentlyUsed.
check if Cache size has reached max size
if yes then delete the leastRecentlyUsed from the map and update the head of leastRecentlyUsed with its next.
else increase the cache size.
if the current size is 0, it means this is the first node, hence mark new Node as leastRecentlyUsed

Cache Get

if the key is not present in Cache, then return null.
If the key is the mostRecentlyUsed ie already at end of the Linked List, then do nothing.
if the key is present in the Cache and is not mostRecentlyUsed, so we need to update its position, we already checked it's not at the rightmost end or mostRecentlyUsed, it means It's either at the leftmost end ie leastRecentlyUsed or in middle, for both conditions, we need to make it mostRecentlyUsed.
if the key is at the leftmost or is leastRecentlyUsed, then is we need to remove it from here and put it at rightmost or make it mostRecentlyUsed, so update leastRecentlyUsed The Key is present in Cache and is not at the left end or leastRecentlyUsed, which means it's in middle, so we need to update its position, remove from the current location and put in the rightmost end or make it mostRecentlyUsed
the Key is present in the cache and is not at the left end or leastRecentlyUsed, which means it's in middle, so we need to update its position, remove it from the current location and put it in the rightmost end or make it mostRecentlyUsed.

lets see LRU and MRU cache implementation

package org.wesome.dsalgo;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.HashMap;
import java.util.Objects;

@Data
@AllArgsConstructor
@NoArgsConstructor
class Node<K, V> {
    Node<K, V> previous;
    Node<K, V> next;
    K key;
    V value;
}

@Data
public class LRUCache<K, V> {
    private HashMap<K, Node<K, V>> cacheMap;
    private Node<K, V> leastRecentlyUsed;
    private Node<K, V> mostRecentlyUsed;
    private int maxSize;
    private int currentSize;

    public LRUCache(int maxSize) {
        this.maxSize = maxSize;
        this.currentSize = 0;
        leastRecentlyUsed = new Node<>();
        /*  currently, both ends of the Deque will be the same, ie head and end both are same, so leastRecentlyUsed is mostRecentlyUsed   */
        mostRecentlyUsed = leastRecentlyUsed;
        cacheMap = new HashMap<>();
    }

    public V get(K key) {
        Node<K, V> tempNode = cacheMap.get(key);
        /*  if the key is not present in cacheMap, then return null */
        if (Objects.isNull(tempNode)) {
            return null;
        }
        /*   If the key is the mostRecentlyUsed ie already at end of the linked list, then do nothing  */
        else if (tempNode.key == mostRecentlyUsed.key) {
            return mostRecentlyUsed.value;
        }

        /*  key is present in the cache and used, so we need to update its position, we already checked it's not at the right-most end or mostRecentlyUsed, which means It's either at the leftmost end ie leastRecentlyUsed or in middle, of both the conditions, we need to make it mostRecentlyUsed    */
        Node<K, V> nextNode = tempNode.next;
        Node<K, V> previousNode = tempNode.previous;

        /*  if the key is at the left-most or is leastRecentlyUsed, then is we need to remove it from here and put it at right most or make it mostRecentlyUsed, so update leastRecentlyUsed   */
        if (tempNode.key == leastRecentlyUsed.key) {
            nextNode.previous = null;
            leastRecentlyUsed = nextNode;
        }

        /*  key is present in the cache and is not at the left end or leastRecentlyUsed, which means it's in middle, so we need to update its position, remove from current location and put it in the right most end or make it mostRecentlyUsed */
        else if (tempNode.key != mostRecentlyUsed.key) {
            previousNode.next = nextNode;
            nextNode.previous = previousNode;
        }

        /*   make tempNode as mostRecentlyUsed   */
        tempNode.previous = mostRecentlyUsed;
        mostRecentlyUsed.next = tempNode;
        mostRecentlyUsed = tempNode;
        mostRecentlyUsed.next = null;
        return tempNode.value;
    }

    public void put(K key, V value) {
        /*  if the cache contains a key, then do nothing  */
        if (cacheMap.containsKey(key)) {
            System.out.println("key = " + key + " is already present in cache");
            Node temp = cacheMap.get(key);
            /*  check if the key present in the cache has the same value, else update */
            if (temp.value != value) {
                System.out.println("key = " + key + " in cache has " + temp.value + " and new value is " + value + " updating cache with " + value);
                temp.value = value;
                cacheMap.put(key, temp);
            }
            return;
        }
        /*  cacheMap doesn't contain the key, so we need to add the key in the Doubly linked list at the rightmost end, and make it mostRecentlyUsed. Put the new node aka mostRecentlyUsed at the right-most end of the linked list */
        Node<K, V> newNode = new Node<>(mostRecentlyUsed, null, key, value);
        /*  add the new Node as the next of mostRecentlyUsed */
        mostRecentlyUsed.next = newNode;
        cacheMap.put(key, newNode);
        /*  now new Node with be the mostRecentlyUsed   */
        mostRecentlyUsed = newNode;
        /*  cacheMap size has reached the max size, delete the leastRecentlyUsed from map   */
        if (currentSize == maxSize) {
            cacheMap.remove(leastRecentlyUsed.key);
            /* leastRecentlyUsed is the head of the doubly linked list, update the head of leastRecentlyUsed with its next    */
            leastRecentlyUsed = leastRecentlyUsed.next;
            /* set previous of leastRecentlyUsed List null, it will delete the previous Node    */
            leastRecentlyUsed.previous = null;
        }

        /*  update the cache size   */
        else if (currentSize < maxSize) {
            /*  if current size is 0, it means this is the first node, hence mark newNode as leastRecentlyUsed  */
            if (currentSize == 0) {
                leastRecentlyUsed = newNode;
            }
            currentSize++;
        }
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.stream.IntStream;

public class LRUCacheTest {
    /*  basic test  */
    @Test
    void LRUCacheTest1() {
        LRUCache<Integer, String> lruCache = new LRUCache(5);
        lruCache.put(1, "apple");
        lruCache.put(2, "ball");
        lruCache.put(3, "cat");
        lruCache.put(4, "dog");
        lruCache.put(5, "egg");
        IntStream.rangeClosed(1, 5).forEach(i -> System.out.println("key: " + i + ", value: " + lruCache.get(i)));
        Node<Integer, String> mostRecentlyUsed = lruCache.getMostRecentlyUsed();
        System.out.println("most Recently Used- key: " + mostRecentlyUsed.key + ", value: " + mostRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(5, mostRecentlyUsed.key), () -> Assertions.assertEquals("egg", mostRecentlyUsed.value));
        Node<Integer, String> leastRecentlyUsed = lruCache.getLeastRecentlyUsed();
        System.out.println("least Recently Used- key: " + leastRecentlyUsed.key + ", value: " + leastRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(1, leastRecentlyUsed.key), () -> Assertions.assertEquals("apple", leastRecentlyUsed.value));
    }

    /*  key exceeds cache size  */
    @Test
    void LRUCacheTest2() {
        LRUCache<Integer, String> lruCache = new LRUCache(5);
        lruCache.put(1, "apple");
        lruCache.put(2, "ball");
        lruCache.put(3, "cat");
        lruCache.put(4, "dog");
        lruCache.put(5, "egg");
        lruCache.put(6, "fish");
        IntStream.rangeClosed(1, 6).forEach(i -> System.out.println("key: " + i + ", value: " + lruCache.get(i)));
        Node<Integer, String> mostRecentlyUsed = lruCache.getMostRecentlyUsed();
        System.out.println("most Recently Used- key: " + mostRecentlyUsed.key + ", value: " + mostRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(6, mostRecentlyUsed.key), () -> Assertions.assertEquals("fish", mostRecentlyUsed.value));
        Node<Integer, String> leastRecentlyUsed = lruCache.getLeastRecentlyUsed();
        System.out.println("least Recently Used- key: " + leastRecentlyUsed.key + ", value: " + leastRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(2, leastRecentlyUsed.key), () -> Assertions.assertEquals("ball", leastRecentlyUsed.value));
    }

    /*  key not present in cache  */
    @Test
    void LRUCacheTest3() {
        LRUCache<Integer, String> lruCache = new LRUCache(5);
        lruCache.put(1, "apple");
        lruCache.put(2, "ball");
        lruCache.put(3, "cat");
        lruCache.put(4, "dog");
        lruCache.put(5, "egg");
        IntStream.rangeClosed(10, 15).forEach(i -> System.out.println("key: " + i + ", value: " + lruCache.get(i)));
        Node<Integer, String> mostRecentlyUsed = lruCache.getMostRecentlyUsed();
        System.out.println("most Recently Used- key: " + mostRecentlyUsed.key + ", value: " + mostRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(5, mostRecentlyUsed.key), () -> Assertions.assertEquals("egg", mostRecentlyUsed.value));
        Node<Integer, String> leastRecentlyUsed = lruCache.getLeastRecentlyUsed();
        System.out.println("least Recently Used- key: " + leastRecentlyUsed.key + ", value: " + leastRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(1, leastRecentlyUsed.key), () -> Assertions.assertEquals("apple", leastRecentlyUsed.value));
    }

    /*  put same key multiple times in cache  */
    @Test
    void LRUCacheTest4() {
        LRUCache<Integer, String> lruCache = new LRUCache(5);
        lruCache.put(1, "apple");
        lruCache.put(1, "ball");
        lruCache.put(1, "cat");
        lruCache.put(1, "dog");
        lruCache.put(1, "egg");
        IntStream.rangeClosed(1, 5).forEach(i -> System.out.println("key: " + i + ", value: " + lruCache.get(i)));
        Node<Integer, String> mostRecentlyUsed = lruCache.getMostRecentlyUsed();
        System.out.println("most Recently Used- key: " + mostRecentlyUsed.key + ", value: " + mostRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(1, mostRecentlyUsed.key), () -> Assertions.assertEquals("egg", mostRecentlyUsed.value));
        Node<Integer, String> leastRecentlyUsed = lruCache.getLeastRecentlyUsed();
        System.out.println("least Recently Used- key: " + leastRecentlyUsed.key + ", value: " + leastRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(1, leastRecentlyUsed.key), () -> Assertions.assertEquals("egg", leastRecentlyUsed.value));
    }

    /*  get most Recently Used and least Recently Used  */
    @Test
    void LRUCacheTest5() {
        LRUCache<Integer, String> lruCache = new LRUCache(5);
        lruCache.put(1, "apple");
        lruCache.put(2, "ball");
        lruCache.put(3, "cat");
        lruCache.put(4, "dog");
        lruCache.put(5, "egg");
        Node<Integer, String> mostRecentlyUsed = lruCache.getMostRecentlyUsed();
        System.out.println("most Recently Used- key: " + mostRecentlyUsed.key + ", value: " + mostRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(5, mostRecentlyUsed.key), () -> Assertions.assertEquals("egg", mostRecentlyUsed.value));
        Node<Integer, String> leastRecentlyUsed = lruCache.getLeastRecentlyUsed();
        System.out.println("least Recently Used- key: " + leastRecentlyUsed.key + ", value: " + leastRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(1, leastRecentlyUsed.key), () -> Assertions.assertEquals("apple", leastRecentlyUsed.value));
    }

    /*  get Key in reverse order  */
    @Test
    void LRUCacheTest6() {
        LRUCache<Integer, String> lruCache = new LRUCache(5);
        lruCache.put(1, "apple");
        lruCache.put(2, "ball");
        lruCache.put(3, "cat");
        lruCache.put(4, "dog");
        lruCache.put(5, "egg");
        for (int i = 5; i >= 1; i--) {
            System.out.println("key: " + i + ", value: " + lruCache.get(i));
        }
        Node<Integer, String> mostRecentlyUsed = lruCache.getMostRecentlyUsed();
        System.out.println("most Recently Used- key: " + mostRecentlyUsed.key + ", value: " + mostRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(1, mostRecentlyUsed.key), () -> Assertions.assertEquals("apple", mostRecentlyUsed.value));
        Node<Integer, String> leastRecentlyUsed = lruCache.getLeastRecentlyUsed();
        System.out.println("least Recently Used- key: " + leastRecentlyUsed.key + ", value: " + leastRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(5, leastRecentlyUsed.key), () -> Assertions.assertEquals("egg", leastRecentlyUsed.value));
    }

    /*  get same Key multiple times  */
    @Test
    void LRUCacheTest7() {
        LRUCache<Integer, String> lruCache = new LRUCache(5);
        lruCache.put(1, "apple");
        lruCache.put(2, "ball");
        lruCache.put(3, "cat");
        lruCache.put(4, "dog");
        lruCache.put(5, "egg");
        IntStream.rangeClosed(1, 5).forEach(i -> System.out.println("iteration: " + i + " key: 1" + ", value: " + lruCache.get(1)));
        Node<Integer, String> mostRecentlyUsed = lruCache.getMostRecentlyUsed();
        System.out.println("most Recently Used- key: " + mostRecentlyUsed.key + ", value: " + mostRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(1, mostRecentlyUsed.key), () -> Assertions.assertEquals("apple", mostRecentlyUsed.value));
        Node<Integer, String> leastRecentlyUsed = lruCache.getLeastRecentlyUsed();
        System.out.println("least Recently Used- key: " + leastRecentlyUsed.key + ", value: " + leastRecentlyUsed.value);
        Assertions.assertAll(() -> Assertions.assertEquals(2, leastRecentlyUsed.key), () -> Assertions.assertEquals("ball", leastRecentlyUsed.value));
    }
}

plugins {
    id 'java'
    id "io.freefair.lombok" version "6.2.0"
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}

test {
    useJUnitPlatform()
}