注：本文章基于尚硅谷相关视频及资料进行编写，代码简单，较容易理解，若有问题或者源码资料获取可以在评论区留言或者联系作者！

文章目录

• 开篇
• 一、双链表增删改初解
• • • 双向链表的增加功能
    • • • 思路：
        • 代码实现
        • 结果展示
    • 修改链表
    • • • 思路：
        • 代码实现：
        • 结果展示
    • 删除
    • • • 思路
        • 代码实现
        • 效果展示
    • 根据编号进行排序
    • • • 思路：
        • 代码实现
• 二、单向环型链表
• • • 单向环型链表介绍：
    • 构建单向环型链表
    • • • 思路：
        • 代码实现：
        • 效果演示
    • 遍历单项环型链表
    • • • 思路：
        • 代码实现
• 三、单项环型链表与约瑟夫问题
• • • 需求：
    • 编码实现：
    • 效果展示

开篇

管理单项链表的缺点的分析：

1. 单项链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找；
2. 单链表不能自我删除，需要靠辅助节点，而双向链表。则可以自我删除，所以我们前面单链表删除删除节点，总是找到temp（temp是待删除节点的前一个节点）的下一个节点来删除的；

一、双链表增删改初解

分析双向链表的遍历，添加，修改，删除的操作思路：

1. 遍历：遍历的方式和单链表一样，只是可以向前，也可以向后查找
2. 添加（默认是添加到双向链表的最后）：
   先找到双向链表的最后这个节点
   temp.next=newHeroNode
   newHeroNode.pre=temp
3. 修改：和原来的单项链表的一样
4. 删除：
   temp.pre.next=temp.next

双向链表的增加功能

思路：

找到链表的最后一个元素（该节点的下一个元素指向为空），然后令该节点的下一个节点为新增节点，新增节点的前一个节点为该节点

代码实现

//添加节点（在末尾）
    public void add(HeroNode2 heroNode) {
        //因为头节点不能动，因此我们需要一个辅助遍历temp
        HeroNode2 temp = head;
        //遍历链表，找到最后
        while (true) {
            //  找到链表的最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到，将temp后移
            temp = temp.next;
        }
        //当退出while循环的时候，temp就指向了链表的最后
        //形成一个双向链表
       temp.next=heroNode;
        heroNode.pre=temp;

    }

结果展示

修改链表

思路：

根据传入链表信息的no值来进行查询，若查询到与传入值相同的节点，则将该节点的相关属性设置为传入值的相关属性；

代码实现：

public void  update(HeroNode2 newHeroNode){
        //判断是否为空
        if (head==null){
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点，根据no编号
        //定义一个辅助变量
        HeroNode2 temp=head;
        boolean flag=false;//表示是否找到该节点
        while (true){
            if (temp==null){//表示已经遍历完链表
                break;

            }
            if (temp.no==newHeroNode.no){//表示找到该节点
                flag=true;
                break;

            }
            temp=temp.next;
        }

        //根据flag判断是否找打要修改的节点
        if (flag) {
            temp.name= newHeroNode.name;
            temp.nickname= newHeroNode.nickname;

        }else{
            //说明没有找到要修改的节点
            System.out.printf("没有找到编号%d 的节点，不能进行修改",newHeroNode.no);
        }
    }

结果展示

删除

思路

根据传入的no值进行查询节点，若找到待删除的节点，若该节点为尾节点，则将该节点的上一个的下一个节点指向该节点的下一个节点（空），若该节点不为空，则还要将该节点的下一个节点的上一个节点指向该节点的前置 节点；

代码实现

public void del(int no){
        //判断当前链表是否为空
        if (head.next==null){//空链表
            System.out.println("链表为空，无法删除");
            return;
        }
        HeroNode2 temp=head;//辅助变量（指针）
        boolean flag=false;//标志是否找到待删除节点的前一个
        while (true){
            if (temp==null){//表示已经到链表的最后节点的最后一位
                break;
            }
            if (temp.no==no){//找到待删除节点temp
                flag=true;
                break;
            }
            temp=temp.next;//temp后移，遍历
        }
        if (flag){//找到
            //删除
            temp.pre.next=temp.next;
            //这里代码有危险，如果是最后一个点，temp.next为空，下面这句话执行就会有问题
            //所以这里可以进行判断，如果是最后一个节点，就不需要执行下面的的代码
            if (temp.next!=null){//说明要删除的不是最后 一个节点
                temp.next.pre=temp.pre;
            }


        }else{
            System.out.printf("没有找到要删除的%d 的节点，不能进行修改",no);
        }
    }

效果展示

根据编号进行排序

思路：

可以在之前的添加方法上做一个扩展，首先和之前一样进行判断，如果当前在链表的最后，则直接进行插入操作，然后判断当前节点的下一个元素的编号是否小于新增节点编号，若大于当前新增节点，则也直接进行一个新增操作，另外的，如果当前元素的下一个节点的编号等于当前新增节点编号，表明该新增节点已经存在，则输出无法插入，最后，最重要的是插入操作，之前的插入都是在链表的最后进行插入操作，而现在可能出现在链表中间进行数据的插入，所以要对插入操作做一个变化，具体如入菜代码所示

代码实现

    //根据编号进行添加排序
    public void addByOrder(HeroNode2 heroNode2){
        //因为头节点不能动，因此我们需要一个辅助遍历temp
        HeroNode2 temp = head;
        //遍历链表，找到最后
        boolean flag=false;
        while (true) {
            //  找到链表的最后
            if (temp.next == null) {
                break;//直接添加在链表的最后
            }
            if (temp.next.no>heroNode2.no){
                break;
            }else if (temp.next.no== heroNode2.no){//该编号节点已经存在
                flag=true;
                break;

            }
            //如果没有找到，将temp后移
            temp = temp.next;
        }
        if (flag){
            System.out.printf("准备插入的节点编号 %d已经存在了，不能加入n", heroNode2.no);

        }else {
            //当退出while循环的时候，temp就指向了链表的最后
            //形成一个双向链表
            heroNode2.next=temp.next;//将新增链表的下一个元素指向当前节点的下一个节点
            temp.next=heroNode2;
            heroNode2.pre=temp;

        }


    }

二、单向环型链表

约瑟夫问题：

单向环型链表介绍：

链表的尾节点指向链表的头节点，单向链表，表明链表不可回查

构建单向环型链表

思路：

1. 先创建第一个节点，让frist指向该节点，并形成环型
2. 后面当我们每创建一个新的节点，就把该节点，加入到已有的环型链表中即可

代码实现：

//创建一个first节点，当前没有 编号
    private Boy first = new Boy(-1);

    //添加小孩节点，构成一个环型的链表
    public void addBoy(int nums) {//传入要添加的节点个数
        //对nums的值作一个数据校验
        if (nums < 1) {//表明至少应该有一个
            System.out.println("nums的值不正确！");
            return;
        }

        Boy curBoy = null;//辅助指针，帮助构建环型链表
        //使用for循环创建我们的环型链表
        for (int i = 1; i < nums; i++) {
            //根据编号创建小孩节点
            Boy boy = new Boy(i);
            //如果是第一个小孩节点
            if (i == 1) {
                first = boy;//将第一个之前预定的节点设为boy
                first.setNext(first);//将boy的下一个节点指向它自己
                curBoy = first;//让curBoy指向第一个小孩

            } else {//如果不是第一个节点
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;//让curBoy往下移动一位
            }

        }
    }

效果演示

遍历单项环型链表

思路：

1. 先让一个辅助指针（变量）curBoy，指向first节点
2. 然后通过一个while循环遍历该环型链表curBoy.next==first结束

代码实现

//遍历当前环型链表
    public void showBoy() {
        //判断链表是否为空
        if (first == null) {
            System.out.println("没有任何小孩!");
            return;

        }
        //因为first不能动，所以可以使用一个辅助指针完成遍历
        Boy curBoy = first;
        while (true) {
            System.out.printf("小孩的编号%d n",curBoy.getNo());
            if (curBoy.getNext()== first){//说明已经遍历完毕
                break;

            }
            curBoy=curBoy.getNext();//curBoy后移
        }
    }

三、单项环型链表与约瑟夫问题

需求：

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

1. 需要创建一个辅助指针（变量），helper，事先要指向环型链表的最后的这个节点；
2. 小孩报数前，先让first和helper移动k-1次到k小孩这里来
3. 当小孩报数的时候，让first和helper指针同时移动m-1次（因为自身也需要进行报数）；
4. 这时就可以将first指向小孩节点出圈first=first.next; helper.next=first; 原来first指向的节点就没有任何引用，就会被回收
   

编码实现：

//根据用户的输入，计算出小孩出圈的顺序

    /**
     * @param starNO   表示从第几个小孩开始数数
     * @param countNum 表示数几下
     * @param nums     表示最初有多少个小孩在圈中
     */
    public void countBoy(int starNO, int countNum, int nums) {
        //先对数据进行校验
        if (first == null || starNO < 1 || starNO > nums) {
            System.out.println("您的参数输入有误，请重新输入");
            return;
        }
        //创建辅助指针，帮助小孩完成出圈
        Boy helper = first;

        while (true) {//将helper指向最后一个节点
            if (helper.getNext() == first) {//说明helper指向最后的一个节点
                break;

            }
            helper=helper.getNext();

        }

        //小孩报数前，先让first和helper移动k-1次
        for (int j = 0; j < starNO-1; j++) {
            first=first.getNext();
            helper=helper.getNext();

        }

        //当小孩报数时，让first和helper指针同时移动m-1次,然后出圈
        //这里是一个循环的操作，知道圈中只有一个节点
        while (true){
          if (helper==first){//说明圈中只有一个节点
              break;
          }

          //让first和helper同时移动count-1次，出圈
            for (int j = 0; j < countNum-1; j++) {
                first=first.getNext();
                helper=helper.getNext();

            }
            //这时first指向的节点，就是要出圈的小孩节点
            System.out.printf("小孩%d出圈n",first.getNo());
            //这时将first指向的小孩节点出圈
            first=first.getNext();
            helper.setNext(first);

        }
        System.out.printf("最后留在圈中的小孩的编号%dn",first.getNo());



    }


}

效果展示

如果感觉内容写的还不错的话，一键三连不迷路！！！！
后面将会更新更多学习内容，一起学习吧！！！！！！

最后

以上就是快乐黄豆为你收集整理的【大厂必会的数据结构和算法】03- 双向链表及约瑟夫问题开篇一、双链表增删改初解二、单向环型链表三、单项环型链表与约瑟夫问题的全部内容，希望文章能够帮你解决【大厂必会的数据结构和算法】03- 双向链表及约瑟夫问题开篇一、双链表增删改初解二、单向环型链表三、单项环型链表与约瑟夫问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。