【编程驿站】C＋“链链”不忘＠必有回响之单链表

1. 前言

数组和链表是的基石，是逻辑上可描述、物理结构真实存在的具体数据结构。其它的数据结构往往在此基础上赋予不同的数据操作语义，如栈先进后出，队列先进先出……

数组中的所有数据存储在一片连续的内存区域；链表的数据以结点形式存储，结点分散在内存的不同位置，结点之间通过保存彼此的地址从而知道对方的存在。

因数组物理结构的连续特性，其查询速度较快。但因数组的空间大小是固定的，在添加、插入数据时，可能需要对空间进行扩容操作，删除时，需要对数据进行移位操作，其性能较差。

链表中的结点通过地址彼此联系，查询有点繁琐，查询过程有点像古时候通过烽火传递军情一样。而插入、删除操作则较快，只需要改变结点之间的地址信息就可以。

可认为是由结点组成的集合实体，根据结点中存储信息的不同，可把链表分成：

单链表：结点中存储数据和其后驱结点的地址。

循环链表：在单链表的基础上，其最后一个结点，也称尾结点中存储头结点的地址，形成一个闭环。

双向链表：结点中存储数据和前、后驱结点的地址。

双向循环链表：在双向链表的基础上，头结点保存尾结点地址，尾结点保存头结点地址。一般说双向链表都是指双向循环链表。

在链表的基本形式之上，可以根据需要在结点上添加更多信息，如等复杂形式。在链表基础认知之上，请不要拘泥于知识本身，而要善于根据实际需要进行变通。

本文聊聊基于单链表形式的数据查询、插入、删除操作。

2. 单链表

单链表的特点是结点中仅存储数据本身以及后驱结点的地址，所以单链表的结点只有 个域：

存放数据信息，称为数据域。

存放后驱结点的地址信息，称为指针域。

如下图描述了单链表结点的存储结构：

中可以使用结构体描述结点：

当结点与结点之间手牵手后，就构成了：

有 个特殊结点：

头结点：链表的第一个结点，头结点没有前驱结点。头结点可以存储数据，也可以不存储数据，不存储时，此结点为标识用的空白结点，可在链表操作时提供便利。关于第一结点的问题在后文会详细介绍。

尾结点：链表中的最后一个结点，在单链表中其后驱结点的地址为，也就是没有后驱结点。

链表需要一个类型的变量（）用来存储头结点地址，对于整个链表的操作往往都是从保存的头结点开始。

链表还应该提供维护整个结点链路的基本操作算法（抽象数据结构）：

2.1 初始化

链表由多个结点组成，因头结点没有前驱结点，所以需要一个变量存储其地址，此变量称为链表的首地址。后续操作基本都是顺着首地址"顺滕摸瓜"。

当为时，说明此链表为空链表。一般会在初始化时，为变量存储一个没有实际数据语义的标志性结点，也称为空白头结点。

所以初始化时，会有 种方案：

设置 为 。建立一个空链表。

设置指向一个没有实际数据语义的空白结点，此结点仅起到标志作用。

是否一定要提供一个标志性的空白头结点，这不是必须的，但是有了这个空白头结点后，会为链表的操作带来诸多的便利性。一般在描述链表时，都会提供空白头结点。

2.2 创建单链表

创建单链表有 种方案：

创建过程中，新结点替换原来的头结点，成为新的头结点，也称为头部插入创建方案。如构建数据为的单链表。

头部插入创建单链表后，数据在链表中的存储顺序和数据的逻辑顺序是相反的。如上图所示。

注：上述插入演示没有带空白结点。

代码实现：

添加 个结点，测试上述创建的正确性。

执行结果：

从结果可知，输入顺序和输出顺序是相反的。

尾部插入创建单链表，创建时的新结点替换原来的尾结点。如构建数据为的单链表。

尾部插入方案创建的单链表，数据在链表中的存储顺序和数据的逻辑顺序是一致，从而也能保证最终读出来顺序和输入顺序是一致的。

与头部插入创建算法不同，除了需要存储头结点的地址信息，尾部插入算法中还需要一个变量存储尾结点的地址。初始时，和指向同一个位置。

代码实现：

测试尾部插入创建的正确性：

执行后的结果：

前文说过，初始化时，可以指定一个空白头结点作为链表的头结点。其意义在哪里？

可以在尾部创建插入算法中使用或不使用空白头结点了解一下代码的差异性 。上述尾部创建插入算法中，因链表是不带空白结点的，所以在创建新结点时，必须有如下一段代码：

因为刚开始时链表是空的，和都是，创建第一个新结点后，它即是头结点，也是尾结点，所以和都需要指向此新结点。

后续再创建新结点后，则不需修改，通用逻辑是：原来的尾结点成为新结点的前驱结点，新创建的结点成为新的尾结点。

如果在初始化链表时，已经指定了一个空白结点，则尾部创建插入算法中只需遵循通用逻辑便可。

尾部创建插入算法可修改为：

初始链表时如果指定了空白头结点，就不需要考虑第一个结点的位置特殊性。

本文后续的算法都是基于带空白头结点的链表的操作。

2.3 查询链表

链表中的常用查询操作有 种方案：

按结点所在位置查找。

按结点的值查找。

查询链表中的所有结点。

2.3.1 按结点位置查找

设链表的头结点为编号为 的结点，当给定编号 后，从头结点一至向后报数似的进行查找，至到找到与给定值相同的结点 。

2.3.2 按结点的值查找

扫描链表中的每一个结点，比较那一个结点的值和给定的参数值相同。

如果链表带有空白头结点，可以从头结点的后驱结点开始查找。

因为是按值比较，所以，无论链表是否带有空白头结点，都可以从头结点开始进行查找，对结果没有影响。

2.3.3 查询所有

不带空白头结点遍历操作：

带空白头结点的遍历：

2.4 插入

链表创建好后，后续维护过程，难免时时需要插入新的结点。插入时可以如前文在创建链表时一样，在头部插入和尾部插入。这里的插入指在链表的某个中间位置插入新结点。

后插入。

前插入。

2.4.1 后插入

所谓后插入，指新结点插入到某个已知结点的后面。如下图所示：

如果把值为 的新结点插入到值为 的结点之后，称为后插入。后插入的通用逻辑：

查找到值为的结点地址，称为 结点。

创建新结点。

指定新结点的后驱结点为的后驱结点。

指定的后驱结点为新结点。

代码实现：

测试后插入操作：

执行后输出结果：

2.4.2 前插入

所谓前插入，指新结点插入到某个已知结点的前面。如下图所示：

如果把新结点插入到已知结点的前面，则称为前插入。前插入的通用逻辑：

除了要查找到结点在链表中的地址，还需要知道结点的前驱结点的地址。

创建新结点，然后指定新结点的后驱结点为结点。

指定结点的后驱结点为新结点。

代码实现：

测试前插入操作：

执行后输出结果：

如果仅仅是关心数据在链表中的逻辑关系，则可以先把新结点插入到结点的后面，然后交换 个结点中的数据。

2.5 删除

删除算法包括：

删除某一个结点。

删除所有结点，也称为清空链表。

2.5.2  删除结点

删除结点的基本思路：

在链表中查找到要删除的结点。

找到结点的前驱结点。

指定 的后驱结点为 的后驱结点。

编码实现：

测试删除操作：

输出结果：

2.5.2 清空链表

清空链表指删除所有结点。从头结点开始扫描，找到一个删除一个，真到没有结点为止。

测试：

输出结果：

2.6 时间复杂度分析

在链表中查询的时间复杂为 。

在链表中进行插入操作时，先要查找到结点，如果不计查找时间，仅从插入算法本身而言，后插入算法时间复杂度为。因前插入算法需要要查找前驱结点，时间复杂度为。

删除结点时同样需要查找到被删除结点的前驱结点，时间复杂度为，如果是删除某个结点的后驱结点，时间复杂度为。

通过上述的基本操作得知：

单链表上插入、删除一个结点，需要知道其前驱结点的地址。

单链表不具有按序号随机访问的特点，只能从头结点开始依次查询。

3. 总结

本文主要讲解单链表的概念以及基于单链表的基本操作算法，除了单链表，还有循环链表、双向链表，将在后继博文中再详细讨论。无论链表的结构如何变化，单链表都是这种变化的始端。