LRU cache mechanism implementation in java

     LRU -Least Recently used. Cache is a fast memory. Let us implement the LRU cache mechanism in java.

Data structures used: hashmap and doubly linked list.

Program implementation:

• A class LRUCacheEg is created with three variables capa(capacity), hash map object and doubly Linked list.
• Constructor initialises the three variable.
•  ‘get()’ function is used to get the value.
• ‘put()’ function is use to return value.
• ‘Node’ and ‘doubly linked list’ are created with its structure.
• ‘addtoHead()’ , ‘remove tail()’, ‘removenode()’ and ‘removetohead()’ are the functions in the class.
• Create the main() function. Create cache object and call the get and put function to display the output.

Program:

import java.util.*;

class LRUCacheEg<K, V> {

    private final int capa;

    private final Map<K, Node<K, V>> cache;

    private final DoublyLinkedList<K, V> list;

    public LRUCacheEg(int capa) {

        this.capa = capa;

        this.cache = new HashMap<>();

        this.list = new DoublyLinkedList<>();

    }

    public V get(K key) {

        if (!cache.containsKey(key)) {

            return null; // if Key is not present,return null.

        }

        Node<K, V> node = cache.get(key);

        list.moveToHead(node); // Update access order

        return node.value;

    }

    public void put(K key, V value) {

        if (cache.containsKey(key)) {

            Node<K, V> node = cache.get(key);

            node.value = value;

            list.moveToHead(node);

        } else {

            if (cache.size() == capa) {

                Node<K, V> tail = list.removeTail();

                cache.remove(tail.key);

            }

            Node<K, V> newNode = new Node<>(key, value);

            list.addToHead(newNode);

            cache.put(key, newNode);

        }

    }

    private static class Node<K, V> {

        K key;

        V value;

        Node<K, V> prev;

        Node<K, V> next;

 

        Node(K key, V value) {

            this.key = key;

            this.value = value;

        }

    }

    private static class DoublyLinkedList<K, V> {

        private final Node<K, V> head;

        private final Node<K, V> tail;

        DoublyLinkedList() {

            head = new Node<>(null, null);

            tail = new Node<>(null, null);

            head.next = tail;

            tail.prev = head;

        }

        void addToHead(Node<K, V> node) {

            node.next = head.next;

            node.prev = head;

            head.next.prev = node;

            head.next = node;

        }

        void moveToHead(Node<K, V> node) {

            removeNode(node);

            addToHead(node);

        }

        Node<K, V> removeTail() {

            if (tail.prev == head) return null; // List is empty

            Node<K, V> node = tail.prev;

            removeNode(node);

            return node;

        }

        private void removeNode(Node<K, V> node) {

            node.prev.next = node.next;

            node.next.prev = node.prev;

        }

    }

    public static void main(String[] args) {

        LRUCacheEg<Integer, String> c1 = new LRUCacheEg<>(3);

        c1.put(1, "One");

        c1.put(2, "Two");

        c1.put(3, "Three");

        System.out.println(c1.get(2));

        c1.put(4, "Four");

        System.out.println(c1.get(3));

    }

}

Output:

C:\raji\blog>javac LRUCacheEg.java

C:\raji\blog>java LRUCacheEg

Two

Three

This is the sample implementation of LRU cache mechanism in java. Hope,this code is useful to you.Keep coding!!!