//构造方法 public LRUCache(int capacity) { this.capacity = capacity; map = new HashMap<>(capacity); first = new Node(); //初始化虚拟头尾节点 last = new Node(); first.next = last; //开始没有任何键值对 头尾节点互指 last.prev = first; } //get方法 public int get(int key) { Node node = map.get(key); if(node == null) return -1;
//将该节点先删后插入到最前面 用完放前面 removeNode(node); addAfterFirst(node);
return node.value; } //put方法 public void put(int key, int value) { Node node = map.get(key); if(node != null){ node.value = value; //将该节点先删后插入到最前面 更新双向链表 removeNode(node); }else{ //添加一对新的key-value if(map.size() == capacity){ //淘汰最久未用的node //map中的key要删除 双向链表中的虚拟尾节点前的节点也要删除 removeNode(map.remove(last.prev.key)); } map.put(key,node = new Node(key,value)); //插入新节点 } addAfterFirst(node); //更新双向链表 }
//从双向链表中删除节点 private void removeNode(Node node){ node.next.prev = node.prev; node.prev.next = node.next; } //将该节点插入到虚拟头节点前面 private void addAfterFirst(Node node){ node.next = first.next; first.next.prev = node; node.prev = first; first.next = node; }
//静态内部类 value节点是一个个Node private static class Node{ public int key; public int value; public Node prev; public Node next; public Node(int key,int value){ this.key = key; this.value = value; } public Node(){} } }
/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */