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);}@Overrideprotected 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. 当缓存达到其容量限制时，最少使用的节点（链表头部的节点）将被移除，以确保缓存大小不超过设定的容量。