Simple improvement on double linked list


  • 0

    Two minor improvements:

    1. add two sentinel as head and tail so we do not have to deal with corner case when the node is head or tail
    2. when node is the first node we do not need to delete and move it.
    public class LRUCache {
        Map<Integer, Node> map;
        Node head;
        Node tail;
        int capacity;
        
        public LRUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>();
            head = new Node(Integer.MAX_VALUE,Integer.MAX_VALUE);
            tail = new Node(Integer.MAX_VALUE,Integer.MAX_VALUE);
            head.next=tail;
            tail.pre=head;
        }
        
        private void delete(Node cur){
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;
            cur.pre=null;
            cur.next=null;
        }
        
        private void addToHead(Node n){
            Node next = head.next;
            n.next=next;
            next.pre=n;
            head.next=n;
            n.pre=head;
        }
        
        
        public int get(int key) {
            Node n = map.get(key);
            if(n==null) return -1;
            if(head.next!=n){
                delete(n);
                addToHead(n);    
            }
            return n.val;
        }
        
        public void set(int key, int value) {
            Node n = map.get(key);
            if(n==null){
                if(capacity==0){
                    map.remove(tail.pre.key);
                    delete(tail.pre);
                    capacity++;
                }
                n = new Node(key, value);
                map.put(key, n);
                addToHead(n);
                capacity--;
            }else{
                if(n!=head.next){
                    delete(n);  
                    addToHead(n);
                }
                n.val=value;
            }
        }
        
        public class Node{
            int key;
            int val;
            Node pre = null;
            Node next = null;
            public Node(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.