使用单链表实现LRU(Least Recently Used)淘汰缓存机制
需求:存在一个单链表,在单链表尾部的都是越早之前添加的元素。
- 当元素被访问到时,会添加进缓存(也就是这个单链表中)。
- 如果这个元素在之前已经被缓存到了链表中,则将这个元素从原来的位置删除,用头插法放到链表的头部。
-
如果这个元素不在链表中,则根据链表的容量进行判断
- 缓存容量未满时,直接用头插法,放到链表的头部
- 缓存容量已满时,首先删除链表尾部的元素,再将元素进行插入到头部。
创建Node对象
package com.codezs.datastruct.mylinkedlist; public class Node<T> { T data; Node<T> next; Node(Node<T> next) { this.next = next; } public Node(T data, Node<T> next) { this.data = data; this.next = next; } public T getData(){ return data; } public Node<T> getNext(){ return next; } public void setNext(Node<T> next){this.next = next;}; }
对单链表实现LRU淘汰缓存机制的实现
package com.codezs.datastruct.mylinkedlist; public class MyLinkedList<T> { //默认链表容量 private final static Integer DEFAULT_CAPACITY = 10; //头结点 private Node head; //链表长度 private Integer length; //链表容量 private Integer capacity; public MyLinkedList() { this.capacity = DEFAULT_CAPACITY; this.head = new Node(null); this.length = 0; } public MyLinkedList(Integer capacity) { this.capacity = capacity; this.head = new Node(null); this.length = 0; } public Node getHead(){ return head; } //添加新的元素 public void add(T data){ Node<T> preNode = findPreNode(data); if (preNode != null){ remove(preNode); insertNode(data); } else { if (length >= this.capacity){ deleteNodeAtEnd(); } insertNode(data); } } //获取查找到元素的前一个节点 private Node<T> findPreNode(T data){ Node node = head; while(node.getNext() != null){ if (data.equals(node.getNext().getData())){ return node; } node = node.getNext(); } return null; } //删除node结点下一个元素 private void remove(Node preNode){ Node node = preNode.getNext(); preNode.setNext(node.getNext()); node = null; length--; } //头插法 private void insertNode(T data){ Node node = head.getNext(); head.setNext(new Node(data,node)); length++; } //删除链表中最后一个元素 private void deleteNodeAtEnd(){ Node node = head; if (node.getNext() == null) { return; } while (node.getNext().getNext() != null) { node = node.getNext(); } Node nextNode = node.getNext(); node.setNext(null); nextNode = null; length--; } public boolean isEmpty(){ return length == 0; } public int size(){ return length; } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 图解kubernetes容器运行时状态缓存数据结构
- 数据结构与算法 | 如何实现LRU缓存淘汰算法
- 数据结构 – 用于构建文件系统的数据结构?
- 荐 用Python解决数据结构与算法问题(三):线性数据结构之栈
- 数据库索引背后的数据结构
- 基础数据结构及js数据存储
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。