数据结构，单链表讲解，并使用Java代码实现单链表增删改查【尾部添加，中间插入、修改节点、删除节点、展示链表】

2022-09-09 08:36:28

文章目录

单链表

什么是单链表，链式存储结构详解

链表，别名链式存储结构或单链表，用于存储逻辑关系为 “一对一” 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。

例如，使用链表存储 {1,2,3}，数据的物理存储状态如图 1 所示：
在这里插入图片描述
我们看到，图 1 根本无法体现出各数据之间的逻辑关系。对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。如图 2 所示：
在这里插入图片描述
像图 2 这样，数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。

链表的节点

链表中每个数据的存储都由以下两部分组成：

  1. 数据元素本身，其所在的区域称为数据域；
  2. 指向直接后继元素的指针，所在的区域称为指针域；

即链表中存储各数据元素的结构如图 3 所示：
在这里插入图片描述
图 3 所示的结构在链表中称为节点。也就是说，链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中，如图 4 所示：
在这里插入图片描述

头节点，头指针和首元节点

其实，图 4 所示的链表结构并不完整。一个完整的链表需要由以下几部分构成：

  1. 头指针（含义同下问的辅助指针）：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
  2. 节点：链表中的节点又细分为头节点、首元节点和其他节点：
    头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
    首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
    其他节点：链表中其他的节点；

因此，一个存储 {1,2,3} 的完整链表结构如图 5 所示：
在这里插入图片描述
注意：链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。

单链表的实现

使用带 head 头的单向链表实现：王者荣耀英雄排行榜管理完成对英雄人物的增删改查操作。

1.尾部添加新节点

思路分析

在这里插入图片描述

  1. 首先要定义一个节点类，每个节点存放俩部分内容，数据域和指针域。
  2. 节点的数据域部分存放人物编号、姓名、外号。节点的指针域指向下一个节点。
  3. 编写构造器初始化数据域内容，为了显示方便，需要重写toString方法。
  4. 定义单向链表类，初始化一个头节点，整型数据初始化为0，字符类型数据初始化为空字符。注意：头节点不存放数据，作用就是表示单链表的头。
  5. 定义节点添加的方法，思路：(1)找到当前链表的最后节点，注意先判断链表是否为空。(2)将最后的节点next指向新节点，完成尾部添加。
  6. 定义显示链表方法，通过遍历输出节点的数据域。

代码实现

publicclassSingleLinkedListDemo{publicstaticvoidmain(String[] args){//代码测试//先创建几个节点HeroNode hero1=newHeroNode(1,"铠","绛天战甲");HeroNode hero2=newHeroNode(2,"瑶妹","遇见神鹿");HeroNode hero3=newHeroNode(3,"吕布","天魔缭乱");HeroNode hero4=newHeroNode(4,"貂蝉","仲夏夜之梦");//创建一个链表SingleLinkedList singleLinkedList=newSingleLinkedList();//加入
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);//显示
        singleLinkedList.list();}}//定义SingleLinkedList，管理英雄classSingleLinkedList{//先初始化一个头节点，头节点不要动privateHeroNode head=newHeroNode(0,"","");//添加节点到单向链表//思路：当不考虑编号顺序时//1. 找到当前链表最后的节点//2. 将最后的节点next指向新的节点publicvoidadd(HeroNode heroNode){//因为head节点不能动，因此我们需要一个辅助变量 tempHeroNode temp= head;//遍历链表，找到最后while(true){//当找到链表的最后时，temp.next==nullif(temp.next==null){break;}
            temp= temp.next;//如果没有找到最后，将temp后移}//当推出while循环时，temp就指向了链表的最后，然后让它指向新的节点。
        temp.next= heroNode;}//显示链表【遍历】publicvoidlist(){//判断是否为空if(head.next==null){System.out.println("链表为空！！！");return;}//因为头节点不可以动，因此需要一个辅助变量来遍历HeroNode temp= head.next;while(true){//判断指针是否指向最后if(temp==null){break;}//输出节点信息System.out.println(temp);//将temp后移，一定后移！！！
            temp= temp.next;}}}//定义一个HeroNode，每个HeroNode对象就是一个节点classHeroNode{publicint no;publicString name;publicString nickname;publicHeroNode next;//指向下一个节点// 构造器publicHeroNode(intNo,StringName,StringNickname){this.no=No;this.name=Name;this.nickname=Nickname;}// 为了显示方便，重写 toString 方法@OverridepublicStringtoString(){return"HeroNode{"+"no="+ no+", name='"+ name+'\''+", nickname='"+ nickname+'\''+'}';}}

运行结果：

HeroNode{no=1, name='铠', nickname='绛天战甲'}HeroNode{no=2, name='瑶妹', nickname='遇见神鹿'}HeroNode{no=3, name='吕布', nickname='天魔缭乱'}HeroNode{no=4, name='貂蝉', nickname='仲夏夜之梦'}Process finishedwithexit code0

注意事项

  • 1.由于头节点不能动，所以在遍历的时候需要一个辅助变量，或者说是辅助指针，进行指针移动。
  • 2.注意代码中俩次遍历链表时辅助指针的初始化区别。第一次遍历是在添加节点时找到链表最后节点，辅助指针是直接将head节点指针赋给它，是因为在最后节点的指针指向新节点之前，必须将先将该指针指向空；第二次遍历是在显示链表各个节点数据域的时候，而这次辅助指针的初始化和第一次不一样，是直接将头节点的下一个节点赋值给辅助指针，原因是头节点无数据域，所以显示数据需从含有第一个数据域的节点开始。
  • 3.由于在代码中想要将节点的数据域输出，所以在节点类当要重写内置的toString方法。

2.按照编号插入新节点

思路分析

在这里插入图片描述

  1. 首先要定义一个节点类，每个节点存放俩部分内容，数据域和指针域。
  2. 节点的数据域部分存放人物编号、姓名、外号。节点的指针域指向下一个节点。
  3. 编写构造器初始化数据域内容，为了显示方便，需要重写toString方法。
  4. 定义单向链表类，初始化一个头节点，整型数据初始化为0，字符类型数据初始化为空字符。注意：头节点不存放数据，作用就是表示单链表的头。通过辅助指针找到新添加节点的位置，
  5. 定义节点插入的方法，使用辅助指针找到要插入位置的前一个位置，然后将新结点指向该位置的下一个节点，该位置的指针域指向新节点。
  6. 定义显示链表方法，通过遍历输出节点的数据域。

代码实现

代码和上述尾部添加法一样，只是多写了一个插入的方法。

publicclassSingleLinkedListDemo{publicstaticvoidmain(String[] args){//代码测试//先创建几个节点HeroNode hero1=newHeroNode(1,"铠","绛天战甲");HeroNode hero2=newHeroNode(2,"瑶妹","遇见神鹿");HeroNode hero3=newHeroNode(3,"吕布","天魔缭乱");HeroNode hero4=newHeroNode(4,"貂蝉","仲夏夜之梦");//创建一个链表SingleLinkedList singleLinkedList=newSingleLinkedList();//插入节点，按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero3);//显示
        singleLinkedList.list();}}//定义SingleLinkedList，管理英雄classSingleLinkedList{//先初始化一个头节点，头节点不要动privateHeroNode head=newHeroNode(0,"","");//添加节点到单向链表//思路：当不考虑编号顺序时//1. 找到当前链表最后的节点//2. 将最后的节点next指向新的节点publicvoidadd(HeroNode heroNode){//因为head节点不能动，因此我们需要一个辅助变量 tempHeroNode temp= head;//遍历链表，找到最后while(true){//当找到链表的最后时，temp.next==nullif(temp.next==null){break;}
            temp= temp.next;//如果没有找到最后，将temp后移}//当推出while循环时，temp就指向了链表的最后，然后让它指向新的节点。
        temp.next= heroNode;}//第二种方式添加英雄，根据排名编号插入（如果有这个排名，则添加失败，并给出提示）publicvoidaddByOrder(HeroNode heroNode){//因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置//因为这是一个单链表，因此找的temp是位于添加位置的前一个节点，否则无法插入HeroNode temp= head;boolean flag=false;//flag标识添加的编号是否存在，默认为falsewhile(true){if(temp.next==null){//说明temp已经在链表最后break;}if(temp.next.no> heroNode.no){//位置找到，在temp后面插入break;}elseif(temp.next.no== heroNode.no){//说明希望添加的hero编号已经存在
                flag=true;//说明编号存在break;}
            temp= temp.next;}//判断flag的值if(flag){//不能添加，说明编号存在System.out.printf("准备插入的英雄的编号 %d 已经存在，不能加入\n", heroNode.no);}else{//插入到链表中，temp的后面
            heroNode.next= temp.next;
            temp.next= heroNode;}}//显示链表【遍历】publicvoidlist(){//判断是否为空if(head.next==null){System.out.println("链表为空！！！");return;}//因为头节点不可以动，因此需要一个辅助变量来遍历HeroNode temp= head.next;while(true){//判断指针是否指向最后if(temp==null){break;}//输出节点信息System.out.println(temp);//将temp后移，一定后移！！！
            temp= temp.next;}}}//定义一个HeroNode，每个HeroNode对象就是一个节点classHeroNode{publicint no;publicString name;publicString nickname;publicHeroNode next;//指向下一个节点// 构造器publicHeroNode(intNo,StringName,StringNickname){this.no=No;this.name=Name;this.nickname=Nickname;}// 为了显示方便，重写 toString 方法@OverridepublicStringtoString(){return"HeroNode{"+"no="+ no+", name='"+ name+'\''+", nickname='"+ nickname+'\''+'}';}

运行结果：

准备插入的英雄的编号3 已经存在，不能加入HeroNode{no=1, name='铠', nickname='绛天战甲'}HeroNode{no=2, name='瑶妹', nickname='遇见神鹿'}HeroNode{no=3, name='吕布', nickname='天魔缭乱'}HeroNode{no=4, name='貂蝉', nickname='仲夏夜之梦'}Process finishedwithexit code0

注意事项

要注意的地方则是新添加的插入方法。

  • 1.注意辅助指针要找的位置，必须是所要插入地方的前一个位置，如果辅助指针指向后一个位置，那么下一步操作则是新节点指向后面这个位置，再下一步操作，发现并没有前驱节点无法指向新节点，“链子”也就断了。
  • 2.另外需要注意的一个地方是，在代码中，是以编号的形式进行排序插入，所以得知道原先链表是否已经有了该编号的数据，所以得先判断，正如代码中设立flag一举动。
  • 3.在辅助指针循环遍历判断完成之后，要将新节点指向后一个节点，而且该位置前一个节点需指向新节点，以连接好链表。

3.按照编号修改节点信息

思路分析

在修改节点信息update方法中：同样第一步先判断链表是否位空，然后借助辅助节点进行遍历查询，找到要修改的节点位置，通过flag判断是否是要修改的节点，最后进行信息更新。

新增的修改节点方法如下图：
在这里插入图片描述
主函数中新增的代码测试部分如下图：
在这里插入图片描述

代码演示

publicclassSingleLinkedListDemo{publicstaticvoidmain(String[] args){//代码测试//先创建几个节点HeroNode hero1=newHeroNode(1,"铠","绛天战甲");HeroNode hero2=newHeroNode(2,"瑶妹","遇见神鹿");HeroNode hero3=newHeroNode(3,"吕布","天魔缭乱");HeroNode hero4=newHeroNode(4,"貂蝉","仲夏夜之梦");//创建一个链表SingleLinkedList singleLinkedList=newSingleLinkedList();//加入//        singleLinkedList.add(hero1);//        singleLinkedList.add(hero2);//        singleLinkedList.add(hero3);//        singleLinkedList.add(hero4);//插入节点，按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);//        singleLinkedList.addByOrder(hero3);//显示System.out.println("未修改的链表信息如下：");
        singleLinkedList.list();//测试修改节点的代码HeroNode newHeroNode=newHeroNode(2,"花木兰","麒麟志");
        singleLinkedList.update(newHeroNode);System.out.println("修改之后链表的信息如下：");
        singleLinkedList.list();}}//定义SingleLinkedList，管理英雄classSingleLinkedList{//先初始化一个头节点，头节点不要动privateHeroNode head=newHeroNode(0,"","");//添加节点到单向链表//思路：当不考虑编号顺序时//1. 找到当前链表最后的节点//2. 将最后的节点next指向新的节点publicvoidadd(HeroNode heroNode){//因为head节点不能动，因此我们需要一个辅助变量 tempHeroNode temp= head;//遍历链表，找到最后while(true){//当找到链表的最后时，temp.next==nullif(temp.next==null){break;}
            temp= temp.next;//如果没有找到最后，将temp后移}//当推出while循环时，temp就指向了链表的最后，然后让它指向新的节点。
        temp.next= heroNode;}//第二种方式添加英雄，根据排名编号插入（如果有这个排名，则添加失败，并给出提示）publicvoidaddByOrder(HeroNode heroNode){//因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置//因为这是一个单链表，因此找的temp是位于添加位置的前一个节点，否则无法插入HeroNode temp= head;boolean flag=false;//flag标识添加的编号是否存在，默认为falsewhile(true){if(temp.next==null){//说明temp已经在链表最后break;}if(temp.next.no> heroNode.no){//位置找到，在temp后面插入break;}elseif(temp.next.no== heroNode.no){//说明希望添加的hero编号已经存在
                flag=true;//说明编号存在break;}
            temp= temp.next;}//判断flag的值if(flag){//不能添加，说明编号存在System.out.printf("准备插入的英雄的编号 %d 已经存在，不能加入\n", heroNode.no);}else{//插入到链表中，temp的后面
            heroNode.next= temp<
  • 作者：一片枯黄的枫叶
  • 原文链接：https://blog.csdn.net/shuyv/article/details/119769405
    更新时间：2022-09-09 08:36:28