双向链表

在单链表的基础上，每个节点增加了一个pre属性指向前一个节点。

因为单链表只有next指针，因此只能单向遍历。而双向链表可以从前或从后遍历。另外也可以自我删除，也就是不用借助被删节点的前一个节点进行删除，直接靠自己就行。

增删改查

节点增加了pre指向前一个节点

//双向链表的节点
class StudentNode2{
    public int no;
    public String name;
    StudentNode2 next;
    StudentNode2 pre;

    public StudentNode2(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "StudentNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}

先遍历找到链表中的最后一个元素，再分别连上next和pre

//向链表中增加元素，直接加在末尾
    public void add(StudentNode2 node){
        //遍历链表，找到链表的最后
        StudentNode2 temp=head;
        while (true){
            if (temp.next==null){
                break;
            }else if(temp.next.no==node.no){
                throw new RuntimeException("重复添加！");
            }
            //遍历链表
            temp=temp.next;
        }
        //temp指向链表最后一个元素,向temp后添加新元素
        temp.next=node;
        node.pre=temp;
    }

找到添加位置的前一个，然后node.next=temp.next;连上后续不丢失，temp.next=node;与前面连接，node.pre = temp;反向连接，如果是加在链表的最末尾，后面是null，node.next有个空指针异常的问题，因此要加个判断。

//向链表中有顺序的添加元素，如果编号重复，添加失败
    public void addByOrder(StudentNode2 node){
        //根据编号找到需要添加的位置
        StudentNode2 temp=head;
        while (true){
            if(temp.next==null){
                break;
            }
            if(temp.next.no>node.no){
                break;
            }
            if(temp.next.no==node.no){
                throw new RuntimeException("重复添加！");
            }
            temp=temp.next;
        }

        node.next=temp.next;
        temp.next=node;
        node.pre = temp;
        if(node.next!=null) {
            node.next.pre = node;
        }
    }

没啥变化

//根据编号修改链表
    public void updata(int no,String name){
        //遍历找到需要修改的节点
        StudentNode2 temp=head.next;
        //是否找到该节点
        boolean flag=false;
        while (true){
            if(temp==null){
                break;
            }else if(temp.no==no){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if(flag){
            temp.name=name;
        }else {
            System.out.println("没有这个编号，修改失败");
        }
    }

可以自我删除，因此temp直接指向要被删除的节点，考虑删的是最后一个节点，同样有空指针异常的问题，要加一层判断。

//根据编号删除节点
    public void del(int no){
        //找到这个节点
        StudentNode2 temp=head.next;
        //是否找到该节点
        boolean flag=false;
        while (true){
            if(temp==null){
                break;
            }else if(temp.no==no){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if(flag){
            temp.pre.next=temp.next;
            if(temp.next!=null) {
                temp.next.pre = temp.pre;
            }
        }else {
            System.out.println("没有这个编号，删除失败");
        }

    }

没什么变化

//显示链表
    public void show(){
        //遍历整个链表，并打出信息
        StudentNode2 temp=head.next;
        while (true){
            if(temp==null){
                break;
            }
            System.out.println(temp);
            temp=temp.next;
        }
    }

环形链表

无头结点的环形链表。最后一个节点next指向第一个节点，形成一个闭环。如果只有一个节点，就自己指向自己。

Josephu问题

Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此
产生一个出队编号的序列。

用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

代码实现

节点设置

//小孩节点
class Boy{
    public int no;
    public Boy next;
    public Boy(int no){
        this.no=no;
    }
}

创建一个有num个节点的循环链表。
cur-辅助指针-指向要插入的前一个节点
创建时，第一个节点是不一样的，赋值，然后让他指向自己形成闭环，然后让cur指向first，附上初值。
接下来的每一个都是连上前后两条线，然后让cur移动到新的节点上。

//按照num创建环形链表
    public void add(int num){
        if(num<1){
            System.out.println("数据不对");
            return;
        }
        Boy cur=null;
        for(int i=1;i<=num;i++){
            Boy boy=new Boy(i);
            if(i==1){
                first=boy;
                first.next=first;
                cur=first;
            }else {
                cur.next = boy;
                boy.next = first;
                cur = boy;
            }
        }
    }

打印时first不变，借助辅助变量，直接打印，当cur.next==first时，cur指向最后一个元素，结束循环。

public void show(){
        Boy cur=first;
        if(first==null){
            System.out.println("空");
            return;
        }
        while (true){
            System.out.println("编号："+cur.no);
            if(cur.next==first){
                break;
            }
            cur=cur.next;
        }
    }

解决约瑟夫问题，k表示从第几个人开始，m是间隔几人，num是总人数，用来创建链表。
辅助指针cur永远指向first前一个节点，也就是一开始指向最后一个节点。
首先把cur移动到末尾
然后first和cur同时移动k-1次，因为从他开始，要让first指向那个开始的人。first一开始指向1，如果从3开始，只要移动2次。
然后开始出列，当cur=first时代表链表里只剩下一个元素，循环停止。
出列时，cur和first同时移动m-1次，实现间隔，然后将first向前一位，cur.next=first删去目标。

public void out(int k,int m,int num){
        if(k<1 | m>num | num<1 |k>num |m<1 |first==null){
            System.out.println("误");
            return;
        }
        Boy cur=first;
        //cur去末尾
        while (true){
            if(cur.next==first){
                break;
            }
            cur=cur.next;
        }
        //同时移动到k-1处
        for (int i=0;i<k-1;i++){
            first=first.next;
            cur=cur.next;
        }
        //出列
        while (true){
            if(cur==first){
                System.out.println("剩下："+cur.no);
                break;
            }
            for (int j=0;j<m-1;j++){
                first=first.next;
                cur=cur.next;
            }
            System.out.println("离开："+first.no);
            first=first.next;
            cur.next=first;
        }
    }