A clean and simple Java solution using HashMap and Doubly LinkedList


  • 1
    H
    public class LRUCache {
        
        private Node head;
        private Node tail;
        private int capacity;
        private int size;
        private HashMap<Integer, Node> map;
        
        public LRUCache(int capacity) {
            this.head = null;
            this.tail = null;
            this.capacity = capacity;
            this.size = 0;
            this.map = new HashMap<Integer, Node>();
        }
        
        public int get(int key) {
            Node node = map.get(key);
            if (node != null) {
                refresh(node);
                return node.val;
            }
            return -1;
        }
        
        public void set(int key, int value) {
            Node node = map.get(key);
            if (node != null) {
                node.val = value;
                refresh(node);
            } else {
                node = new Node(key, value);
                add(node);
            }
        }
        
        private void refresh(Node node) {
            remove(node);
            add(node);
        }
        
        private void remove(Node node) {
            if (size == 1) {
                head = null;
                tail = null;
            } else if (node == head) {
                head = head.next;
                head.pre = null;
                node.next = null;
            } else if (node == tail) {
                tail = tail.pre;
                tail.next = null;
                node.pre = null;
            } else {
                node.pre.next = node.next;
                node.next.pre = node.pre;
                node.pre = null;
                node.next = null;
            }
            map.remove(node.key);
            size--;
        }
        
        private void add(Node node) {
            if (size == capacity) {
                remove(head);
            }
            if (size == 0) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                node.pre = tail;
                tail = node;
            }
            map.put(node.key, node);
            size++;
        }
        
        class Node {
            int key;
            int val;
            Node pre;
            Node next;
            
            public Node(int key, int val) {
                this.key = key;
                this.val = val;
                this.pre = null;
                this.next = null;
            }
        }
    }

Log in to reply
 

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