Java Transparent O(1) get O(1) set: Doubly Linked List + HashMap


  • 0
    T
    public class LRUCache {
    
    static class DoubleLinkedNode{
    	int val;
    	int key;
    	DoubleLinkedNode prev;
    	DoubleLinkedNode next;
    	
    	public DoubleLinkedNode(int key,int val){
    		this.key=key;
    		this.val=val;
    	}
    }
    
    static class DoubleLinkedList{
    	DoubleLinkedNode head;
    	DoubleLinkedNode tail;
    	int capacity;
    	int len;
    	
    	public DoubleLinkedList(int capacity){
    		this.capacity=capacity;
    	}
    	
    	//precondition N0 exist
    	public void removeNode(DoubleLinkedNode N0){
    		//head/tail changes
    		if (len==1){
    			head=null; tail=null;
    		}
    		else {
    			if (N0==head) head=head.next;
    			if (N0==tail) tail=tail.prev;
    		}
    		//connection changes
    		if (N0.prev==null && N0.next!=null){N0.next.prev=null; N0.next=null;}
    		else if (N0.prev!=null && N0.next==null){N0.prev.next=null; N0.prev=null;}
    		else if (N0.prev!=null && N0.next!=null){N0.prev.next=N0.next; N0.next.prev=N0.prev; N0.prev=null; N0.next=null;}
    		//length changes
    		this.len--;
    	}
    	
    	public void addNode(DoubleLinkedNode N0){
    		if (this.len==0) {this.head=N0; this.tail=N0;this.len++;}
    		else {
    			this.tail.next=N0;
    			N0.prev=this.tail;
    			this.tail=N0;
    			this.len++;
    		}
    	}
    }
    
    HashMap<Integer,DoubleLinkedNode> H;
    	DoubleLinkedList L;
        
        public LRUCache(int capacity) {
            this.H=new HashMap<Integer,DoubleLinkedNode>();
            this.L=new DoubleLinkedList(capacity);
        }
        
        public int get(int key) {
            if (H.keySet().contains(key)){
            	DoubleLinkedNode N=H.get(key);
            	this.set(key,N.val);
            	return N.val;
            }
            return -1;
        }
        
        public void set(int key, int value) {
            //if key already exists
        	if (H.keySet().contains(key)){
        		L.removeNode(H.get(key));
        		DoubleLinkedNode N1=new DoubleLinkedNode(key,value);
        		H.put(key,N1);
        		L.addNode(N1);
        	}
        	//if key not yet exist
        	else {
        		DoubleLinkedNode N1=new DoubleLinkedNode(key,value);
        		H.put(key,N1);
        		L.addNode(N1);
        		if (L.len>L.capacity) {
        			DoubleLinkedNode oldHead=L.head; 
        			L.removeNode(oldHead);
        			H.remove(oldHead.key);
        		}
        	}
        }
    

    }


Log in to reply
 

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