• 【数据结构】—— 单链表的增删改查

    ❤️一名热爱Java的大一学生，希望与各位大佬共同学习进步❤️

    🧑个人主页：@周小末天天开心

    各位大佬的点赞👍 收藏⭐ 关注✅，是本人学习的最大动力

    感谢！

    📕该篇文章收录专栏—数据结构

    目录

    方法重写

    重写条件

    重写好处

    重写演示

    单链表

    介绍

    单链表的增删改查

    创建HeroNode类，用来存放信息

    创建SingleLinkedList类，用来存放方法

    按顺序插入到链表最后

    按照编号的顺序添加

    编写显示该链表的方法

    修改节点信息

    删除节点

    编写SingleLinkedListDemo类进行演示

    获取单链表中的节点个数

    将单链表反转

    查找单链表中倒数第k个节点

    测试单链表的增删改查，查看输出结果

    方法重写

            在学习之前先要了解什么是方法重写，简单来说，方法重写就是子类可继承父类中的方法，而不需要重新编写相同的方法，但有时子类并不想原封不动地继承父类的方法，而是想作一定的修改，这就需要采用方法的重写。方法重写又称方法覆盖。

    重写条件

    （1）必须是继承关系

    （2）子类中的方法要和父类一样

    （3）重写是发生在两个类中

    重写好处

            子类扩展了父类中的方法，让父类中的功能变得更加强大。

    注意：如果子类想调用父类方法，直接在重写方法中使用 super 关键字重写父类中的方法，且方法的修饰符必须是公共的，私有方法不可以重写。

    重写演示

    编写一个父类Animal

    1. public class Animal { //创建一个父类 Animal
    2.     public String name;//属性
    3.  
    4.     public String getName() {
    5.         return name;
    6.     }
    7.  
    8.     public void setName(String name) {
    9.         this.name = name;
    10.     }
    11.     public void eat() {
    12.         System.out.println("喜欢……");
    13.     }
    14. }

    再编写一个子类Dog，并继承父类

    1. public class Dog extends Animal{//子类 Dog 继承父类 Animal
    2.  
    3.     @Override //方法重写的标记，看到此标记就代表方法重写现象
    4.     public void eat() {
    5.         //方法重写现象，在该类中eat方法和父类Animal中的eat方法的名称一样
    6.         super.eat();//调用父类的 eat 方法
    7.         System.out.println("吃骨头……");
    8.     }
    9. }

     编写Demo类进行演示

    1. public class Demo {
    2.     public static void main(String[] args) {
    3.         Dog dog = new Dog();
    4.         dog.setName("哈士奇……");
    5.         System.out.println(dog.getName());
    6.         dog.eat();
    7.     }
    8. }

    查看输出结果：

    单链表

    介绍

    链表是一个有序的列表，但是它在内存中是存储如下的：

    头指针
    head150
    地址data域next域
    110a2180
    120
    130a4170
    140a6NULL
    150a1110
    160
    170a5140
    180a3130

    （1）链表是以节点的方式来存储的，是链式存储

    （2）每个节点包含data域，next域：指向下一个节点

    （3）如上图：发现链表的各个节点不一定是连续存储的

    （4）链表分带头节点的链表和没有头节点的链表，根据实际需求来确定单链表（带头节点）

    单链表的增删改查

    创建HeroNode类，用来存放信息

    1. //定义HeroNode，每个HeroNode 对象就是一个节点
    2. class HeroNode {
    3.     public int no;
    4.     public String name;
    5.     public String nickname;//昵称
    6.     public HeroNode next;//指向下一个节点
    7.  
    8.     //构造器
    9.     public HeroNode(int no, String name, String nickname) {
    10.         this.no = no;
    11.         this.name = name;
    12.         this.nickname = nickname;
    13.     }
    14.  
    15.     //为了显示方法，这里重写 toString() 方法
    16.     @Override
    17.     public String toString() {
    18.         return "HeroNode{" +
    19.                 "no=" + no +
    20.                 ", name='" + name + '\'' +
    21.                 ", nickname='" + nickname + '\'' + "}";
    22.     }
    23. }

    创建SingleLinkedList类，用来存放方法

    按顺序插入到链表最后

    （1）先创建一个 head头节点，作用就是表示单链表的头

    （2）后面每添加一个节点，就直接加入到链表最后，也可以理解为每有一个新节点，我们就把最后一个节点的 next域 指向新节点

    链表为空的条件：head.next == null（表示头节点的下一位为空）

    链表最后的条件：temp.next == null （temp为辅助变量）

    1. //先初始化一个头节点，头节点不要动，如果改动头节点那么就不好去找到链表最顶端的节点了
    2.     private HeroNode head = new HeroNode(0 , "" , "");
    3.     //头节点不存放具体的数据
    4.  
    5.     public HeroNode getHead() {//返回头节点
    6.         return head;
    7.     }
    8.  
    9.     //思路：
    10.     //1.找到当前链表的最后一个节点
    11.     //2.将最后这个节点的next域指向新的节点
    12.     public void add(HeroNode heroNode) {
    13.         //因为head头节点不能动，所以需要一个辅助变量temp
    14.         HeroNode temp = head;//将temp指向head
    15.         //遍历链表，找到链表最后
    16.         while(true) {
    17.             //当temp的域等于空时，说明temp找到了链表最后了
    18.             if(temp.next == null) {//找到最后了，结束程序
    19.                 break;
    20.             }
    21.             //如果没有找到最后，就将temp 后移指向下一个数据
    22.             temp = temp.next;
    23.         }
    24.         //当退出了 while 循环时，那么 temp 就指向了链表的最后
    25.         temp.next = heroNode; //将最后这个节点的next域指向新的节点
    26.     }

    按照编号的顺序添加

    （1）首先找到新添加节点的位置，是通过辅助变量找到的

    （2）添加方法：

    1）新的节点.next = temp.next

    2）temp.next = 新的节点

    1.     public void addByOrder(HeroNode heroNode) {
    2.         //因为头节点不能动，因此需要通过一个辅助指针(变量)来帮助找到添加的位置
    3.         //因为是单链表，所以辅助变量temp应该是位于添加位置的前一个节点，否则无法插入
    4.         HeroNode temp = head;
    5.         boolean flag = false;//flag标志添加的编号是否存在，默认为false
    6.         while(true) {
    7.             if(temp.next == null) {//说明temp已经到了链表最后
    8.                 break;
    9.             }
    10.             if(temp.next.no > heroNode.no) {//位置找到，就在temp的后面插入
    11.                 //如果temp.next.no > heroNode.no 
    12.                 //说明 heroNode 就应该插入到 temp 和 temp.next 之间
    13.                 break;
    14.             }
    15.             if(temp.next.no == heroNode.no) {
    16.                 //说明希望添加的heroNode的编号以及存在
    17.                 flag = true;
    18.                 break;
    19.             }
    20.             temp = temp.next;//如果三个条件都不符合就将 temp 后移，继续遍历
    21.         }
    22.         //判断flag的值
    23.         if(flag) {
    24.             //如果 flag == true。说明编号已存在，所以无法插入
    25.             System.out.printf("准备插入的编号%d已经存在，无法插入",heroNode.no);
    26.         } else {
    27.             //否则可以插入到链表中，temp 的后面
    28.             heroNode.next = temp.next;
    29.             temp.next = heroNode;
    30.         }
    31. }

    编写显示该链表的方法

    1. //显示链表[遍历]
    2.     public void list() {
    3.         //先判断链表是否为空
    4.         if(head.next == null) { //说明了链表为空
    5.             System.out.println("链表为空");
    6.             return;
    7.         }
    8.         //如果链表不为空，且头节点不能动，因此需要一个辅助变量来遍历
    9.         HeroNode temp = head.next;
    10.         //因为已经判断了链表不为空，说明链表至少有一个数据，所以是 head.next(头节点指向的下一个数据)
    11.         while(true) {
    12.             //判断是否已经到了链表最后
    13.             if(temp == null) {
    14.                 //遍历是到了链表最后，所以退出循环
    15.                 break;
    16.             }
    17.             //如果不为空，则输出该节点的信息
    18.             System.out.println(temp);//已经重写了 toString()
    19.             //输出后需要将temp后移一位，因为输出该信息后需要让temp指向下一位，输出下一位的信息
    20.             temp = temp.next;//不后移就是一个死循环
    21.         }
    22.     }

    修改节点信息

    1. //修改节点的信息，根据no编号来修改，即no编号不能改
    2.     //根据newHeroNew 的 no 来进行修改即可
    3.     public void update(HeroNode newHeroNew) {
    4.         //判断是否为空
    5.         if(head.next == null) {
    6.             System.out.println("该链表为空");
    7.             return;
    8.         }
    9.         //找到需要更改的节点，根据no编号
    10.         //定义一个辅助变量
    11.         HeroNode temp = head.next;//temp 赋的值为头节点的下一个节点
    12.         boolean flag = false;//表示是否找到了该节点
    13.         while(true) {
    14.             if(temp == null) {
    15.                 //说明链表已经遍历完成，因为temp 指向的是下一个节点(需要注意，和上面不同)
    16.                 break;
    17.             }
    18.             if(temp.no > newHeroNew.no) {
    19.                 //因为temp 指向的是下一个节点。
    20.                 //所以就不需要 temp.next.no 了(需要注意，和上面不同)
    21.                 //位置找到，就在temp后面进行添加
    22.                 break;
    23.             }
    24.             if(temp.no == newHeroNew.no) {
    25.                 //因为temp 指向的是下一个节点。所以就不需要 temp.next.no 了(需要注意，和上面不同)
    26.                 //说明希望添加的编号已经存在
    27.                 flag = true;
    28.                 break;
    29.             }
    30.             temp = temp.next;//如果循环没有结束就一直进行遍历
    31.         }
    32.         //根据 flag 来进行判断是否找到了要修改的节点
    33.         if(flag) {//如果flag 为 true 说明就找到了要修改的节点
    34.             temp.name = newHeroNew.name;
    35.             temp.nickname = newHeroNew.nickname;
    36.             //注意：no 编号不可以修改
    37.         } else { //说明没有找到要修改的节点
    38.             System.out.printf("没有找到编号等于%d的节点\n",newHeroNew.no);
    39.         }
    40.     }

    删除节点

    （1）先找到需要删除的这个节点的前一个节点 temp

    （2）temp.next = temp.next.next

    （3）被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收

    1.     /*
    2.     思路
    3.     1.head 节点不能动，因此我们需要一个 temp 辅助接点找到待删除的前一个节点
    4.     2.说明我们在比较时，是 temp.next.no 和需要删除的节点的 no 比较
    5.      */
    6.     public void delete(int no) {
    7.         HeroNode temp = head;
    8.         boolean flag = false;//标志是否找到了待删除的节点
    9.         while(true) {
    10.             if(temp.next == null) {//已经到链表的最后了
    11.                 break;
    12.             }
    13.             if(temp.next.no == no) {
    14.                 //找到了待删除节点的前一个节点temp
    15.                 flag = true;
    16.                 break;
    17.             }
    18.             temp = temp.next;//让 temp 后移，实现遍历
    19.         }
    20.         //判断 flag
    21.         if(flag) {
    22.             //如果flag位真，找到了要删除的节点，可以删除
    23.             temp.next = temp.next.next;//将temp的下下个节点赋给下个节点(删除temp的下个节点)
    24.         } else {
    25.             System.out.printf("要删除的%d节点不存在\n",no);
    26.         }
    27.     }

    编写SingleLinkedListDemo类进行演示

    获取单链表中的节点个数

    1. //获取单链表中节点的个数(如果是带头节点的链表。需要不统计头节点)
    2.  
    3.     /**
    4.      * @param head 链表的头节点
    5.      * @return 返回的就是有效节点的个数
    6.      */
    7.     public static int getlength(HeroNode head) {
    8.         if (head.next == null) {
    9.             //说明该链表为空链表
    10.             return 0;
    11.         }
    12.         int length = 0;
    13.         //定义一个辅助变量，没有统计头节点
    14.         HeroNode cur = head.next;
    15.         while (cur != null) {
    16.             length++;
    17.             cur = cur.next;//后移 cur 进行遍历
    18.         }
    19.         return length;
    20.     }

    将单链表反转

    （1）先定义一个节点 reverseHead = new HeroNode();

    （2）从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead的最前端

    （3）原来的链表的 head.next = reverseHead.next

    1. //将单链表反转
    2.     public static void reverseList(HeroNode head) {
    3.         //如果当前链表为空，或者只有一个节点，则无需反转，直接返回
    4.         if(head.next == null || head.next.next == null) {
    5.             return ;
    6.         }
    7.         //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
    8.         HeroNode cur = head.next;
    9.         HeroNode next = null;//指向当前节点[cur]的下一个节点
    10.         HeroNode reverseHead = new HeroNode(0, " ", " ");
    11.         //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
    12.         while(cur != null) {
    13.             next = cur.next;//先暂时保存，当前节点的下一个节点，因为后面需要使用
    14.             cur.next = reverseHead.next;//将 cur 的下一个节点指向新的链表的最前端
    15.             reverseHead.next = cur;//将 cur 连接到新的链表上
    16.             cur = next;//让 cur 后移
    17.         }
    18.         //将 head.next 指向 reverseHead.next ，实现单链表的反转
    19.         head.next = reverseHead.next;
    20.     }

    查找单链表中倒数第k个节点

    1. //查找单链表中倒数第k个节点
    2.     /*
    3.     思路
    4.     1.编写一个方法，接收 head 节点，同时接收一个 index
    5.     2.index 表示是倒数第 index 个节点
    6.     3.先将链表从头到尾进行遍历，得到的链表的总长度 getlength
    7.     4.得到 size 后，从链表的第一个节点开始遍历(size - index)个，
    8.     5.如果找到了，则返回该节点，否则返回 null
    9.      */
    10.     public static HeroNode findLastIndexNode(HeroNode head, int index) {
    11.         //如果该链表为空，则返回 null
    12.         if(head.next == null) {
    13.             return null;//返回空
    14.         }
    15.         //第一个遍历得到链表的长度
    16.         int size = getlength(head);
    17.         //第二个遍历得到 size - index 的位置，就是我们倒数第k个节点
    18.         //首先校验 index 的长度
    19.         if(index <= 0 || index > size) {//不可以小于等于零以及不能大于 size
    20.             return null;
    21.         }
    22.         //定义辅助变量然后进行赋值
    23.         HeroNode cur = head.next;
    24.         //for 循环定位到倒数的 index
    25.         for(int i = 0; i < size - index; i++) {
    26.             cur = cur.next;//后移一位遍历
    27.         }
    28.         return cur;
    29.     }

    测试单链表的增删改查，查看输出结果

    1. public class SingleLinkedListDemo {
    2.     public static void main(String[] args) {
    3.         //进行测试
    4.         //先创建节点
    5.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    6.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    7.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    8.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
    9.  
    10.         //创建要给链表
    11.         SingleLinkedList singleLinkedList = new SingleLinkedList();
    12.  
    13.         //直接加入在链表尾部
    14.         singleLinkedList.add(hero1);
    15.         singleLinkedList.add(hero2);
    16.         singleLinkedList.add(hero3);
    17.         singleLinkedList.add(hero4);
    18.  
    19. //        按顺序插入链表
    20. //        singleLinkedList.addByOrder(hero1);
    21. //        singleLinkedList.addByOrder(hero4);
    22. //        singleLinkedList.addByOrder(hero3);
    23. //        singleLinkedList.addByOrder(hero2);
    24.  
    25.         //显示
    26.         singleLinkedList.list();
    27.  
    28. //        测试要修改节点的代码
    29. //        System.out.println("=====修改后的链表为=====");
    30. //        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~~");
    31. //        singleLinkedList.update(newHeroNode);
    32. //
    33. //        //显示
    34. //        singleLinkedList.list();
    35.  
    36.         //删除一个节点
    37. //        System.out.println("=====删除后的链表为=====");
    38. //        singleLinkedList.delete(1);
    39. //        singleLinkedList.delete(4);
    40. //
    41. //        //显示
    42. //        singleLinkedList.list();
    43.  
    44. //        //显示该链表中有效节点的个数
    45. //        System.out.println("=====该链表中有效节点的个数是=====");
    46. //        System.out.println(getlength(singleLinkedList.getHead()));
    47. //
    48. //        //测试一下看看是否得到了倒数第k个节点
    49. //        HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 2);
    50. //            System.out.println("res= " + res);
    51.  
    52. //        //测试单链表的反转功能
    53. //        System.out.println("=====原来链表的情况=====");
    54. //        singleLinkedList.list();
    55. //        System.out.println("=====反转后的链表情况=====");
    56. //        reverseList(singleLinkedList.getHead());
    57. //        singleLinkedList.list();
    58.     }
    59. }

  • 相关阅读:
    自用 K8S 资源对象清单 YAML 配置模板手册-1
    学习笔记-算法-9-二叉树-1
    Aptos 中文文档
    myssql基于Spring Boot的宠物猫店管理系统的设计与实现毕业设计源码140909
    iOS打基础之Block二三事
    odoo javascript参考（六）
    R语言实现：统计学及计量专业中的多种平均值计算方式
    电子科技大学820笔记【2011年】
    嵌入式 Linux 入门（十、Linux 下的 C 编程）
    【C++】STL——反向迭代器的模拟实现：迭代器适配器
  • 原文地址：https://blog.csdn.net/weixin_71646897/article/details/127956528