Best modularized solution


  • 0
    E
    class LRUCache {
    
        private DoublyLinkedList list;
        private Map<Integer, Node> map;
        private Map<Node, Integer> reverseMap;
        private int size;
        private int capacity;
    
        public LRUCache(int capacity) {
            this.capacity = capacity;
            list = new DoublyLinkedList();
            map = new HashMap<>();
            reverseMap = new HashMap<>();
        }
    
        public int get(int key) {
            int val = -1;
            if (map.containsKey(key)) {
                Node used = map.get(key);
                val = used.getVal();
                list.use(used);
            }
            return val;
        }
    
        public void put(int key, int value) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                node.setVal(value);
                list.use(node);
            } else {
                if (isFull()) {
                    Node victim = list.removeFromTail();
                    int keyToEvict = reverseMap.get(victim);
                    map.remove(keyToEvict);
                    reverseMap.remove(victim);
                    size--;
                }
                Node toAdd = new Node(value);
                map.put(key, toAdd);
                reverseMap.put(toAdd, key);
                list.addToHead(toAdd);
                size++;
            }
        }
    
        private boolean isFull() {
            return size == capacity;
        }
    }
    
    class Node {
        private int val;
        private Node prev;
        private Node next;
    
        public Node(int val) {
            this.val = val;
        }
    
        public int getVal() {
            return val;
        }
    
        public void setVal(int val) {
            this.val = val;
        }
    
        public Node getPrev() {
            return prev;
        }
    
        public void setPrev(Node prev) {
            this.prev = prev;
        }
    
        public Node getNext() {
            return next;
        }
    
        public void setNext(Node next) {
            this.next = next;
        }
    }
    
    class DoublyLinkedList {
    
        private Node head;
        private Node tail;
    
        public DoublyLinkedList() {
            head = new Node(0);
            tail = new Node(0);
            head.setNext(tail);
            tail.setPrev(head);
        }
    
        public Node removeFromTail() {
            Node toRemove = tail.getPrev();
            return remove(toRemove);
        }
    
        private Node remove(Node toRemove) {
            Node prev = toRemove.getPrev();
            Node next = toRemove.getNext();
            prev.setNext(next);
            next.setPrev(prev);
            toRemove.setPrev(null);
            toRemove.setNext(null);
            return toRemove;
        }
    
        public void addToHead(Node toAdd) {
            Node next = head.getNext();
            head.setNext(toAdd);
            toAdd.setPrev(head);
            toAdd.setNext(next);
            next.setPrev(toAdd);
        }
    
        public void use(Node used) {
            remove(used);
            addToHead(used);
        }
    }
    

Log in to reply
 

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