数据结构和算法 | 数组之上-链表【3】

1. 链表介绍

从底层的存储结构来看，数组需要一块连续的内存空间。而链表不需要一块连续的内存空间。通过“指针”将一组零散的内存块串联起来使用。下图中橙色的地方即分散的内存块，内存块又可以被称为结点。下面介绍几种常见的链表结构：单链表、循环链表、双向链表。

1.1. 单链表

单链表中，链表的结点除了存储数据之外，还需要记录链表上的下一个结点的地址，记录下一个结点地址的指针被叫做后继指针。在单链表中，有两个结点比较特殊，分别是第一个结点（头结点）和最后一个结点（尾结点）。头结点用来记录链表的基地址，尾结点指向一个空地址 NULL。

在链表中插入、删除一个数据，不需要像数组那样保持连续的，只需要考虑相邻结点的指针改变即可。因此，链表中的插入、删除操作是很快的，时间复杂度是 O(1)。由于不是连续的，无法通过数组那样的寻址公式就能访问到第 k 个元素，因此链表访问第 k 个元素的时候，需要一个一个遍历下去，那么需要 O(n) 的时间复杂度。

1.2. 循环链表

循环链表跟一种特殊的单链表，跟普通的单链表唯一的区别就是尾结点指针是指向链表的头结点的。如下图所示

和单链表相比，循环链表的优点是从链尾到链头比较方便，这在处理具有环形结构的数据时特别适合。

1.3. 双向链表

单链表只有一个方向，而双向链表支持两个方向。每个结点不止有一个后继指针，还有一个前驱指针指向前面的结点。因此双向链表的结点中，需要额外的两个空间来存储后继结点和前驱结点的地址。

虽然两个指针域比较浪费空间，但是可以支持双向遍历，带来了操作的灵活性。比如

双向链表中可以在 O(1) 时间复杂度的情况下找到前驱结点。这样的话，在已经找到要删除结点的情况下，删除该结点的时间复杂度为 O(1)。为什么这么说呢？因为在删除结点的时候，需要对前驱结点和后继结点进行指针域的改变。使用双向链表的话，可以很方便找到的前驱结点和后继结点。而针对单链表，因为不知道前驱结点，因此需要从头开始遍历，直到找到一个结点，这个结点的后继结点是要删除的结点为止，那么这个寻找的操作对于单链表来说，时间复杂度是 O(n)。

在某个结点前面插入一个结点的情况，也是一样的。
对于有序链表来说，双向链表的按值查询（找到等于要查询的值的结点）的效率要比单链表高些。因为可以记录上次查找的位置 P，每次查找先跟 P 所在结点的值进行比较，从而决定是往前找还是往后找。那么平均只需要查找一半的数据。

1.4. 其他链表

双向循环链表 --- 就是将循环链表和双向链表结合在一起

2. 链表和数组比较

插入、删除、随机访问操作的时间复杂度正好相反

操作数组链表

插入删除 O(n) O(1)

随机访问 O(1) O(n)
在实际开发中，不能单纯使用复杂度分析来判断选择哪种数据结构来存储数据。数组本质上是连续的内存空间，CPU 的缓存机制会预先读取数组中的数据，所以访问效率更高。而链表不是连续存储的，因此 CPU 缓存没办法有效预读链表数据。

CPU 在从内存读取数据的时候，除了把要访问的地址的数据读取进来，还要读取附近的一个数据块并保存到 CPU 缓存中。这样下次访问内存的时候，就会先从 CPU 缓存开始查询，如果找到了就不需要从内存中读取，从而使得访问数据更快。那么对于数组来说，因为是连续的，所以加载数组中某数据的时候，会把数组中的其他数据也加载进来，从而导致数组的访问效率会更高。然而链表不是连续存储的，因此加载附近的数据块不一定会加载到链表中的数据。
数组的缺点是大小固定，那么当数组出现不够用的情况时，需要申请一个更大的内存空间，然后把数据迁移过去，这个是非常耗时的。而链表本身没有大小的限制，天然支持动态扩容。这是另一个区别。
链表进行频繁的插入、删除等操作会导致频繁的内存申请和释放，容易造成内存碎片。这对 Java 来说会导致频发的 GC（Garbage Collection，垃圾回收）。而数组相对来说没那么频繁。

操作	数组	链表
插入删除	O(n)	O(1)
随机访问	O(1)	O(n)

3. 链表代码的撰写

争哥根据自己的学习经历和工作经验，总结了几个写链表代码技巧。

3.1. 理解指针或引用的含义

C 语言有“指针”的概念，有些语言没有指针的概念，但是有“引用”的概念。**不管是指针还是引用，意思都是一样的，都是存储所指对象的内存地址。**比如 p->next = p->next->next 表示 p 的 next 指针存储了 p 结点的下下一个结点的内存地址。

3.2. 警惕指针丢失和内存泄漏

写链表代码的时候，一定要注意插入或者删除的顺序，否则很容易把指针或者结点给弄丢（这个自己确实碰到过哈哈哈哈）。比如要在 a、b 两个结点之间插入结点 x，假设当前指针 p 指向结点 a

如果使用下面这段代码则会发生指针丢失和内存泄露，因为 x->next 最终指向了自己。整个链表被断成两段，结点 b 及之后的所有结点都无法访问到了。

p->next = x;  // 将p的next指针指向x结点；
x->next = p->next;  // 将x的结点的next指针指向b结点；

另外，对于 C 语言来说，内存管理是由程序员负责的。如果没有手动释放结点对应的内存空间，那么会导致内存泄露。所以插入结点的时候，要注意先后顺序。对于刚才的代码，只要调换一下顺序即可。同理，删除结点对于 C 语言来说也一定要记得释放内存，否则也会出现内存泄露的问题。Java 因为有 GC 所以不需要考虑那么多。

3.3. 利用哨兵简化实现难度

**哨兵的主要作用是让代码变得统一。**因为在对链表进行插入、删除操作时，需要对插入第一个结点或者删除最后一个结点的情况进行特殊处理，如下所示。但是，这样让代码变得很繁琐、不简洁。

// 非第一个结点插入
next_node->next = p->next;
p->next = new_node;

// 第一个结点插入
if (head == null) {
    head = new_node;
}

// 删除非最后一个结点
p->next = p->next->next;

// 删除最后一个结点
if (head->next == null) {
    head = null;
}

为此可以引入哨兵结点，让上述代码变得统一一点。比如不管链表是不是为空，让 head 一直指向一个结点，这个结点是不带数据的，只有指针域，如下所示。这样删除最后一节点的时候和插入第一个结点的时候，操作就都变得统一了。而这个结点就是哨兵结点，我们把有哨兵结点在的链表称为带头链表。（PS：哨兵的意思让我想到了当兵的，当兵的就是要整齐统一的，因此引入哨兵之后，就变得统一了）

哨兵节点在插入排序、归并排序、动态规划中都会用到。

3.4. 重点留意边界条件处理

**在编写的时候一定要多注意边界条件是否考虑到了，在边界条件下能否正确运行。**边界条件，个人理解就是极端情况，比如链表为空等。那么链表代码需要检查的边界条件主要有：

链表为空的时候；
链表只包含一个结点的时候；
链表只包含两个结点的时候；
处理头结点和尾结点的时候；

在写任何代码的时候，一定要多想想，你的代码在运行的时候，可能会遇到哪些边界情况或者异常情况，针对这些情况一定要处理，这样代码才能健壮。

3.5. 举例画图，辅助思考

针对链表的操作，有时候光在脑子里比较难想清楚，那么可以使用举例法和画图法，这样会清晰许多。

3.6. 多写多练，没有捷径

**自己把常见的链表操作多写几遍，出问题就一点一点调试，孰能生巧。**写链表代码是最考研逻辑思维能力的，因为链表代码到处都是指针的操作、边界条件的处理，稍有不慎就会产生 bug。链表代码写得好坏，可以看出一个人写代码是否够细心，考虑问题是否全面，思维是否缜密等（这也是面试官喜欢让人手写链表代码的原因）。那么针对链表代码，可以拿这几个链表操作练练手，一定要练啊！

单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第 n 个结点
求链表的中间结点

LeetCode 上的题号分别是 206，141，21，19，876。

leetcode 上 206，141，21，19，876。

4. 应用场景

使用单链表来实现 LRU 缓存淘汰算法。首先维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表。
- 如果该数据在链表中，那么删除数据对应的结点，然后将其添加到头结点的位置。
- 如果此数据没有在链表中，那么根据缓存空间是否已满来分别进行处理。如果未满的话，那么直接插入到链表的头部；如果已满的话，那么将链表尾结点删除，将新的数据结点插入到链表的头部。
由于不管缓存有没有满，都需要遍历一遍链表，因此这种方式实现的时间复杂度是 O(n)。

另外联系生活：比如自己容量有限，清除掉自己觉得没用的东西。
Java 中的 LinkedHashMap 容器，使用的就是双向链表这种数据结构。
空间换时间或者时间换空间的思想：对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。比如双向链表中，就是空间换时间的思想，通过拿出另一个指针域来存储前驱结点地址，从而使得有些操作很方便。比如缓存结构中，也还是空间换时间的思想。先把数据加载到内存或者更快的缓存上，虽然带来了空间上消耗，但是速度却上去了。
Linux 内核很多地方也是用到了链表的。

5. 总结

与数组一样，链表也是一种线性表，最大的区别在于底层的存储结构，链表不需要一块连续的内存空间，而数组是需要的。因此，链表中的一个结点（一块内存块）除了数据之外，还需要用来存储下一个结点地址的空间。常见的链表有单链表，循环链表，双向链表等。

链表和数组由于底层的存储结构发生了改变，因此有些操作的时间复杂度也跟数组不一样，或者说相反。数组中根据索引查找一个元素的时间复杂度是 O(1)，插入/删除操作（不考虑优化的情况，即删除则移动）的平均时间复杂度是 O(n)。而在单链表中插入/删除操作（不考虑找到插入/删除位置的时间复杂度）的时间复杂度是 O(1)。由此可见是完全相反的。

链表的应用场景很多，比如 LRU 缓存淘汰算法就可以使用单链表实现。比如 Java 的LinkedHashMap 容器的底层实现。然而链表中还有一个重要的应用思想是空间换时间，比如双向链表中使用一个额外的空间来存储前驱结点，那么省得有些操作会更省时间，比如在一个有序（如升序）的链表中，前一次找到了一个值所处的位置，那么之后再进行查找的时候，假如这个值比当前值小，则可以往前查找。在操作系统中，缓存的使用也是空间换时间的应用。

下面总结一下自己对链表实现的一些注意事项吧。链表是无哨兵结点的，也就是 head 指针直接指向头结点的。

对于插入位置已经确定了的，比如 insertToHead 或者 insertToTail 来说，需要考虑是不是第一个插入的问题；
对于插入位置不确定的，比如 insertAfter insertBefore 来说，除了判断是否是空链表之外，还需要判断是否找到相关的插入的结点，以及找到的结点的位置，个人觉得分别三个，第一个结点、中间结点、尾结点；
对于删除位置不确定的，几乎同上。
对于查找来说，几乎也是一样的，判断是否是空链表，判断怎么样才算是找到了结点，怎样又算没找到结点。

巨人的肩膀

极客时间-《数据结构与算法》-王争老师