Java O(1) get/set solution, with map + double linked list


  • 0
    M

    This question is really practical. I have used similar code in a database system design project though this is more simple.

    public class LRUCache {
    
    	final int CAPACITY;
    	Map<Integer, DListNode> map;
    	DListNode head, tail;
    	
        public LRUCache(int capacity) {
        	CAPACITY = capacity;
        	map = new HashMap<>(CAPACITY);
        	head = new DListNode(0,0);
        	tail = new DListNode(0,0);
        	head.next = tail;
        	tail.next = head;
        }
        
        public int get(int key) {
        	DListNode node = map.get(key);
            if(node == null){
            	return -1;
            } else {
            	updateNode(node);
            	return node.val;
            }
        }
        
        public void set(int key, int value) {
        	DListNode node = map.get(key);
            if(node == null){
            	node = new DListNode(key, value);
            	if(map.size() < CAPACITY){
            		map.put(key, node);
            		addNode(node);
            	} else { // do LRU
            		policy_LRU(node);
            	}
            } else {
            	node.val = value;
            	map.put(key, node);
            	updateNode(node);
            }
        }
        
        private void policy_LRU(DListNode node){
        	//delete the last one
        	map.remove(tail.pre.key);
        	deleteNode(tail.pre);
        	//add the new one
        	map.put(node.key, node);
        	addNode(node);
        }
        
        private void updateNode(DListNode node){
            deleteNode(node);
            addNode(node);
        }
            
        private void addNode(DListNode node){
        	DListNode secondNode = head.next;
        	head.next = node;
        	node.pre = head;
        	secondNode.pre = node;
        	node.next = secondNode;
        }
        
        private void deleteNode(DListNode node){
        	DListNode preNode = node.pre;
        	DListNode nextNode = node.next;
        	preNode.next = node.next;
        	nextNode.pre = preNode;
        }
        
        class DListNode{
        	int key;
        	int val;
        	DListNode next;
        	DListNode pre;
        	DListNode(int key, int val){
        		this.key = key;
        		this.val = val;
        	}
        }
    }
    

  • 0
    F

    O(1) you are kidding me!!!!?


Log in to reply
 

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