LRU Cache using Doubly Linked List and Hash Map


  • 0
    Y
    import java.util.HashMap;
    import java.util.Map;
    
    class LRUCache{
        
        class Node{
            int key;
            int value;
            Node pre;
            Node next;
    
            public Node(int key, int value){
                this.key = key;
                this.value = value;
                }
        }
    
        int capacity;
        HashMap<Integer, Node> map = new HashMap<Integer, Node>();
        Node head=null;
        Node end=null;
     
        public LRUCache(int capacity) {
            this.capacity = capacity;
        }
     
        public int get(int key) {
            if(map.containsKey(key)){
                Node n = map.get(key);
                remove(n);
                set(n);
                return n.value;
            }
     
            return -1;
        }
     
        public void remove(Node n){
            if(n.pre!=null){
                n.pre.next = n.next;
            }else{
                head = n.next;
            }
     
            if(n.next!=null){
                n.next.pre = n.pre;
            }else{
                end = n.pre;
            }
     
        }
     
        public void set(Node n){
            n.next = head;
            n.pre = null;
     
            if(head!=null)
                head.pre = n;
     
            head = n;
     
            if(end ==null)
                end = head;
        }
     
        public void put(int key, int value) {
            if(map.containsKey(key)){
                Node old = map.get(key);
                old.value = value;
                remove(old);
                set(old);
            }else{
                Node created = new Node(key, value);
                if(map.size()>=capacity){
                    map.remove(end.key);
                    remove(end);
                    set(created);
     
                }else{
                    set(created);
                }    
     
                map.put(key, created);
            }
        }
    }
    
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.