[146 LRU缓存](https://leetcode.cn/problems/lru-cache/)

分析

维护一个双向链表保存缓存中的元素。
如果元素超过容量阈值，则删除最久未使用的元素。为了实现这个功能，将get(), put()方法获取的元素添加到链表首部。
为了在O(1)时间复杂度执行get()方法，再新建一个映射表，缓存key与链表节点。

源码

class LRUCache {private int size;private int capacity;private Map<Integer, Node> cache = new HashMap<>();private Node head;private Node tail;public LRUCache(int capacity) {this.capacity = capacity;this.size = 0;this.head = new Node();this.tail = new Node();this.head.next = this.tail;this.tail.prev = this.head;}public int get(int key) {Node node = cache.get(key);if (node == null) {return -1;}moveToHead(node);return node.value;}public void put(int key, int value) {Node node = cache.get(key);if (node == null) {node = new Node(key, value);cache.put(key, node);addToHead(node);size++;if (size > capacity) {Node tail = removeTail();cache.remove(tail.key);size--;}}node.value = value;moveToHead(node);}private void addToHead(Node node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(Node node) {removeNode(node);addToHead(node);}private Node removeTail() {Node res = tail.prev;removeNode(res);return res;}class Node {int key;int value;Node prev;Node next;public Node(int key, int value) {this.key = key;this.value = value;}public Node() {}}
}