LRUCache Data Struture

LRUCache.java

/*
LRU Cache capacitate 5

  MostRecently U             Least Recenty Used
HEAD(-1) 9 <-> 10 <-> 1 <-> 5 <-> 2(-1)TAIL

Put(5)

get(1)

get(key)

put(9,data)

put(10,data)

get( 9 )

//agenda telefonica:

//nickname: telefon





1. doubly Linked list

2. HashMap

node1(info, next, prev) --->node2(info, next, prev) -> node3(info, next, prev) -> .....->nodeN(info, next, prev)

1 <--> 2 <-> 3...

HEAD <-> TAIL
*/

import java.util.HashMap;

public class LRUCache {

       static class Node {

            int key;
            int data;
            Node next;
            Node prev;

            Node(int key, int data) {
                this.key = key;
                this.data = data;
                next = null;
                prev = null;

            }
       }

       int capacity;

       //santinale -> noduri fictive la cap si coada , nu contin date reale

       Node head; //cel mai recent MRU
       Node tail; // cel mai putin recent LRU

       //Hashmap key -> value;
       //ne da referinta directa la nod
       //
       HashMap<Integer, Node> map;

       LRUCache(int capacity) {

           this.capacity = capacity;
           this.map = new HashMap<>();

           //initializam santinelele
           head = new Node(-1, -1);
           tail = new Node(-1, -1);

           head.next = tail;
           tail.prev = head;
           //HEAD <--> Tail (lista vida)
       }

       //operatii interne pe lista
       // HEAD <--> <prev> -- [node] --<next> ...TAIL
       // HEAD node1(info,next, prev) [node(info, next, prev)] node3(info,next, prev)... TAIL
       void removeNode( Node node ) {

            node.prev.next = node.next;//primul link
            
            node.next.prev = node.prev;//al doilea link
       }

       //HEAD <--> [node(info, next, prev)] <--> nodeX(next, prev) .... TAIL
       void addAfterHead(Node node) {

             node.next = head.next;
             node.prev = head;
             head.next.prev = node;
             head.next = node;
             //head.next in stanga semnului egal
             //head.next in dreapta semnului egal
       }

       void moveToHead(Node node) {

            removeNode(node);

            addAfterHead(node);
       }

      //HEAD node5 <--->node1  <--->node2  <--->node3  <--->node4 <-->TAIL
       Node removeLRU() {

           Node lru = tail.prev;

           removeNode(lru);

           return lru;
       }

       //--------------- API Public------------
       //get( key ) --- returneaza valoarea daca exista
       //put( key, data ) --->adauga in cache

       int get( int key ) {

           if(!map.containsKey(key)) {

              System.out.println("GET " + key + " --> not found");
              return -1;
           }

           Node node = map.get( key );

           moveToHead( node ); //acum este cel mai recent folosit

           System.out.println("GET "+ key + "-->" + node.data);

           return node.data;
       }

       void put(int key, int val) {

            if(map.containsKey(key)) {

                 Node node = map.get(key);

                 node.data = val;

                 moveToHead( node );//RMU

                 System.out.println("PUT " + key + " = " + val);

            } else {
              //cheia este noua

                 if(map.size() == capacity) {

                        //cache este plin .. ELIMINARE LRU
                        Node lru =removeLRU();

                        map.remove( lru.key );

                 } else {

                     System.out.println("PUT " + key + " = " + val);

                 }

                 Node newNode = new Node(key, val);

                 addAfterHead(newNode);
                 map.put(key, newNode);
            }
       }

      /*
       HEAD node1 node2 node3 node4 node5 TAIL
       //                                  c
      */
       void display() {

          Node c = head.next;

          System.out.print("Cache (MRU) <--> (LRU)");

          while(c != tail) {
                System.out.print("(" + c.key + " = " + c.data + " )");
                c = c.next;
          }

            System.out.println("| Size = " + map.size() + "/" + capacity);
       }

       public static void main(String[] args) {

            System.out.println("===== LRU Cache (capacity = 3)");
            LRUCache cache = new LRUCache( 3 );

            cache.put(1, 10); cache.display();
            cache.put(2, 20); cache.display();
            cache.put(3, 30); cache.display();
            //HEAD 3 <-> 2 <-> 1 <->TAIL


            System.out.println();

            cache.get(1); //access key = 1
            cache.display();

            System.out.println();
            cache.put(4, 40);//cache este plin
            cache.display();

            cache.get(2); //access key = 2
            cache.display();

            cache.get(3); //access key = 3
            cache.display();

            System.out.println();
            cache.put(5, 50);//cache este plin
            cache.display();


       }

}