使用單鏈表實作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 = https://www.cnblogs.com/zsiscool/p/data;
this.next = next;
}
public T getData(){
return data;
}
public Node getNext(){
return next;
}
public void setNext(Node 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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/137103.html
標籤：Java
下一篇：生成亂數，時間格式轉換