LRU Cache

1. Example

Least Recently Used cache

       MRU                  LRU

LinkedList    
        Node                 Node
        head->...........->tail
HashMap
        (, Node head)
        (, Node tail)

GET
        Node          Node         Node
        head->.......Target....->tail
                                X
             <-------------|
                                SET
        Node          Node         Node
        head->.......Target....->tail
                             set
                              +
                              X 
           <-------------|
                               OR
                                              X                                              
      NewNode(@head)

Doubly Linked List REMOVE
//A->B->C
//      X
//A->B->C
//X
//A->B->C
//            X

Doubly Linked List SET HEAD
// A->B->C
//Q->A->B->C

// ""
// Q (first and last)

map.remove(last.key);
removeNode(last); 

num--;

setHead(newHead); 

 map.put(key, newNode); 

 num++;


- get(key), O(1) => hashmap
1.exist =>value, not exist => -1
- set(key, value), O(1) insert + in order => linkedlist
1.not present=> insert
2.reached capacity=> invalidate the least recently used and insert


2. Implementation

// Cache: size
// Get O(1), Set O(1)

public class LRUCache
{



     class Node 
     {
         Node pre, next;
         int key;
         int value;
     }




     private int capacity;
     private int num;
     private HashMap<> map;// achieve run time of search O(1)
     private Node first, last;
     public LRUCache(int capacity)
     {
          this.capacity = capacity;
          num = 0;
          map = new HashMap();
     } 





     public int get(int key)
     {
          //if ( map.containsKey(key) )
          //   return map.get(key).value;
          //else 
          //   return -1;
          

          // NOTE: get ALSO move the get node to the HEAD(MRU)
          


          Node node = map.get(key);
          if ( node == null )
              return -1;



          removeNode(node);
          setHead(node);
          return node.val;


     }





     public void set(int key, int value)
     {
         //if ( ! map.containsKey(key) )
         // map.put(key, value)
         // InsertNewNode(key,value);// do the capacity check in InsertNewNode() method
         //else 
         // map.put(key, value)
         // changeNodeValue(key,value);




         Node node = map.get(key);
         if ( node != null )
         {
              node.val = value;
              // NOTE: set and mode the set node to HEAD(MRU)
              removeNode(node);
              setHead(node);
         }
         else
         {
             

             
              Node newNode = new Node(key, value);
             



              if ( num >= capacity )
              {
                   map.remove(last.key);// remove ref first
                   removeNode(last);// remove node itself
                   num--;
              }


             
     
              setHead(newHead);// set up node first 
              map.put(key, newNode);// point to node
              num++;




         }
     }





     private void removeNode( Node node)
     {
              //A->B->C
              //   X
              //A->B->C
              //X   
              //A->B->C
              //      X


              // NOTE : already node != null
              Node cur = node;
              Node pre = node.pre;
              Node next = node.next;



              if ( pre != null )
              {
                   pre.next = next;
              }
              else 
              {
                   first = next;
              }
              if ( next != null )
              {
                   next.pre = pre;
              }
              else 
              {
                   last = pre;
              }


                    
     }
     private void setHead( Node node )
     {



              //   A->B->C
              //Q->A->B->C
              // ""
              // Q (first and last) 
              // NOTE: already node != null
              // Set Head
              node.next = first;
              node.pre = null;



              if (first != null)
                  first.pre = node;


              first= node;



              if ( last == null )
                  last = node;



              
     }
}

3. Similar Ones