Clean Java solution. HashMap, doubly linked list, plus dummy head and tail.


  • 0
    G

    Basic idea is let the hashmap to do the store and fetch job, and this would give average O(1) performance on get and set. Also maintain a queue implemented using doubly linked list for priority job. This data structure ensures a O(1) time complexity on enqueue, dequeue, and prioritize certain node. Hope you guys like it.

    public class LRUCache {
        
        private final int capacity;
        private HashMap<Integer, LRUNode> cache;
        private LRUNode head;
        private LRUNode tail;
        
        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.cache = new HashMap<>();
            this.head = new LRUNode(0, 0); // dummy node.
            this.tail = new LRUNode(0, 0); // dummy node.
            head.next = tail;
            tail.prev = head;
        }
        
        public int get(int key) {
            
            int result = -1;
            
            LRUNode retVal = cache.get(key);
            if (retVal != null) {
                updateQueue(retVal);
                result = retVal.value;
            }
            
            return result;
        }
        
        public void set(int key, int value) {
            
            LRUNode retVal = cache.get(key);
            
            if (retVal != null) {
                updateQueue(retVal);
                retVal.value = value;
            } else {
                if (cache.size() == capacity) {
                    int deleted = dequeue();
                    cache.remove(deleted);
                }
                LRUNode node = new LRUNode(key, value);
                enqueue(node);
                cache.put(key, node);
            }
        }
        
        // move a specific node to the tail.
        private void updateQueue(LRUNode node) {
            
            // it has been used last time, no need to update the queue.
            if (tail.prev == node) {
                return;
            }
            
            removeNode(node);
            enqueue(node);
        }
        
        // add a node to the tail.
        private void enqueue(LRUNode node) {
            
            // connect to second to last node.
            tail.prev.next = node;
            node.prev = tail.prev;
            
            // connect to tail;
            tail.prev = node;
            node.next = tail;
        }
        
        // remove the first node in the queue.
        private int dequeue() {
            LRUNode node = head.next;
            removeNode(node);
            return node.key;
        }
        
        // remove a specific node from the queue.
        private void removeNode(LRUNode node) {
            
            // no incoming reference from neighbors.
            node.prev.next = node.next;
            node.next.prev = node.prev;
            
            // no outgoing reference to neighbors.
            node.prev = null;
            node.next = null;
        }
        
        // the doubly linked list node class.
        private class LRUNode {
            
            int key;
            int value;
            
            LRUNode prev;
            LRUNode next;
            
            LRUNode(int key, int value) {
                this.key = key;
                this.value = value;
                this.prev = null;
                this.next = null;
            }
        }
    }
    

Log in to reply
 

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