网页设计成品网站,房地产楼盘微信网站建设营销方案,下载app到手机上并安装,装饰工程有限公司经营范围这个双向链表采用的是有伪头节点和伪尾节点的 与上一篇文章中单链表的实现不同#xff0c;区别于在实例化这个链表时就初始化了的伪头节点和伪尾节点#xff0c;并相互指向#xff0c;在第一次添加节点时#xff0c;不需要再考虑空指针指向问题了。
/*** 通过链表与HashMa…这个双向链表采用的是有伪头节点和伪尾节点的 与上一篇文章中单链表的实现不同区别于在实例化这个链表时就初始化了的伪头节点和伪尾节点并相互指向在第一次添加节点时不需要再考虑空指针指向问题了。
/*** 通过链表与HashMap实现LRU缓存** author CC* version 1.0* since2023/9/27*/
public class LRUCache {private MapInteger, Node cache new HashMap();//哈希表private int size;//链表长度private int capacity;//缓存容量private Node first;//伪头节点private Node last;//伪尾节点/*** 将一个新节点添加到头部** param newNode 要添加的新节点*/private void addFirst(Node newNode) {//注意 顺序很重要//1、分配新节点的前驱和后继newNode.prev first;newNode.next first.next;//2、头节点原来的后继的前驱指向新节点first.next.prev newNode;//3、头节点的后继执行新节点first.next newNode;}/*** 删除一个节点** param node 要删除的节点*/private void deleteNode(Node node) {//要删除节点的后继和前驱相互指引node.prev.next node.next;node.next.prev node.prev;}/*** 将一个节点放到伪头节点后** param node 移动的节点*/private void moveToFirst(Node node) {//删除这个节点deleteNode(node);//添加一个头节点addFirst(node);}/*** 删除尾节点** return 返回删除的这个节点*/private Node deleteToLast() {//获得伪尾节点的前驱 也就是尾节点Node ret last.prev;//删除尾节点deleteNode(last.prev);return ret;}/*** 存入缓存** param key* param value*/public void put(int key, int value) {//从hash表中查询这个健Node node cache.get(key);//如果hash表中不存在要添加的健if (node null) {//创建一个新的节点Node newNode new Node(key, value);//将这个健和节点添加到hash表中cache.put(key, newNode);//将这个节点存到头节点中addFirst(newNode);//如果这个缓存已满if (size capacity) {//删除尾节点Node last deleteToLast();//从hash表中也删除这个健cache.remove(last.key);size--;}//如果hash表中存在要添加的健} else {//将新添加的值覆盖原来的值node.value value;//并移到头节点moveToFirst(node);}}/*** 获取缓存** param key 该缓存的健* return 返回 该节点的值*/public int get(int key) {//通过健从hash表中获取这个节点Node node cache.get(key);//如果为空 则返回-1if (node null) {return -1;}//否则 将该节点 移到头节点处moveToFirst(node);return node.value;}/*** 双向链表的遍历 头-尾** return*/Overridepublic String toString() {StringJoiner sj new StringJoiner(-);for (Node n first.next;n.next!null;nn.next){sj.add(String.valueOf(n.value));}return 头-尾:sj.toString();}/*** 构造方法** param capacity 设置缓存容量*/public LRUCache(int capacity) {size 0;//初始链表长度位0this.capacity capacity;//设置缓存容量first new Node();//实例化伪头节点last new Node();//实例化伪尾节点//初始头尾节点相互指向first.next last;last.prev first;}/*** 节点类*/class Node {int key; //键int value;//值Node prev;//前驱Node next;//后继/*** 无参构造*/public Node() {}/*** 有参构造** param key 健* param value 值*/public Node(int key, int value) {this.key key;this.value value;}}}测试 //实例一个缓存大小为7的LRU缓存LRUCache lruCache new LRUCache(5);lruCache.put(1,1);lruCache.put(2,2);lruCache.put(3,3);lruCache.put(4,4);lruCache.put(5,5);lruCache.put(6,6);System.out.println(依次存入1、2、3、4、5、6后的缓存lruCache);int l1 lruCache.get(1);System.out.println(取出1后的缓存lruCache,取出的值l1);int l2 lruCache.get(2);System.out.println(取出2后的缓存lruCache,取出的值l2);int l3 lruCache.get(3);System.out.println(取出3后的缓存lruCache,取出的值l3);lruCache.put(9,9);System.out.println(存入9后的缓存lruCache);
测试结果
