【数据结构】链表的概念 及 分类 （使用比喻解释概念）

一. 链表的概念及结构

概念：链表是一种 物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的。

1.1 超级通俗的比喻

 

链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。

车厢是独立存在的，且每节车厢都有车门。想象一下这样的场景，假设每节⻋厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车头走到车尾？最简单的做法：每节车厢里都放一把下一节车厢的钥匙。

1.2 在链表里，每节"车厢"是什么样的呢？

• 与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为"结点/节点"
• 节点的组成主要有两个部分：数据域：当前节点要保存的数据  和  指针域：保存下一个节点的地址（指针变量）。
• 图中指针变量  plist  保存的是第一个节点的地址，我们称  plist此时“指向”第一个节点，如果我们希望plist“指向”第二个节点时，只需要修改  plist  保存的内容为  0x0012FFA0。

• 为什么还需要指针变量来保存下一个节点的位置？
• 链表中每个节点都是  独立申请  的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。
• 结合前面学到的结构体知识，我们可以给出每个节点对应的结构体代码：
• 假设当前保存的节点为整型：
• 创建一个节点

• struct SListNode
  {
  	int data; //节点数据
  	struct SListNode* next ; //指针变量用保存下一个节点的地址
  };

       当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个节点的地址（当下一个节点为空NULL  时保存的地址为空NULL）。
当我们想要从第一个节点走到最后一个节点时，只需要在前一个节点拿上下一个节点的地址（下一个节点的钥匙）就可以了。

1.3 总结：对应 1.1 节 的 比喻 和 链表的关系

• 火车 == 链表
• 车厢 == 节点
• 车头 == 第一个节点
• 车头自己的钥匙 == 上图中的 plist ，存放第一个节点的地址
• 下一个车厢的钥匙 == 节点存放的指针
• 尾车厢没钥匙 == 尾节点 指针域为 NULL
• 各个车厢相对独立 == 各个节点相对独立

1.4 补充说明：

1 、链式结构在逻辑上是连续的，在物理结构上不一定连续

2 、节点一般是从堆上申请的

3 、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

二. 链表的分类

1.1 链表的多样 和 说明

链表的结构非常多样，以下情况组合起来就有 8 种（2x2x2）链表结构：

1.1.1 一些解释说明

带头链表：

在单链表中，我们提到的“头节点”的“头”和“带头”链表是两个概念

单链表中提到的 “头结点” 指的是第一个有效的节点 “带头” 链表里的 “头” 指的是无效的节点

带头链表的 头结点: 哨兵位 (不保存任何有效的数据)

 循环链表：

一般链表的 尾节点 next 指向 NULL，

而 循环链表 尾节点 next 指向 头节点，刚好 头尾相连，形成一个环状，即循环

1.2 链表说明：

虽然链表的种类非常之多，但是使用比较多的只有两种:单链表〈不带头单向不循环链表) 和 双向链表（带头双向循环链表), 学会了这两种链表(代表的两种 最复杂 或 最简单 的情况)，其他 6 种的实现就会了

1. 不带头单向非循环链表( 单链表 )： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结构 ，如哈希桶、图的邻接表 等等。另外这种结构在 笔试面试 中出现很多。

2. 带头双向循环链表( 双向链表 )：  结构最复杂 ，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。