Java Doubly linked list with sentinel node for easy maintenance


  • 1
    public class LRUCache {
        DListNode sentinel;
        Map<Integer, DListNode> map;
        int count;
        int capacity;
        
        public LRUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>();
            sentinel = new DListNode(0, 0);
            sentinel.next = sentinel;
            sentinel.prev = sentinel;
            count = 0;
        }
        
        public int get(int key) {
            if (!map.containsKey(key))
                return -1;
            reorder(key);
            return map.get(key).val;
        }
        
        public void set(int key, int value) {
            if (map.containsKey(key)) {
                map.get(key).val = value;
                reorder(key);
            } else {
                if (count == capacity) {
                    map.remove(sentinel.prev.key);
                    sentinel.prev = sentinel.prev.prev;
                    sentinel.prev.next = sentinel;
                    count--;
                }
                DListNode n = new DListNode(key, value);
                map.put(key, n);
                n.next = sentinel.next;
                n.prev = sentinel;
                sentinel.next.prev = n;
                sentinel.next = n;
                count++;
            }
        }
        
        private void reorder(int key) {
            DListNode n = map.get(key);
            if (sentinel.next == n)
                return;
            n.prev.next = n.next;
            n.next.prev = n.prev;
            
            n.prev = sentinel;
            n.next = sentinel.next;
            sentinel.next.prev = n;
            sentinel.next = n;
        }
    }
    
    class DListNode {
        public DListNode next;
        public DListNode prev;
        int key;
        int val;
        public DListNode(int k, int v) {
            key = k;
            val = v;
        }
    }

Log in to reply
 

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