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

文章目录

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

开篇

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

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("最后留在圈中的小孩的编号%d\n",first.getNo());    }}

效果展示

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

ChinaFonts