当前位置:   article > 正文

lru算法c语言实现单链表,基于单链表实现LRU算法

lru链表c语言实现思路

基本思路:

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;

}

}

复制代码

}

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/163728?site
推荐阅读
相关标签
  

闽ICP备14008679号