HashMap and 'doubly linked' linked list solution


  • 0
    Q
    public class LRUCache {
        private HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
    	    private HashMap<Integer, LinkNode> nodeCache = new HashMap<Integer, LinkNode>();
    	    int capacity;
    	    private LinkNode head = null;
    	    private LinkNode tail = null;
    
    	    public LRUCache(int capacity) {
    	        this.capacity = capacity;
    	    }
    	    
    	    public int get(int key) {
    	        Integer inter = map.get(new Integer(key));
    	        if (inter == null){
    	            return -1;
    	        }
    	        LinkNode node = nodeCache.get(new Integer(key));
    	        moveToHead(node);
    	        return inter;
    	    }
    	    
    	    public void set(int key, int value) {
    	        if (head == null){
    	            head = new LinkNode();
    	            tail = head;
    	            head.key = key;
    	            nodeCache.put(key, head);
    	        }
    	        else {
    	        	if (nodeCache.containsKey(key)){
    	            	LinkNode n = nodeCache.get(key);
    	            	moveToHead(n);
    	            }
    	        	else if (map.size()>=capacity){
    	        		int tailKey = tail.key;
    	        		if (tail.prev !=null){
    	        		    tail = tail.prev;
    	        		    tail.next = null;
    	        		}
    	        		else{
    	        			head = null;
    	        			tail = null;
    	        		}
    	        		LinkNode n = new LinkNode();
    	        		n.key=key;
    	        		
    	        		if (head!=null){
    		        		n.next=head;
    		        		head.prev = n;
    		        		head = n;
    	        		}
    	        		else{
    	        			head = n;
    	        			tail = head;
    	        		}	
    	            	nodeCache.remove(tailKey);
    	        		map.remove(tailKey);
    	        		nodeCache.put(key, head);
    	            }
    	        	else{
    	        		LinkNode l = new LinkNode();
    	                l.key = key;
    	                l.next = head;
    	                head.prev = l;
    	                head = l;
    	            	nodeCache.put(key, head);
    	        	}
    	        }
    	        map.put(key, value);
    	    }
    	    
    	    private void moveToHead(LinkNode node){
    	    	 if (node == head){
    	    		 return;
    	    	 }
    	    	 LinkNode prev = node.prev;
    	         LinkNode next = node.next;
    
    	         prev.next = next;
    	         
    	         if (next!=null){
    	        	 next.prev = prev;
    	         }
    	         else{
    	        	 tail = prev;
    	         }
    	         
    	         node.next = head;
    	         head.prev = node;
    	         head = node;
    	    }
    	    
    	    private class LinkNode{
    	        int key;
    	        LinkNode next;
    	        LinkNode prev;
    	    }
    }

Log in to reply
 

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