146. LRU 缓存 - 力扣（LeetCode）
这道题采用双向链表加哈希表；
哈希表是为了随机访问，双向链表是为了能够确定位置
这里面注意的是我们需要一个哨兵节点来辅助，需要让哨兵节点的prev.next以及next.next指向自己，即这里是一个双向循环链表，并且我们每次头插节点的时候都是头插在哨兵节点之后
class LRUCache {//这里put和get想实现O1那么就需要使用哈希表，但是哈希表是没有位置观念的//比如我们想删除最久插入的元素，那么只能一个个遍历，而有位置观念的就是数组和链表了//但是我们每次插入元素的时候都要放到最前面也就是头插，如果用数组的话，那么元素需要//整体移动，所以采用双向链表static class Node{int key;int val;Node prev;Node next;Node(int k ,int v){key = k;val = v;}}private int capacity;private Map<Integer,Node> map = new HashMap<>();//设置一个哨兵节点private Node head = new Node(0,0);//构造初始化public LRUCache(int capacity) {this.capacity = capacity;head.next = head;head.prev = head;}public int get(int key) {//获取最新节点的值Node node = getNode(key);return node == null ? -1 : node.val;}public void put(int key, int value) {Node node = getNode(key);if(node != null){map.put(key,node);node.val = value;return;} //不存在插入Node newNode = new Node(key,value);addLeft(newNode);map.put(key,newNode);if(map.size() > capacity) {Node last = head.prev;remove(last);map.remove(last.key);}}private Node getNode(int key){Node node = map.get(key);if(node == null) return null;remove(node);addLeft(node);return node;}private void remove(Node node){node.next.prev = node.prev;node.prev.next = node.next;}private void addLeft(Node node){//插到烧饼节点后面node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;// node.prev.next = node;// node.next.prev = node;}
}
