lru算法c语言实现单链表,基于单链表实现LRU算法
赞
踩
基本思路：
1.如果数据已经在链表中已经存在了，则直接删除原数据，再插入头结点
2.若链表中不在：
2.1 若链表容量未满，则直接插入头结点
2.2 若链表容量已满，则先删除尾结点，再插入头结点
代码如下：
public class LRUBaseLinkedList {
/**
* 默认链表容量
*/
private final static Integer DEFAULT_CAPACITY=10;
/**
* 头结点
*/
private SNode headNode;
/**
* 链表长度
*/
private Integer length;
/**
* 链表容量
*/
private Integer capacity;
public LRUBaseLinkedList(){
this.headNode=new SNode<>();
this.capacity=DEFAULT_CAPACITY;
this.length=0;
}
public LRUBaseLinkedList(Integer capacity){
this.headNode=new SNode<>();
this.capacity=capacity;
this.length=0;
}
public void add(T data){
SNode preNode=findPreNode(data);
//链表中已经存在，则删除原数据，插入头结点
if(preNode!=null){
deleteElemOptim(preNode);
}else{
//链表中不存在则直接插入，若超出容量，则删除尾结点
if(length>=this.capacity){
deleteElemAtEnd();
}
}
insertElemAtBegin(data);
}
/**
* 删除preNode结点下一个元素
* @param preNode
*/
private void deleteElemOptim(SNode preNode){
//讲preNode后继指针替换
SNode temp=preNode.getNext();
preNode.setNext(temp.getNext());
temp=null;
length--;
}
/**
* 在链表头结点插入元素
* @param data
*/
private void insertElemAtBegin(T data){
SNode next=headNode.getNext();
headNode.setNext(new SNode(data,next));
length++;
}
/**
* 获取查找元素的前一个结点
* @param data
* @return
*/
private SNode findPreNode(T data){
SNode node=headNode;
while(node.getNext()!=null){
if(data.equals(node.getNext().getElement())){
return node;
}
node=node.getNext();
}
return null;
}
/**
* 删除尾结点
*/
private void deleteElemAtEnd(){
SNode ptr=headNode;
//空链表直接返回
if(ptr.getNext()==null){
return;
}
//倒数第二个结点
while(ptr.getNext()!=null){
ptr=ptr.getNext();
}
SNode tmp=ptr.getNext();
ptr.setNext(null);
tmp=null;
length--;
}
private static class SNode{
/**
* 结点
*/
T element;
/**
* 后继指针
*/
SNode next;
SNode(T element){
this.element=element;
}
SNode(T element,SNode next){
this.element=element;
this.next=next;
}
SNode(){
this.next=null;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public SNode getNext() {
return next;
}
public void setNext(SNode next) {
this.next = next;
}
}
复制代码
}
