LRU Cache Implementation

Abhinay Gupta

·

Follow

1 min read

·

Jul 14, 2021

--

Share

class LRUCache {
    
    private Map<Integer, Node> map;
    final Node head = new Node();
    final Node tail = new Node();
    private int capacity;public LRUCache(int capacity) {
        this.map = new HashMap<>(capacity);
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        int result = -1;
        Node node = map.get(key);
        if(node != null) {
            result=node.value;
            remove(node);
            add(node);
        }
        
        return result;
    }
    
    public void put(int key, int value) {
        Node node = map.get(key);
        if(node != null) {
            remove(node);
            node.value = value;
            add(node);      
        }      
        else
        { 
            if(map.size() == capacity) {
            map.remove(tail.prev.key);
            remove(tail.prev);
            }
        node = new Node();
        node.key = key;
        node.value = value;
        map.put(key, node);
        add(node);
        }
    }
    
    //add the first node to Doubly Linked List
    public void add(Node node){
        Node head_next = head.next;
        head.next = node;
        node.next = head_next;
        node.prev = head;
        head_next.prev = node;
        
    }
    
    //remove the  node of Doubly LinkedList
    public void remove(Node node){
        Node next_node = node.next;
        Node prev_node = node.prev;
        
        next_node.prev = prev_node;
        prev_node.next = next_node;
    }
    
    class Node {
  int key;
  int value;
  Node next;
  Node prev;
  
 } 
}