[Java] HashMap with double linked list (147ms beats 89%)


  • 2
    Z

    The initial problem can be solved by double linked list, the linked list acts like a queue, but keeps moving the latest used (by put and get) node to the end of the queue so that the least recently used node will be at the head. Note that both get and put operation need to find the key in the list first, which costs at least O(n) time if n is the list's length (list is not sorted so binary search is not applicable). Even with the most advanced search method, the follow-up's requirement of O(1) is impossible. The only way to find some key in a data structure in O(1) time is to memorize the key's location. Thus, the hashtable, hashmap and array are suitable for storing the keys. For here I use hashmap, since array has disadvantages in resizing.
    Still, we would like to keep track of the nodes in the linked list, considering a key is with its corresponding node, we combine the hashmap and linked list, which is to store the key as the hashmap's key, and the key's corresponding node as the value. The linked list is formed by node pointer within the node class. Every time a node in the linked list changes, we update the hashmap so it keeps tracking of the structure change in the list.
    In this case, we find any node with certain value in O(1) time, and maintain the linked list's structure. The sample code is as follows, I also store the key in the node as well for a clear understanding. The runtime is about 200ms, only 20% above others, so I'm also looking for other optimization.

    public class LRUCache {
    
    
    	class ListNode {
    		int val;
    		int key;
    		ListNode next;
    		ListNode prev;
    
    		ListNode(int key, int val) {
    			this.key = key;
    			this.val = val;
    			this.prev = null;
    			this.next = null;
    		}
    	}
    
    	private HashMap<Integer, ListNode> list = new HashMap<>();
    	private ListNode head = null;
    	private ListNode tail = null;
    	private int cap = 0;
    
    	public LRUCache(int capacity) {
    		if (capacity > 0) {
    			cap = capacity;
    		} else {
    			System.out.println("Capacity should be positive integer!");
    			return;
    		}
    	}
    
    	public int get(int key) {
    		int val = -1;
    		ListNode n = list.get(key);
    		if (n != null) {
    			val = n.val;
    			refreshNode(n);
    		}
    		return val;
    	}
    
    	public void put(int key, int value) {
    		ListNode n = list.get(key);
    		if (n != null) { // key already in
    			n.val = value;
    			refreshNode(n);
    		} else {
    			removeHead();
    			addTail(key, value);
    		}
    	}
    
    	private void removeHead() {
    		if (list.size() == cap) {// remove head
    			if (head.next != null) { // more than 1 element
    				head.next.prev = null;
    			}
    			ListNode temp = head;
    			head = head.next;
    			temp.next = null;
    			temp.prev = null;
    			int temp_key = temp.key;
    			temp = null;
    			list.remove(temp_key);
    		}
    	}
    
    	private void addTail(int key, int value) {
    		ListNode new_element = new ListNode(key, value);
    		if (tail != null) { // Add to tail
    			tail.next = new_element;
    			new_element.prev = tail;
    			tail = tail.next;
    		} else { // Initialize the head element
    			head = new_element;
    			tail = head;
    		}
    		list.put(new_element.key, new_element);
    	}
    
    	private void refreshNode(ListNode node) {
    		if (node.next != null) {
    			if (node.prev == null) {// head element
    				head = node.next;
    			} else {
    				node.prev.next = node.next;
    			}
    			node.next.prev = node.prev;
    			node.next = null;
    			tail.next = node;
    			node.prev = tail;
    			tail = tail.next;
    		} // else the element is the last one, do nothing
    	}
    }
    

  • 0
    Z

    @zmlzeze I updated my code with significant performance improvement. The original update function is useless since I confused about Java's reference mechanic and repeat useless hashmap update operation.


  • 0
    H

    Your code has bugs. As of now you don't even have a class LRUCache. How are you able to run it?


  • 0
    Z

    @hihihahahoho Sure, I just accidentally copied the outer class from other solution, just change

    class Solution{}
    

    to

    class LRUCache{}
    

    and it will work


Log in to reply
 

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