数据结构与算法之美笔记——链表（上）

摘要：

链表和数组一样，也是基础常用的数据结构之一，由于采取了与数组不同的数据存储方式，导致链表的随机访问、插入和删除操作时间复杂度都为 $O(n)$ ，链表有多种类型，如单链表、循环链表和双向链表等。

链表的特性

链表有许多类型，接下来先以最简单的单链表进行分析。要了解链表的特性先得了解链表是如何存储的，链表每个存储单元被称为「结点」，结点不仅会存储数据本身，还会存储一个指向下一结点的指针，这个指针称为「后继指针」，链表的第一个结点被叫做「头结点」，最后一个结点被称为「尾结点」，链表可以依靠头结点查找整个链，而尾结点后继指针通常不指向其他结点，所以尾结点的后继指针存储空地址。

链表与数组存储方式的区别说明了链表不需要进行连续存储空间的申请，这样对存储的利用率比较高，不会像数组因为申请不到相应大小的连续存储空间导致失败。

随机访问、插入、删除的时间复杂度

根据链表的特点，如果需要随机访问链表中的某个结点，链表只能从头结点开始依靠后继指针遍历结点，直到查找到相应结点结束，假设链表结点个数为 n，随机访问每个结点的机率相同，都为 $1/n$ ，访问每个结点时分别需要遍历链表结点 1,2,3,...,n 次，所以时间复杂度为

$T(n)=\frac{1}{n}+\frac{2}{n}+\frac{3}{n}+...+\frac{n}{n}=\frac{\frac{n\times(n+1)}{2}}{n}=\frac{n+1}{2}=O(n)$

进行插入操作时，只需要在结点要插入的地方将前一个结点指向需要插入的结点，插入的结点再指向下一个结点即可，所以时间复杂度为 $O(1)$ ，删除操作也是同理，将需要删除结点的前一结点指向删除结点的后一结点即可，时间复杂度也是 $O(1)$ ，插入和删除操作可对照下图进行理解。

链表插入删除操作图

可以将以上链表的分析与数组类似操作对比，能够看出链表结点因为不是使用连续存储空间存储，所以随机访问时间复杂度比较高，但同样也是因为不需要像数组一样保持连续存储空间，在插入和删除操作时不需要和数组一样进行数据搬移，所以时间复杂度比较低。

链表类型

链表主要有「单链表」、「循环链表」和「双向链表」三种类型，单链表在上面的例子中已经详细讲过，接下来分析复杂一些的循环链表和双向链表。

循环链表

循环链表就是指链表的尾结点后继指针是指向头结点的链表，这样的链表从尾结点到头结点会比较方便，适合处理环型结构的数据。

循环链表

双向链表

双向链表指链表中的结点在指向后面一个结点的同时也会指向前面一个结点，有两个方向，结点中指向前一个结点的指针叫做「前驱指针」。双向链表因为支持链表两个方向的遍历，所以在进行插入和删除操作时比单链表更加高效。

双向链表

双向链表的插入和删除

之前分析过单链表的插入和删除时间复杂度都是 $O(1)$ ，双向链表比单链表的插入、删除操作更加高效的话还能将时间复杂度降低到什么程度？

其实单链表分析的插入和删除操作的时间复杂度并不全面，下面以删除结点为例分析，在实际中对链表的删除操作存在两种情况

删除指定值的结点
删除指定指针的结点

如果是删除指定值的结点，无论是单链表还是双向链表都需要遍历结点进行删除，虽然删除操作时间复杂度是 $O(1)$ ，但是查找结点时间复杂度是 $O(n)$ ，根据时间复杂度的加法法则，整个删除操作时间复杂度是 $O(n)$ 。

如果是删除指定指针的结点的情况，通过指定指针就可以找到需要删除的结点，但删除操作需要先找到当前结点的前一个结点，单链表就需要对链表进行遍历找到前一个结点，时间复杂度就为 $O(n)$ ，而双向链表因为存储有前驱指针，可以在 $O(1)$ 时间复杂度下找到前一个结点，所以这种情况下的删除操作双向链表可以将时间复杂降为 $O(1)$ ，插入结点同理。

虽然双向链表在操作上更加方便高效，但是双向链表的结点需要使用更多的空间来存储前驱指针，在结点存储的数据占存储较小的情况下存储指针的资源消耗比较明显，当结点存储的数据占据存储比较大时，存储前驱指针消耗也就可以忽略，这也是算法中「空间换时间」的思想。

课后题目

判断回文链表
题目解答可点击此处查看。

文章中如有问题欢迎留言指正
数据结构与算法之美笔记系列将会做为我对王争老师此专栏的学习笔记，如想了解更多王争老师专栏的详情请到极客时间自行搜索。