LinkedList增删改查链表算法。

LRU算法：

1、插入数据到头节点

2、访问数据命中。则将数据移到头部。

3、链表满 的时候，删除尾部节点。

public class LinkedList<T> {
Node nodelist;
int size;

public LinkedList(){
size=0;
}
//插入节点到头部
public void put(T data){
Node cur=new Node(data,nodelist);//新创建的节点next指向node
nodelist=cur;//node重新指向头部
size++;
}
public void put(int index,T data){
checkPositionIndex(index);
Node cur=nodelist;//创建节点cur 等于头集结点node
Node head=nodelist;
for(int i=0;i<index;i++){
head=cur;
cur=cur.next;
}
Node node=new Node(data,cur); 
head.next=node;
size++;
}
public void checkPositionIndex(int index) {
if(!(index>=0&&index<=size)){//index不合法
throw new IndexOutOfBoundsException("inedx: "+index+", size: "+size);
}

}
//删除节点 头节点
public T remove(){
if(nodelist!=null){
Node node=nodelist;
nodelist=nodelist.next;
node.next=null;//gc
size--;
return node.data;
}else{
return null;
}

}
//删除指定位置
public T remove(int index){
checkPositionIndex(index);
Node head=nodelist;
Node cur=nodelist;
for(int i=0;i<index;i++){
head=cur;
cur=cur.next;
}
//删除cur节点
head.next=cur.next;
cur.next=null;
size--;
return cur.data;
}
//删除尾部节点
public T removeLast(){
if(nodelist!=null){
Node node=nodelist;
Node cur=nodelist;
while(cur.next!=null){
node=cur;
cur=cur.next;
}
node.next=null;
size--;
return cur.data;
}else{
return null;
}

}
//修改节点
public void set(int index,T newData){
Node node=nodelist;
for(int i=0;i<index;i++){
node=node.next;
}
node.data=newData;
}
//查询节点 头部节点
public T get(){
Node node=nodelist;
if(node!=null){
return node.data;
}else{
return null;
} 
}

public class LruLinkedList<T> extends LinkedList<T> {
int memory_size;
public LruLinkedList(int size){
memory_size=size;
}
//LRU添加节点
public void Lruput(T data){
if(size>=memory_size){//删除尾部节点在插入
removeLast();
put(data);
}else{
put(data);
}
}
//删除尾部节点
public T Lruremove(){
return removeLast();
}
//LRU访问  访问数据插入头部，若链表满则删除尾部节点
public T Lruget(int index){
checkPositionIndex(index);
Node pre=nodelist;
Node cur=nodelist;
for(int i=0;i<index;i++){
pre=cur;
cur=cur.next;
}
T data=cur.data;
pre.next=cur.next;
Node head=nodelist;
cur.next=head;
nodelist=cur;
return data;
}
public static void main(String[] args) {
LruLinkedList<String> lrulist=new LruLinkedList<String>(8);
for (int i=0;i<7;i++){
lrulist.Lruput("name"+i);
}
lrulist.toString();
lrulist.Lruget(1);
lrulist.toString();

lrulist.Lruput("3");
lrulist.toString();

lrulist.Lruget(7);
lrulist.toString();

lrulist.Lruput("9");
lrulist.toString();
}

}