数据结构之——链表一（链表结构）【更新中】

[yaodebian]

其他平台文章地址

• csdn：https://blog.csdn.net/YaoDeBiAn/article/details/101117630
• 知乎：https://zhuanlan.zhihu.com/p/83549181

概况

与数组类似，链表是一种线性结构，如图所示：

链表结构与数组结构有什么区别呢？

• 数组：连续固定的内存空间，对内存要求较高；
• 链表：零散的一系列内存通过指针的形式串接在一起；

现在假设有这样一个场景：目前系统拥有的剩余内存空间充足，现在如果需要申请 100MB 的数组或者链表，系统中虽然剩余空间大于 100MB，但没有大于或等于 100MB 的连续内存块，那么数组将声明成功，链表因为不受内存连续影响，故而能够申请成功。

基于最基本的链表结构，链表也衍生出了几种不同的形式：

• 单链表
• 双向链表
• 循环链表

单链表——最简单的链表形式

其结构如果所示：

上面的结构由一个个内存块连接组成，每个内存块称为结点，结点由两部分组成，一部分用来存储数据，一部分用来纯存储下一个节点的地址，也就是一个指针，这个指针我们称为后继指针。

除此之外，链表有两个特殊的结点，即第一个结点和最后一个结点，我们习惯性把它们称为头结点和尾结点：

• 头结点（Head）：用于记录链表的基地址，通过基地址可以遍历链表中的每一个元素；
• 尾结点（Tail）：后继指针为 null，表示这是链表的最后一个结点。

链表的插入、删除、查找操作

如下图所示：

由上图可知，链表的插入与删除操作非常简单，只要经过一两步对后继指针的重新指向就可以完成，所以它们的时间复杂度为 O(1)。

另外，由于链表是由一系列零散的结点组成，无法进行类似数组通过下标访问对应结点的操作，查找每个结点都要从头结点开始一直遍历，直到找到相应的结点，所以时间复杂度为 O(n)。

循环链表

其结构如图所示：

就跟“循环链表”这四个字所说的那样，该结构通过尾结点的后继指针指向头指针形成一个闭环结构，当要处理的数据具有环型结构特点时，就特别适合采用循环链表，如著名的约瑟夫问题。

双向链表

双向链表是在单链表的基础之上在每个结点上增加了一个前驱指针（prev），以使得双向访问变得可能，如图所示：

双向链表在结构上比单链表多了前驱指针，也就表示这种结构将会占用更多的内存，那么在占用内存更高的情况下，其性能相比于单链表是怎样的呢？

首先从插入操作的角度看：

• 当在某个指定结点之后插入某个结点时，双向链表和单链表的操作一样，即时间复杂度为 O(1);
• 当在某个指定结点之前插入某个结点时，由于单链表不知道前驱结点，则需要遍历一次，时间复杂度为 O(n)，相反双向链表时间复杂度为 O(1)；

然后从删除操作的角度看：

• 当删除结点中“值等于某个给定值的结点”时，由于两种结构均需要从头结点出发并依依比对，所以在这种情况下，两种结构的时间复杂度均为 O(n)；
• 当删除指定结点指向的结点时，由于删除操作需要知道结点的前一个结点和后一个结点，单链表在不知道其前驱结点的情况下，需要从头遍历，其时间复杂度为 O(n)，双向链表在知道前驱结点的情况下仅仅需要一步操作就能完成删除操作，其时间复杂度为 O(1)。

最后，从查询的角度思考：

一般的情况下，两者都是遍历查询，时间复杂度为 O(n)，但假如链表内的内容是有序的，双向链表会比单链表高效。因为我们每次查询之后可以记录上次查找的位置 p，然后根据查找值与 p 的大小关系决定往前还是往后查找，所以平均只需要查找一半的数据。

双向循环链表

即双向链表与循环链表的结合，如图所示：

链表与数组时间复杂度比较

	数组	链表
插入和删除(insert and delete)	O(n)	O(1)
随机访问(access)	O(1)	O(n)

以上是两种数据结构一般情况下的时间复杂度，那么我们能够根据上面的时间复杂度来选择使用哪种数据结构吗？

不能，比如：

• 数组简单易用，由连续的内存空间组成，借助 CPU 的缓存机制，可预读数组中的数据，访问率会更高；
• 如果对内存的使用非常苛刻，可以选择数组，因为相同的存储数据，链表需要额外的内存空间存储每一项结点中的前驱指针或后继指针，而且频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片。

总结

和数组相比，链表更适合插入、删除操作频繁的场景，查询的时间复杂度较高。不过，在具体软件开发中，要对数组和链表的各种性能进行对比，综合来选择使用两者中的哪一个。

另外，在日常 coding 中，我们可以采用用空间换时间或者时间换空间的思想：

• 用空间换时间：内存足够大的情况下，可以选择牺牲空间复杂度来减少时间复杂度；
• 时间换空间的思想：内存比较苛刻的情况下，可以选择牺牲时间复杂度来减少空间复杂度，也就是减少空间占用；