https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked

最近最久未使用，显然我们需要维护一个使用队列，最近使用过的在队尾，未使用过的靠近队首
并且他要求函数 get 必须以 O(1) 的平均时间复杂度运行显然我们需要用到hash
put 必须以 O(1)的平均时间复杂度运行显然只有链表能做到，并且我们选择双向链表实现
为什么用双向链表而不是单向链表？
将某个节点移动到链表头部或者将链表尾部节点删去，都要用到删除链表中某个节点这个操作。你想要删除链表中的某个节点，需要找到该节点的前驱节点和后继节点。对于寻找后继节点，单向链表和双向链表都能通过 next 指针在O(1)时间内完成；对于寻找前驱节点，单向链表需要从头开始找，也就是要O(n)时间，双向链表可以通过前向指针直接找到，需要O(1)时间。综上，要想在O(1)时间内完成该操作，当然需要双向链表.

public class LRUCache {class Node{int key;int value;Node prev;Node next;public Node(int key, int value) {this.key = key;this.value = value;this.prev = null;this.next = null;}}int capacity;//容量,最大可以存储多少个节点int currSize;//当前存储的节点数Node head, tail;//头节点,尾节点Map<Integer, Node> map = new HashMap<>();//key-valuepublic LRUCache(int capacity) {this.capacity = capacity;}public int get(int key) {if(map.containsKey(key)){Node node = map.get(key);removeNode(node);return node.value;}return -1;}public void put(int key, int value) {if(map.containsKey(key)){Node node = map.get(key);node.value = value;removeNode(node);} else {if(currSize == capacity){map.remove(head.key);removeNode(head);/*if(capacity == 1) {//当前只有一个节点head.key = key;head.value = value;} else {//当前节点不是尾节点，则他会被放到尾节点tail.key = key;tail.value = value;}*/tail.key = key;tail.value = value;map.put(key, tail);} else if(currSize < capacity){Node node = new Node(key, value);map.put(key, node);if(currSize == 0) {//当前没有节点head = node;tail = node;} else {tail.next = node;node.prev = tail;tail = node;}currSize++;}}}//将节点node移动到链表尾public void removeNode(Node node){if(node.next == null) return;if(node.prev == null) {//当前节点是头节点head = node.next;node.next.prev = null;node.next = null;tail.next = node;node.prev = tail;tail = node;} else {//当前节点不是头节点和尾节点node.prev.next = node.next;node.next.prev = node.prev;node.next = null;node.prev = tail;tail.next = node;tail = node;}}public static void main(String[] args) {String[] str = {"LRUCache","put","get","put","get","get"};int[][] arr = {{1},{2,1},{2},{3,2},{2},{3}};LRUCache lruCache = null;List<Integer> list = new ArrayList<>();for(int i = 0; i < str.length; i++) {if(str[i].equals("LRUCache")) {lruCache = new LRUCache(arr[i][0]);}if(str[i].equals("put")) {lruCache.put(arr[i][0], arr[i][1]);}if(str[i].equals("get")) {list.add(lruCache.get(arr[i][0]));continue;}list.add(null);}System.out.println(list);}
}