双向链表和环形链表（单向和双向）约瑟夫环实例

双向链表

数组优缺点：根据下标直接查找和修改，增删需要移动后续数据，效率低。

单向链表的缺点：增删快速，查找需要从头遍历，效率低。

双线链表可以向前或向后查找。

单向链表查找的方向只能是一个方向（双向链表可以向前向后查找），且不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除节点时，总是找到temp的下一个节点来删除的（就是指temp.next.data == data，因为要对该节点的前一个节点及后一个节点操作。)

双向链表节点包含数据域data、前驱指针域prev、后继指针域next。

分析双向链表可以实现的功能：

（1）遍历：和单链表一样，只是可以向前向后查找。

（2）添加：举例添加node到链表的最后，rear.next = node;node.prev = rear;rear = node;

（3）修改：和单链表一样

（4）删除：举例删除node，node.prev.next = node.next;node.next.prev = node.prev;

代码实现：

// 定义双向链表
class DoublieLinkedList{
    // 初始化一个头结点
    private LinkedNode head = new LinkedNode(0,"","");

    // 返回头结点
    private LinkedNode getHead(){
        return head;
    }

    // 遍历双向链表
    public void show(){
        // 按顺序遍历
        // 先判断链表是否为空
        if(head.next == null) System.out.println("链表为空");
        // 因为头结点不能动，需要一个辅助变量来遍历
        LinkedNode temp = head.next;
        while(temp != null){ // 链表不为空
            System.out.println(temp.toString()); // 输出节点信息
            temp = temp.next; // 指针后移
        }
    }

    // 尾插法添加节点到单向链表
    public void addRear(LinkedNode node){
        // 遍历找到最后，找到尾结点
        LinkedNode rear = head;
        while(head != null){
            rear = head;
            head = head.next;
        }
        rear.next = node;
        node.prev = rear;
    }

    // 修改节点信息，根据编号修改。
    /*
    说明根据node的id来修改
     */
    public void update(LinkedNode node){
        // 判断链表是否为空
        if(head.next == null) System.out.println("链表为空");
        // 找到需要修改的节点
        // 定义一个辅助变量
        LinkedNode temp = head;
        boolean flag = false;
        while(true){
            if(temp.next == null) {// 链表为空，或遍历到最后一个节点了
                break;
            }
            if(temp.id == node.id){ // 找到节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.name = node.name;
            temp.nickName = node.nickName;
        }else System.out.println("没有找到该编号英雄！");
    }

    // 删除节点
    public void deleteNode(LinkedNode node){
        if(head ==  null) System.out.println("链表为空！");
        LinkedNode temp = head; // 遍历指针
        boolean flag = false;
        while(true) {
            if (temp == null) { // 链表为空或遍历到最后了
                break;
            }
            if (temp.id == node.id) { // 找到该节点的前驱节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.prev.next = temp.next;
            temp.next.prev = temp.prev;
        }else{ // 遍历到最后也没找到
            System.out.println("链表中不存在该节点");
        }
    }

}
// 定义LinkedNode节点，定义LinkedNode节点
class LinkedNode{
    public int id; // 编号
    public String name; // 姓名
    public String nickName; // 英雄名
    // 因为一个节点就是这个Node类的实例对象，那么它存储的就是该对象的地址值。
    // 而指针域的作用就是指向下一个节点的地址，所以类型就是Node
    public LinkedNode next; // 后继指针域，成员变量默认初始化（编译期初始化放在方法区），null
    public LinkedNode prev; // 前驱指针域，null

    // 构造器
    public LinkedNode(int id, String name, String nickName) { // 指针域已置空，不用再动
        this.id = id;
        this.name = name;
        this.nickName = nickName;
    }

    // 显示方便，重写toString方法
    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                // ", next=" + next +
                '}';
    }
}

单向环形链表

应用场景：约瑟夫问题---在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

简单理解：设编号为1,2,...,n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，直到所有人出列为止，由此产生一个出队编号的序列。

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

创建单向环形链表思路：

1.先创建第一个节点，让first指向该节点，并形成环形。

2.后面当我们每创建一个新的节点，就把该节点加入到已有的环形链表中即可。

遍历环形链表：

辅助指针指向first。

public class SingleCircularLinkedList {
    // 初始化一个单向的环形链表
    public Node2 first = new Node2(0);

    // 添加元素到链表里
    public void add(int nums){
        // 数据校验
        if(nums < 1) System.out.println("节点数异常！");
        Node2 rear = new Node2(0); // 辅助尾指针，便于尾插数据
        for (int i = 1; i <= nums; i++) {
            Node2 node = new Node2(i); // 按编号加入小孩
            // 第一个节点特殊考虑
            if(i == 1){
                first = node; // 无头结点，第一个点就是first
                first.next = first; // 形成环状
                rear = first;
            }else{
                rear.next = node;
                node.next = first;
                rear = node;
            }
        }
    }

    // 遍历当前环形链表
    public void show(){
        if(first == null) System.out.println("链表为空！");
        Node2 temp = first; // 辅助指针
       while(true){
           System.out.println(temp.id); // 先输出
           if(temp.next == first) break; // 再判断到最后一个没有，这样能保证最后一个也输出了
           temp = temp.next;
       }
    }

}
class Node2{
    public int id; // 编号
    public Node2 next; // 指向下一个节点，默认初始化null

    // 构造器
    public Node2(int id) {
        this.id = id;
    }

    // 显示方便，重写toString方法

    @Override
    public String toString() {
        return "Node2{" +
                "id=" + id +
                ", next=" + next +
                '}';
    }
}

根据用户的输入，生成一个小孩出圈的顺序：

1.需要创建一个辅助指针prev，初始化遍历指向环形列表的最后这个节点。（即每次出圈节点的前一个节点）

2.根据从第几个数开始，让out和prev指针一起移动到指定开始节点位置。

3.报数时，让prev和out指针同时移动m-1（自己也要报，所以-1）次。

3.这时就可以让out指向的节点出圈，让prev连上后一个点。继续转，直到prev == out只剩一个节点，就停止。

注意当一个节点没有任何引用时就会被回收。

public class SingleCircularLinkedList {
    // 初始化一个单向的环形链表
    public Node2 first = new Node2(0);

    // 添加元素到链表里
    public void add(int nums){
        // 数据校验
        if(nums < 1) System.out.println("节点数异常！");
        Node2 rear = new Node2(0); // 辅助尾指针，便于尾插数据
        for (int i = 1; i <= nums; i++) {
            Node2 node = new Node2(i); // 按编号加入小孩
            // 第一个节点特殊考虑
            if(i == 1){
                first = node; // 无头结点，第一个点就是first
                first.next = first; // 形成环状
                rear = first;
            }else{
                rear.next = node;
                node.next = first;
                rear = node;
            }
        }
    }

    // 根据用户的输入，计算出出圈顺序
    public void outLine(int startId,int countNum,int nums){
        // startId从谁开始数，countNum数几下，nums最初有多少人
        // 先对数据做校验
        if(first == null || startId < 1 || countNum > nums){
            // 圈里有人/至少从1数，最多数人数下
            System.out.println("参数输入有误，请重新输入！");
            return;  // 无返回值return直接跳出这个方法
        }
        // 报数前准备，让prev指针和out指针一起移动，prev少移动一次
        // 类似于快慢指针
        Node2 out = first;
        Node2 prev = first;

        while(prev.next != first){ // 初始化指向最后节点
            prev = prev.next;
        }
        // 然后一起移动到起点位置
        for (int i = 1; i < startId; i++) {
            prev = prev.next;
            out = out.next;
        }

        System.out.println("prev:" + prev.id);
        System.out.println("out:" + out.id);
        // 循环操作，直到只剩一个节点
        while(true) {
            if(prev == out){ // 圈中只有一个节点
                break;
            }
            // 当报数开始，两个指针一起移动countNum - 1次
            for (int i = 1; i < countNum; i++) {
                prev = prev.next;
                out = out.next;
            }
            System.out.println("出圈的是：" + out.id); // 格式化
            // out指针出圈，去引用
            prev.next = out.next;
            out = out.next;
        }
        System.out.println("最后留下的是:" + out.id);
    }

    // 遍历当前环形链表
    public void show(){
        if(first == null) System.out.println("链表为空！");
        Node2 temp = first; // 辅助指针
       while(true){
           System.out.println(temp.id); // 先输出
           if(temp.next == first) break; // 再判断到最后一个没有，这样能保证最后一个也输出了
           temp = temp.next;
       }
    }

}
class Node2{
    public int id; // 编号
    public Node2 next; // 指向下一个节点，默认初始化null

    // 构造器
    public Node2(int id) {
        this.id = id;
    }

}

public class Josepfu {
    public static void main(String[] args) {
        SingleCircularLinkedList circle = new SingleCircularLinkedList();
        circle.add(18);
        // circle.s1how();
        System.out.println("开始您设计的约瑟夫环！");
        System.out.println("请输入总共人数：");
        Scanner sc = new Scanner(System.in);
        int nums = sc.nextInt();
        circle.add(nums);
        System.out.println("请输入每次报几个数：");
        int countNum = sc.nextInt();
        System.out.println("请输入从第几个数开始：");
        int startId = sc.nextInt();
        System.out.println("输入完毕！请看结果：");
        circle.outLine(startId,countNum,nums);
    }
}