LeetCode146. LRU cache

LRU Full name Least Recently Used, The least used recently , The first time I heard this concept was in the operating system course of my junior , For page replacement algorithm , For virtual page storage management services .

LRU The proposed algorithm is based on a fact , Pages that are frequently used in the previous instructions are likely to be frequently used in the next few instructions , Conversely, if you haven't used it for a long time, you think you won't use it next , This is the principle of locality

Now? LRU Algorithms are also often used as cache obsolescence strategies .

LeetCode146. LRU Cache is such a problem , It is said that this is also a common point of interview

In fact, if you understand the principle and use the right method, it is not difficult

  Obviously, this cache is in order , Eliminate cache from the end of the bidirectional linked list , Add and get Methods put the node at the head , It's not difficult to follow the code thinking

public class LRUCache {
    private Map<Integer, MyLinkedNode> cache = new HashMap<Integer, MyLinkedNode>();
    private int capacity;// Initialize capacity 
    private int size;// Cache existing quantity 
    private MyLinkedNode head,tail;
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new MyLinkedNode();
        tail = new MyLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        MyLinkedNode node = cache.get(key);
        if(node == null){
            return -1;
        }
        moveToHead(node);// Every time get Just put the node into the head , It means using more 
        return node.value;
    }

    public void put(int key, int value) {
        MyLinkedNode node = cache.get(key);
        if(node == null){// If this node does not exist, create one and add it to the cache 
            MyLinkedNode newNode = new MyLinkedNode(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            ++size;
            if(size > capacity){
                // If the capacity exceeds, delete the tail node of the linked list 
                MyLinkedNode tail = deleteTail();
                cache.remove(tail.key);// According to this key Index delete cache The key value in it is right 
                --size;
            }
        }else {// This key If it exists , Just modify value And move to the head 
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(MyLinkedNode node){// Add nodes to the chain header 
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    private void moveToHead(MyLinkedNode node){// Transfer the nodes in the linked list to the head 
        removeNode(node);
        addToHead(node);
    }
    private void removeNode(MyLinkedNode node){// Delete node 
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private MyLinkedNode deleteTail(){// Delete tail node 
        MyLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }

    class MyLinkedNode{// Two-way list node 
        int key;
        int value;
        MyLinkedNode prev;
        MyLinkedNode next;
        public MyLinkedNode(){}
        public MyLinkedNode(int key,int value){
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1,1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }

}

When I read the comment section of this topic, someone said , Why does the customized node have key This attribute ,cache Variables are not based on key Did you save it , There is only one in the node value Is it not good?

without key If so, we need to delete the tail node when we eliminate the cache , Note that the node we deleted only dereferences the nodes in the bidirectional linked list , But this node is map Type of cache It's still real , If we don't have any nodes key What to use as an index to delete cache The key value in it is right . This is the maintenance in the user-defined linked list node key The key