[Java] Hashtable + Double linked list (with a touch of pseudo nodes)


  • 209
    L

    The problem can be solved with a hashtable that keeps track of the keys and its values in the double linked list. One interesting property about double linked list is that the node can remove itself without other reference. In addition, it takes constant time to add and remove nodes from the head or tail.

    One particularity about the double linked list that I implemented is that I create a pseudo head and tail to mark the boundary, so that we don't need to check the NULL node during the update. This makes the code more concise and clean, and also it is good for the performance as well.

    Voila, here is the code.

    class DLinkedNode {
    	int key;
    	int value;
    	DLinkedNode pre;
    	DLinkedNode post;
    }
    
    /**
     * Always add the new node right after head;
     */
    private void addNode(DLinkedNode node){
    	node.pre = head;
    	node.post = head.post;
    	
    	head.post.pre = node;
    	head.post = node;
    }
    
    /**
     * Remove an existing node from the linked list.
     */
    private void removeNode(DLinkedNode node){
    	DLinkedNode pre = node.pre;
    	DLinkedNode post = node.post;
    	
    	pre.post = post;
    	post.pre = pre;
    }
    
    /**
     * Move certain node in between to the head.
     */
    private void moveToHead(DLinkedNode node){
    	this.removeNode(node);
    	this.addNode(node);
    }
    
    // pop the current tail. 
    private DLinkedNode popTail(){
    	DLinkedNode res = tail.pre;
    	this.removeNode(res);
    	return res;
    }
    
    private Hashtable<Integer, DLinkedNode> 
    	cache = new Hashtable<Integer, DLinkedNode>();
    private int count;
    private int capacity;
    private DLinkedNode head, tail;
    
    public LRUCache(int capacity) {
    	this.count = 0;
    	this.capacity = capacity;
    
    	head = new DLinkedNode();
    	head.pre = null;
    	
    	tail = new DLinkedNode();
    	tail.post = null;
    	
    	head.post = tail;
    	tail.pre = head;
    }
    
    public int get(int key) {
        
    	DLinkedNode node = cache.get(key);
    	if(node == null){
    		return -1; // should raise exception here.
    	}
    	
    	// move the accessed node to the head;
    	this.moveToHead(node);
    	
    	return node.value;
    }
    
    
    public void set(int key, int value) {
    	DLinkedNode node = cache.get(key);
    	
    	if(node == null){
    		
    		DLinkedNode newNode = new DLinkedNode();
    		newNode.key = key;
    		newNode.value = value;
    		
    		this.cache.put(key, newNode);
    		this.addNode(newNode);
    		
    		++count;
    		
    		if(count > capacity){
    			// pop the tail
    			DLinkedNode tail = this.popTail();
    			this.cache.remove(tail.key);
    			--count;
    		}
    	}else{
    		// update the value.
    		node.value = value;
    		this.moveToHead(node);
    	}
    	
    }

  • 2
    C

    good design to set head and tail as empty point which simple the add and remove operation!


  • 0
    D
    This post is deleted!

  • 0
    G

    Really good one liaison. Thank you so much for sharing it. :)


  • 0
    I

    popTail method does not remove the tail but removed the prev, why? What is the purpose of adding in front of head and not actually adding to the head position?


  • 6
    L

    The "tail" is the pseudo node that marks the boundary of the tail, same as that the "head" node is a pseudo node that marks the head. The double linked list can be represented as head (pseudo) <--> head <--> ....tail <--> tail (pseudo).

    By adding two pseudo nodes to make the boundaries, we could reduce the boundary checking code such as if (head != null), making the code more concise and also more efficient.


  • 0
    I

    Thanks much!


  • 1

    map paired key and node's address made it possible to find the node directly with the key value. Use double linked list help to change list's order.


  • 0
    D

    why not use LinkedList in java, it's already a doubly list with all methods??


  • 0
    J

    Nice solution but I don't understand the purpose of using doubly link list instead of single linked list. Can't this be done using single link list?


  • 0
    H

    LRU.................


  • 11
    P

    Excellent idea! Based on your solution, I moved all methods on DLinkNode to inside the inner class to make the structure neater. I also removed 'count' which is not necessary and kept 'head' and 'tail' as real nodes instead of some Nil.

    public class LRUCache {
        private Map<Integer, DLinkNode> cache;
        DLinkNode tail = null;
        DLinkNode head = null;
        int capacity;
    
        public LRUCache(int capacity) {
            cache = new HashMap<Integer, DLinkNode>();
            this.capacity = capacity;
        }
        
        public int get(int key) {
            if (cache.containsKey(key)) {
                DLinkNode target = cache.get(key);
                int value = target.value;
                target.update();
                return value;
            } else return -1;
        }
        
        public void set(int key, int value) {
            if (cache.containsKey(key)) {
                DLinkNode target = cache.get(key);
                target.value = value;
                target.update();
            } else {
                if (capacity == 0) return;
                if (cache.size() == capacity) {
                    cache.remove(head.key);
                    head.removeFromHead();
                }
                DLinkNode newNode = new DLinkNode(key, value);
                newNode.append();
                cache.put(key, newNode);
            }
        }
        
        class DLinkNode {
            int key;
            int value;
            DLinkNode left = null;
            DLinkNode right = null;
            public DLinkNode(int key, int value) {
                this.key = key;
                this.value = value;
            }
            // remove head from list and update head reference.
            private void removeFromHead() {    
                // if 'this' is the only node, set both head and tail to null.
                if (tail == this) {             
                    head = null;
                    tail = null;
                } else {
                    head = this.right;
                    head.left = null;
                }
            }
            private void update() {
                // no need to update if accessing the most revently used value.
                if (tail == this) return;       
                else { 
                     // remove from current postion and update nodes (if any) on both sides.
                    if (this != head) {        
                        this.left.right = this.right;
                    } else {
                        head = this.right;
                    }
                    this.right.left = this.left;
                     // append to tail.
                    this.append();             
                }
            }
            private void append() {
                // inserting the first node.
                if (tail == null) {     
                    head = this;
                    tail = this;
                // appned as tail and update tail reference.
                } else {                
                    this.right = null;
                    this.left = tail;
                    tail.right =this;
                    tail = this; 
                }
            }
        }
    }

  • 10
    M

    With double linked list implemented by ourselves and a map store key to nodes, we can access to the node corresponding to any key in constant time.
    Using Java 's LinkedList can not make constant access. It requires O(n) time to find which key to move to top.


  • 2
    M

    You can not move a node from the middle to head by single linked list with only carrying the reference of that node. But you can do it by double linked list.


  • 0
    J

    I don't get it, if you want to move one node from middle to the front, you can just do remove node operation of LinkedList and use the head pointer to mount it at the top.


  • 6
    S

    In order to remove the node, you have to let the next pointer of its previous node point to its next node, but in single linked list, you can not easily get the reference(O(n)) to its previous node when you only have the reference to itself. Thus double-linked list solves this problem.


  • 1
    R

    Given a node in a singly linked list, you can remove that node without previous reference.
    And then put it before the head.

    public Node remove(Node node){

    Node temp = new Node (node.data);

    node.value = node.next.value;

    node.next = node.next.next;

    return Node;

    }

    so I think the above code can be implemented using singly linked list


  • 0
    D

    @ronakshah725, I assume you meant to return temp. Also, you need to update the key in the node. Your idea would work as long as you also update the cache map since the node you "removed" now contains different data


  • 0
    D

    @jiten-thakkar, LinkedList.remove() takes O(n) time (it needs to iterate through the list to find the element) whereas when using a HashMap + doubly linked list remove() will take O(1) time. The OP said that adding and removing at the head or tail takes O(1) time, but actually adding or removing from anywhere takes O(1) time.


  • 0
    H

    Why do we use a hashtable instead of a hashmap? Is it because it's synchronized?


Log in to reply
 

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