【数据结构与算法】通过双向链表和HashMap实现LRU缓存 详解

这个双向链表采用的是有伪头节点和伪尾节点的 与上一篇文章中单链表的实现不同，区别于在实例化这个链表时就初始化了的伪头节点和伪尾节点，并相互指向，在第一次添加节点时，不需要再考虑空指针指向问题了。

/*** 通过链表与HashMap实现LRU缓存** @author CC* @version 1.0* @since2023/9/27*/
public class LRUCache {private Map<Integer, 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;n=n.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);

测试结果