LRU implementation in Java and Go

What is LRU Algo?

LRU which stands for Least Recently Used, it is a popular algorithm used in computer science for managing memory caches. It is a type of cache eviction algorithm, which determines about which data to be removed from a cache when the cache is full.

How it Works

In a computer system, caches are used to store frequently accessed data in memory. This helps to speed up access to data as accessing data from memory is much faster than accessing data from the disk or other external storage devices. However, as the size of the cache is limited, it is important to manage the cache efficiently so that the most frequently accessed data is always available in the cache.

The LRU algorithm works on the principle of removing the least recently used data from the cache. The idea behind this is that the data that has not been accessed for a long time is less likely to be accessed again in the near future. Therefore, if the cache is full, the data that was accessed least recently is removed from the cache to make space for new data.

The LRU algorithm is implemented using a data structure called a doubly linked list. In a doubly linked list, each node contains a pointer to the next node as well as a pointer to the previous node. In the context of the LRU algorithm, each node in the doubly linked list represents a data item in the cache.

When a data item is accessed, it is moved to the front of the linked list. This indicates that it has been accessed most recently. When the cache is full and a new data item needs to be added, the least recently used item is removed from the back of the linked list.

Implementation in Java

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

class Main {
  public static void main(String[] args) {
    System.out.println("Hello world!");

    LRUCache cache = new LRUCache(4);
    cache.addToCache(11);
    cache.addToCache(12);
    cache.printLRU();

    cache.addToCache(13);
    cache.printLRU();

    cache.addToCache(11);
    cache.addToCache(14);
    cache.printLRU();

    cache.addToCache(15);
    cache.addToCache(11);
    cache.addToCache(12);
    cache.printLRU();

  }
}

class LRUCache {

  // doublyLRUList - List for LRU data holding
  private Deque<Integer> doublyLRUList;

  // for checking if any page is avalabile in cache 
  // it saves the iteration on doublyLRUList
  private HashSet<Integer> LRUhashSet;

  // LRU_SIZE - maximum size of cache
  private final int LRU_SIZE;

  LRUCache(int capacity) {
    doublyLRUList = new LinkedList<>();
    LRUhashSet = new HashSet<>();
    LRU_SIZE = capacity;
  }

  // addToCache add the page in the LRU cache
  public void addToCache(int page) {
    if (!LRUhashSet.contains(page)) {
      if (doublyLRUList.size() == LRU_SIZE) {
        int last = doublyLRUList.removeLast();
        LRUhashSet.remove(last);
      }
    } else { 
      doublyLRUList.remove(page);
    }
    doublyLRUList.push(page);
    LRUhashSet.add(page);
  }

  // printLRU prints contents of cache
  public void printLRU() {
    Iterator<Integer> itr = doublyLRUList.iterator();
    while (itr.hasNext()) {
      System.out.print(itr.next() + " ");
    }
    System.out.println();
  }

}

Repl Link:: https://replit.com/@AnkitMalik2/LRU-Java#Main.java

Implementation in Golang

package main

import (
    "fmt"
)

type LRUCache struct {
    LRUList    []int
    LRUHashMap map[int]bool
    Size       int
}

func NewLRUCache(size int) *LRUCache {
    return &LRUCache{
        LRUList:    make([]int, 0),
        LRUHashMap: make(map[int]bool),
        Size:       size,
    }
}

// Add insert the data in LRU
func (lru *LRUCache) Add(value int) {
    l := len(lru.LRUList)

    if !lru.LRUHashMap[value] {
        if l >= lru.Size {
            last := lru.LRUList[l-1]
            lru.LRUList = lru.LRUList[:l-1]
            delete(lru.LRUHashMap, last)
        }
    } else {

        for idx, data := range lru.LRUList {
            if data == value {
                lru.LRUList = append(lru.LRUList[:idx], lru.LRUList[idx+1:]...)
                break
            }

        }
    }

    lru.LRUList = append([]int{value}, lru.LRUList...)
    lru.LRUHashMap[value] = true
}

// PrintLRU - prints the data of LRU cache
func (lru *LRUCache) PrintLRU() {
    for _, data := range lru.LRUList {
        fmt.Print(data, " ")
    }
    fmt.Println()
}

func main() {
    // initiate lru with defined size
    lru := NewLRUCache(5)

    // use of Add function
    lru.Add(1)
    lru.Add(2)
    lru.Add(3)
    lru.Add(4)
    lru.Add(5)
    lru.Add(6)
    lru.Add(1)

    // printing all data of LRU
    lru.PrintLRU()
}

Repl Link: https://replit.com/@AnkitMalik2/LRU-Golang#main.go

You can see some complicated LRU implementation here: https://github.com/hashicorp/golang-lru/blob/8d9a62dcf60cd87ed918b57afad8a001d25db3de/simplelru/lru.go