Java solution using Doubly linked list and Hashtable. Please critique coding style.


  • 0
    P
    import java.util.Hashtable;
    public class LRUCache {
        
        int size,MAX_SIZE;
        Node head,tail;
        Hashtable<Integer, Node> table;
    
        public LRUCache(int capacity){
    	        this.size = 0;
            	this.MAX_SIZE = capacity;
    	        this.table = new Hashtable<Integer,Node>(capacity);
            	this.head = null;
        }
    
        public int get(int key){
            	if (table.containsKey(key)){
    	            Node nd = table.get(key),prev,next;
            	    //add the node to the front of the q
    	            removeNode(nd);
            	    addNodeToFront(nd);
    	            return head.value;
    	        }
            	return -1;
        }
        public void set(int key, int value){
    	        if (table.containsKey(key)){
            	    Node nd = table.get(key),prev,next;
    	            //move the node to the front of the q
            	    if (nd == head){ 
    	        	nd.value  = value;
    		        return;
            	    }
    	            removeNode(nd);
            	    addNodeToFront(nd);
    	            head.value = value;
        	}
    	else{
    	    if (size < MAX_SIZE){
    
    		Node nd = new Node(key,value);
    		addNodeToFront(nd);
    		if (size == 0) tail = head;//set the tail pointer for base case
    		size++;//increment the list size
    		table.put(nd.key,nd);//update the table
    	    }
    	    else{
    		Node nd = tail;
    
    		removeNode(nd);
    
    		table.remove(nd.key);//remove the previous key
    
    		nd.key = key;//update the key
    		nd.value = value;//update the value
    
    		addNodeToFront(nd);//move it to the front
    		table.put(nd.key,nd);//update the entry in table
    	    }
    	}
        }
    
        
        private class Node{
    	    Node next,prev;
    	    int key,value;
    	    private Node(int key, int value){
        	    this.key = key; this.value = value;
    	    }
    
    	    void setNext(Node nd){
    	        this.next = nd;
    	        nd.prev = this;
    	    }
        }
    
        private void print(){
    	if (head != null){
    	    Node h = head;
    	    for(;h != null; h = h.next)
    		System.out.println(h.value);
    	}
        }
        private void removeNode(Node node){
    	if (node == head) head = head.next;
    	else{
    	    Node prev,next;
    	    prev = node.prev;
    	    next = node.next;
    	    prev.next = next;
    	    if (next != null) //there is a next node
    		next.prev = prev;
    	    else //there is no next node, that means the tail node was removed
    		tail = prev;
    	}
        }
        private void addNodeToFront(Node node){
    	if (node != head){
    	    node.next = head;
    	    node.prev = null;
    	    if (head != null) head.prev = node;
    	    head = node;
    	}
        }
    }

Log in to reply
 

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