35、链表-LRU缓存

思路：

        首先要了解LRU缓存的原理，首先定下容量，每次get请求和put请求都会把当前元素放最前/后面，如果超过容量那么头部/尾部元素就被移除，所以最近最少使用的元素会被优先移除，保证热点数据持续存在。 不管放在头部还是尾部都可以。看你怎么定义

        那么如何实现呢？有两种方式第一种直接继承LinkedHashMap 这个是已经帮我们实现的，代码如下：

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
 
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
 
    // 这个可不写
    public void put(int key, int value) {
        super.put(key, value);
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

第二种就是手动去实现了，代码如下：

class LRUCache extends AbstractLRUCache<Integer, Integer> {
 
    public LRUCache(int capacity) {
        super(capacity);
 
    }
 
    public int get(int key) {
        Integer ans = super.get(key);
        return ans == null ? -1 : ans;
    }
 
    public void put(int key, int value) {
        super.set(key, value);
    }
}
 
abstract class AbstractLRUCache<K, V> {
 
    private Map<K, Node<K, V>> keyNodeMap;
    private NodeDoubleLinkedList<K, V> nodeList;
    private final int capacity;
 
    public AbstractLRUCache(int cap) {
        if (cap < 1) {
            throw new RuntimeException("should be more than 0");
        }
        keyNodeMap = new HashMap<>();
        nodeList = new NodeDoubleLinkedList<>();
        capacity = cap;
    }
 
    public V get(K key) {
        if (keyNodeMap.containsKey(key)) {
            Node<K, V> res = keyNodeMap.get(key);
            nodeList.moveNodeToTail(res);
            return res.value;
        }
        return null;
    }
 
    public void set(K key, V value) {
        if (keyNodeMap.containsKey(key)) {
            Node<K, V> node = keyNodeMap.get(key);
            node.value = value;
            nodeList.moveNodeToTail(node);
        } else {
            Node<K, V> newNode = new Node<>(key, value);
            keyNodeMap.put(key, newNode);
            nodeList.addNode(newNode);
            if (keyNodeMap.size() == capacity + 1) {
                removeMostUnusedCache();
            }
        }
    }
 
    private void removeMostUnusedCache() {
        Node<K, V> node = nodeList.removeHead();
        keyNodeMap.remove(node.key);
    }
 
    class Node<K, V> {
        public K key;
        public V value;
        public Node<K, V> last;
        public Node<K, V> next;
 
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
 
    class NodeDoubleLinkedList<K, V> {
        private Node<K, V> head;
        private Node<K, V> tail;
 
        public NodeDoubleLinkedList() {
            head = null;
            tail = null;
        }
 
        public void addNode(Node<K, V> newNode) {
            if (newNode == null) {
                return;
            }
            if (head == null) {
                head = newNode;
                tail = newNode;
            } else {
                tail.next = newNode;
                newNode.last = tail;
                tail = newNode;
            }
        }
 
        public void moveNodeToTail(Node<K, V> node) {
            if (this.tail == node) {
                return;
            }
            if (this.head == node) {
                this.head = node.next;
                this.head.last = null;
            } else {
                node.last.next = node.next;
                node.next.last = node.last;
            }
            node.last = this.tail;
            node.next = null;
            this.tail.next = node;
            this.tail = node;
        }
 
        public Node<K, V> removeHead() {
            if (this.head == null) {
                return null;
            }
            Node<K, V> res = this.head;
            if (this.head == this.tail) {
                this.head = null;
                this.tail = null;
            } else {
                this.head = res.next;
                res.next = null;
                this.head.last = null;
            }
            return res;
        }
    }
}

以下是代码实现的功能要点：

1. AbstractLRUCache 是一个抽象类，它包含了 LRU 缓存的核心逻辑，如添加节点、移动节点到链表尾部、移除最少使用的节点等。

2. LRUCache 是 AbstractLRUCache 的具体实现，它提供了 get 和 put 方法来与缓存进行交互。这些方法调用了抽象类中的方法来实现 LRU 逻辑。

3. Node 类代表缓存中的一个条目，包含键、值以及指向前一个和后一个节点的指针。

4. NodeDoubleLinkedList 是一个双向链表，用于按照访问顺序维护缓存中的节点。最近访问的节点被移动到链表的尾部，而最少使用的节点位于链表的头部。

5. 当缓存达到其容量限制时，最少使用的节点（链表头部的节点）将被移除，以确保缓存大小不超过设定的容量。