链表的使用

LRU算法

一、使用单链表实现:新的访问来了之后链表中查询是否存在，如果存在且不说头节点则删除链表当前位置的数据把数据插入到头节点,如果不存在直接插入到头节点,当链表中的数据大小到达阈值时,需要删除尾结点的数据再插入到头节点

二、使用LinkedHashMap 

与HashMap相比LinkedHashMap维护的是一个具有双重链表的HashMap，LinkedHashMap支持2中排序。

一种是插入排序，即插入是什么顺序，读出来的就是什么顺序。

一种是使用排序，最近使用的会移至尾部例如 key1 key2 key3 key4，使用key3后为 key1 key2 key4 key3了。

accessOrder为true表示使用顺序，false表示插入顺序。

基于LinkedHashMap的使用顺序的特性，我们可以用来实现LRU算法

三、约瑟夫问题(丢手绢),单向环形链表实现

约瑟夫问题：有 N 个人围成一圈，每个人都有一个编号，编号由入圈的顺序决定，第一个入圈的人编号为 1，最后一个为 N，从第 k (1<=k<=N)个人开始报数，数到 m (1<=m<=N)的人将出圈，然后下一个人继续从 1 开始报数，直至所有人全部出圈，求依次出圈的编号。

package org.example.config;

public class MyNode {

Nodecur;

  int size;

  public MyNode(int i){

if(cur ==null){

cur =new Node(i);

        cur.next =cur;

        size++;

      }

}

public void addNode(int i){

if(cur!=null){

Node cur1 =new Node(i);

        if(size>=1){

cur1.next =cur.next;

            cur.next = cur1;

        }

size++;

      }

}

public void delNode(int i){

if(cur!=null){

int num =0;

        while(num

if(cur.next.data==i){

cur.next =cur.next.next;

              size--;

break;

            }

cur =cur.next;

            num++;

        }

}

}

public static void main(String[] args) {

MyNode mn1 =new MyNode(1);

      mn1.addNode(2);

      mn1.addNode(3);

      mn1.addNode(4);

      mn1.addNode(5);

      mn1.addNode(6);

      for(int i=0;i<3;i++){

mn1.cur = mn1.cur.next;

      }

System.out.println(mn1.cur.data);

      int i=0;

      while(mn1.cur != mn1.cur.next){

i++;

        if(i==4){

System.out.println(mn1.cur.data);

            mn1.delNode(mn1.cur.data);

            i=0;

        }

mn1.cur = mn1.cur.next;

      }

}

class Node {

int data;

      Nodenext;

      public Node(int data) {

this.data = data;

        this.next =null;

      }

}

}