• Register
Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

LRU (Least Recently Used) cache implementation in java

0 votes
37 views
LRU (Least Recently Used) cache implementation in java. How to implement LRU - Least Recently Used cache in java with running example.
asked Apr 16 in Data Structure And Algorithm by Pravesh Kumar

1 Answer

0 votes
LRU cache:- LRU cache means Least Recently Used cache. LRU is a cache eviction algorithm called least recently used cache. This cache algorithm keeps recently used data near the top of cache. Whenever a new data is accessed, the LRU places it at the top of the cache. When the cache limit has been reached, data that have been accessed less recently will be removed starting from bottom of cache.

LRU cache is implemented using a doubly linked list. Doubly Linked List is used to store list of datas with most recently used data at the start of the list. So, as more datas are added to the list, least recently used datas are moved to end of the list with page at tail being the least recently used data in the list.

See the running code for LRU Cache:-

package com.ds.queue;

/**
 * LRUCache class provides the facility to insert data into cache and get data from cache if available.
 * Doubly linked list data structure used in queue format
 *
 */
public class LRUCache {
   
    final static int CATACITY = 3;
    int currentCapacity = 0;
   
    Node front, rear;
   
    /**
     * Insert data into cache
     *
     * @param data
     */
    public void put(int data){
        //If data is available in cache
        if(isAvailableInCache(data)){
            //Then update data position (Always in front)
            updatePosition(data);
        }else{//If data is not available in cache
            //If cache is full
            if(isFullCache()){
                //Then remove data from queue in rear
                removeFromRear();
            }
            insert(data);
        }
    }
   
    /**
     * if given data is available in cache then return cache data and update its position (Comes front)
     *
     * @param data
     * @return
     */
    public int get(int data){
        if(isAvailableInCache(data)){
            System.out.println("Availabe in cahche:"+data);
            removeFromRear();
            insert(data);
        }
        return data;
    }
   
    /**
     * Insert data into queue
     * @param data
     */
    public void insert(int data){
        Node newNode = new Node(data);
        currentCapacity++;
        if(front == null){
            front =  rear = newNode;
            return;
        }
        newNode.next = front;
        front.prev = newNode;
        front = newNode;
    }
   
    /**
     * Update data to front position. Recently used data always comes front
     *
     * @param data
     */
    public void updatePosition(int data){
        if(rear==null)
            return;
        Node current = front;
        while(current != null){
            if(current.data == data){
                Node temp = current;
                current.prev.next = current.next;
                current.next.prev = current.prev;
                temp.next = front;
                temp.prev = null;
                front.prev = temp;
                front = temp;
                return;
            }
            current = current.next;
        }
    }
   
    /**
     * If data is available in cache then return true otherwise false
     *
     * @param data
     * @return
     */
    private boolean isAvailableInCache(int data){
        Node current = front;
        while(current != null){
            if(current.data == data){
                return true;
            }
            current = current.next;
        }
        return false;
    }
   
    /**
     * If cache is full then return true otherwise false
     *
     * @return
     */
    private boolean isFullCache(){
        return CATACITY == currentCapacity;
    }
   
    /**
     * Remove from rear
     *
     */
    public void removeFromRear(){
        Node prev_of_rear = rear.prev;
        rear.prev = null;
        prev_of_rear.next = null;
        rear = prev_of_rear;
        currentCapacity--;
    }
   
    public static void main(String[] args) {
        LRUCache cache = new LRUCache();
        cache.put(5);
        cache.put(10);
        cache.put(15);
        cache.put(20);
        cache.put(15);
        cache.get(10);
    }
   
    class Node{
        int data;
        Node next;
        Node prev;
       
        public Node(int data){
            this.data = data;
        }
    }
}

Output:-
Availabe in cahche:10
answered Apr 16 by ranju_12 (2,060 points)
...