广州网站建设与网页设计,微信小程序投票怎么快速投多票,最新的网站建设软件,icp备案网站接入信息怎么填LRU cache的实现是面试常见的题目#xff0c;思路比较简单#xff0c;可以参考思路 这个题目在实际面试中容易出错#xff0c;主要是npe和头节点与尾节点的更新#xff0c;有没有办法避免这一点呢#xff0c;这时可以发现伪节点的好处#xff0c;永远不用更新头尾节点思路比较简单可以参考思路 这个题目在实际面试中容易出错主要是npe和头节点与尾节点的更新有没有办法避免这一点呢这时可以发现伪节点的好处永远不用更新头尾节点也不用担心出现npe
在双向链表的实现中使用一个伪头部dummy head和伪尾部dummy tail标记界限这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。
代码实现
import java.util.HashMap;
import java.util.Map;public class LRUCache {class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int _key, int _value) {key _key; value _value;}}private MapInteger, DLinkedNode cache new HashMapInteger, DLinkedNode();private int size;private int capacity;private DLinkedNode head, tail;public LRUCache(int capacity) {this.size 0;this.capacity capacity;// 使用伪头部和伪尾部节点head new DLinkedNode();tail new DLinkedNode();head.next tail;tail.prev head;}public int get(int key) {DLinkedNode node cache.get(key);if (node null) {return -1;}// 如果 key 存在先通过哈希表定位再移到头部moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node cache.get(key);if (node null) {// 如果 key 不存在创建一个新的节点DLinkedNode newNode new DLinkedNode(key, value);// 添加进哈希表cache.put(key, newNode);// 添加至双向链表的头部addToHead(newNode);size;if (size capacity) {// 如果超出容量删除双向链表的尾部节点DLinkedNode tail removeTail();// 删除哈希表中对应的项cache.remove(tail.key);--size;}}else {// 如果 key 存在先通过哈希表定位再修改 value并移到头部node.value value;moveToHead(node);}}private void addToHead(DLinkedNode node) {node.prev head;node.next head.next;head.next.prev node;head.next node;}private void removeNode(DLinkedNode node) {node.prev.next node.next;node.next.prev node.prev;}private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);}private DLinkedNode removeTail() {DLinkedNode res tail.prev;removeNode(res);return res;}
}
