LRU cache - Using doubly linked list (Fast!), Java

LRU cache - Using doubly linked list (Fast!)

//'main' method must be in a class 'Rextester'.
//Compiler version 1.8.0_111

import java.util.*;
import java.lang.*;
class Node{
    int key;
    int val;
    Node prev;
    Node next;
    public Node(int key,int val){
        this.key = key;
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}
class LRUCache{
    Map<Integer,Node> mp = new HashMap<Integer,Node>();
    Node head,tail;
    int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        if(!mp.containsKey(key))
            return -1;
        Node node = mp.get(key);
        remove(node);
        add(node);
        return node.val;
    }
    public void put(int key, int value) {
        if(mp.containsKey(key)){
            remove(mp.get(key));
        }
        Node newNode = new Node(key,value);
        add(newNode);
        mp.put(key,newNode);
        if(mp.size()>capacity){
            Node node = head.next;    
            remove(node);
            mp.remove(node.key);
        }
        
    }
    
    public void add(Node node){
        Node prev = tail.prev;
        prev.next = node;
        node.prev = prev;
        node.next = tail;
        tail.prev = node;
    }
    public void remove(Node node){
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        next.prev = prev;
    }
    
    public void printDS(){
        Node node = head;
        while(node!=null){
            System.out.print(node.key+":"+node.val+"->");
            node = node.next;
        }    
    }
}

class Rextester
{  
    public static void main(String args[])
    {
        System.out.println("Hello, World!");
        LRUCache obj = new LRUCache(2);
        obj.put(1,1);
        
        obj.put(2,2);
        System.out.println(obj.get(1));
        obj.put(3,3);
        System.out.println(obj.get(2));
        obj.printDS();
    }
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development