Java doubly linked list solution


  • 0
    public class LRUCache {
    
        final class Node {
            int key, value;
            Node next, prev;
    
            Node(int key, int value) {
                this.key = key;
                this.value = value;
            }   
        }   
    
        private final int cap;
        private final Node dummy = new Node(0, 0); 
        private final HashMap<Integer, Node> map = new HashMap<>();
    
        public LRUCache(int capacity) {
            cap = capacity;
            (dummy.next = dummy).prev = dummy;
        }   
    
        public int get(int key) {
            Node node = map.get(key);
            if (node == null)
                return -1; 
            setRecent(node);
            return node.value;
        }   
    
        public void set(int key, int value) {
            Node node = map.get(key);
            if (node == null) {
                node = new Node(key, value);
                map.put(key, node);
                append(node);
                if (map.size() > cap) {
                    map.remove(dummy.next.key);
                    unlink(dummy.next);
                }   
            } else {
                node.value = value;
                setRecent(node);
            }
        }
    
        private void append(Node node) {
            Node prev = dummy.prev;
            (prev.next = node).prev = prev;
            (node.next = dummy).prev = node;
        }
    
        private void setRecent(Node node) {
            unlink(node);
            append(node);
        }
    
        private void unlink(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }
    

Log in to reply
 

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