Java Solution HashMap + Double LinkedList + Sentinel Node


  • 0
    public class LRUCache {
        
        class Node {
            Node prev;
            Node next;
            int key;
            int value;
        }
        
        Map<Integer, Node> cache;
        int capacity;
        Node sentinel; // sentinel's next is first element, sentinel's prev is last element;
        
        public LRUCache(int capacity) {
            this.capacity = capacity; // assume capacity always > 0
            cache = new HashMap<>();
            sentinel = new Node();
            sentinel.prev = sentinel;
            sentinel.next = sentinel;
        }
        
        private void removeNode(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        
        private void addNode(Node node) {
            Node firstNode = sentinel.next;
            node.next = firstNode;
            node.prev = sentinel;
            firstNode.prev = node;
            sentinel.next = node;
        }
        
        public int get(int key) {
            if(cache.containsKey(key)) {
                Node node = cache.get(key);
                removeNode(node);
                addNode(node);
                return node.value;
            } else {
                return -1;
            }
        }
        
        public void set(int key, int value) {
            if(cache.containsKey(key)) {
                Node node = cache.get(key);
                node.value = value;
                removeNode(node);
                addNode(node);
            } else {
                if(cache.size()==capacity) {
                    Node lastNode = sentinel.prev;
                    removeNode(lastNode);
                    cache.remove(lastNode.key);
                }
                Node node = new Node();
                node.key = key;
                node.value = value;
                addNode(node);
                cache.put(key, node);
            }
        }
    }

Log in to reply
 

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