链表的基本介绍

链表是有序列表,链表的英文是LinkedList

链表的特点:

1. 链表是以结点方式来存储的,链表是链式存储

2. 链表中的每个结点都分data域和next域

   data域 : 用来存放数据

   next域:用来指向下一个结点

   下面展示的是 链表再内存中的实际结构的布局图：

3. 链表的各个结点不一定是连续存储的

4. 链表分为带头结点的链表和不带头结点的链表,具体要不要带头结点,根据自己的需求而定

---

链表的实际案例

实现：管理在线的用户

需求：在某个约定时间，把某个人的好友发送给服务器，但是发送过去的好友编号并不是连续的，要求在服务器上把所有的好友信息按照编号的顺序返回给客服端，因为客服端要定时地向服务器去询问其好友的状态，而服务器需将客服端发送过来的好友按照编号顺序返回，比如说客服端发送过来某一个人的好友编号是 20、1、19、38、5，发给服务器后，要求把这个人的状态返回给客服端，但是要求返回的好友编号顺序是按照从小到大的顺序排列的，比如 1 、 5、19 、20、38，并且不允许查数据库，不能将数据存入数据库中，然后通过order by返回，这样是不允许的。要求在内存中就将这个排序工作做完，有时间和速度要求。

解决方法：使用链表来实现

实现思路：获取到好友Id编号后，按照顺序插入到单向链表中去

---

带头结点的单链表的逻辑结构，如下图所示

根据上图做描述：头结点指向a1,a1执行a2,a2指向a3，依此类推，若链表中最后一个结点的next域为null就代表链表结束了。

从上图看出a1后面就是a2,a2后面就是a3,依此类推。但这只是逻辑结构，之所以这样画是因为a1的下一个next域正好是指向a2的，但实际上在内存中，a1后面并不一定马上指的就是a2，a1的next域只是通过指针指向了a2的一个地址，最后将它们连成了一个单链表。该图链表中的各个结点看起来好像是连续存储的，但实际上不是。在做开发做分析时，往往都是这样画链表。实际的存储如下图所示：

---

单链表的应用实例

使用带head头结点的单向链表实现实现水浒英雄排行榜的管理，即：用链表来管理一些英雄人物

目标：完成对英雄人物的增删改查，也就是对结点的增删改查的操作

创建单链表的形式:

1. 直接添加在链表尾部，不考虑排序

   即：给我一个英雄对象，我就把它加入到链表最后，不考虑排序

2. 在添加结点时，考虑排序

   即：在添加英雄时，考虑其排名

---

创建单链表的示意图（添加） 和 遍历单链表的思路分析：

何为创建？即 添加，添加结点的同时产生链表。

注意:

1. head头结点不存放具体的数据
2. head头结点的作用:就是用来连接整个链表，表示单链表的头

根据上图，分析创建单链表的思路：

当我创建一个新的HeroNode结点，然后让头结点的next域指向这个新建的HeroNode结点，这个新建的HeroNode结点中有两个部分，分别具体的数据（即：data域）和next域，这个新建的HeroNode结点的next域又指向下一个HeroNode2结点，若还有一个HeroNode3结点，则让前一个HeroNode2结点的next域指向后一个HeroNode3结点。这样就形成了一个链表。若最后一个HeroNode3结点不再指向任何结点了，那这最后一个HeroNode3结点的next域默认为null

总结创建（添加）单链表步骤：

第一步，先创建一个head结点，作用就是用来连接整个链表，表示单链表的头

第二步，后面每添加一个结点，就直接加入到链表的最后

问题：

1. 怎么去判断链表中的哪一个是最后的结点呢？

   答：是以判断结点的next域是否为空来决定这个链表是否结束

遍历显示单链表的思路分析:

遍历时，通过定义一个临时变量（或者叫做辅助指针），帮助遍历整个单链表，因为head结点不能动,若head头结点变化了,就找不到链表最后那个结点了.

---

用代码分析实现单向链表

链表最重要的就是增删改查

1. 首先定义一个HeroNode类,每个HeroNode对象就是一个结点

   代码实现:

   class HeroNode {
        
         
       // 编写属性(共4个)
       // data域 用来存放具体的数据
       public int id;
       public String name;
       public String nickName;
       // next域  用来指向下一个结点
       public HeroNode next;  // 最重要的一个属性
       // 无参构造
       public HeroNode() {
        
         
           
       }
       // 带参构造,实现将局部变量的值赋值给成员变量
       public HeroNode(int id,String name,String nickName) {
        
         
           // 对属性进行初始化
           this.id  = id;
           this.name = name;
           this.nickName = nickName;
       }
       // 重写toString()方法,为了显示 | 遍历方便
       @Override
       public String toString() {
        
         
           return "HeroNode{" +