目录

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

1. 链表介绍

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

https://img.dawnguo.cn/Algorithm/2_2_0.jpg

1.1. 单链表

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

https://img.dawnguo.cn/Algorithm/2_2_1.jpg

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

1.2. 循环链表

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

https://img.dawnguo.cn/Algorithm/2_2_2.jpg

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

1.3. 双向链表

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

https://img.dawnguo.cn/Algorithm/2_2_3.jpg

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

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

    在某个结点前面插入一个结点的情况,也是一样的。

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

1.4. 其他链表

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

    https://img.dawnguo.cn/Algorithm/2_2_4.jpg

2. 链表和数组比较

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

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

    CPU 在从内存读取数据的时候,除了把要访问的地址的数据读取进来,还要读取附近的一个数据块并保存到 CPU 缓存中。这样下次访问内存的时候,就会先从 CPU 缓存开始查询,如果找到了就不需要从内存中读取,从而使得访问数据更快。那么对于数组来说,因为是连续的,所以加载数组中某数据的时候,会把数组中的其他数据也加载进来,从而导致数组的访问效率会更高。然而链表不是连续存储的,因此加载附近的数据块不一定会加载到链表中的数据。

  • 数组的缺点是大小固定,那么当数组出现不够用的情况时,需要申请一个更大的内存空间,然后把数据迁移过去,这个是非常耗时的。而链表本身没有大小的限制,天然支持动态扩容。这是另一个区别。

  • 链表进行频繁的插入、删除等操作会导致频繁的内存申请和释放,容易造成内存碎片。这对 Java 来说会导致频发的 GC(Garbage Collection,垃圾回收)。而数组相对来说没那么频繁。

3. 链表代码的撰写

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

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

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

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

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

https://img.dawnguo.cn/Algorithm/2_2_5.jpg

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

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// 非第一个结点插入
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:哨兵的意思让我想到了当兵的,当兵的就是要整齐统一的,因此引入哨兵之后,就变得统一了)

https://img.dawnguo.cn/Algorithm/2_2_6.jpg

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

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

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

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

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

3.5. 举例画图,辅助思考

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

3.6. 多写多练,没有捷径

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

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

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

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

4. 应用场景

  1. 使用单链表来实现 LRU 缓存淘汰算法。首先维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,从链表头开始顺序遍历链表。

    • 如果该数据在链表中,那么删除数据对应的结点,然后将其添加到头结点的位置。
    • 如果此数据没有在链表中,那么根据缓存空间是否已满来分别进行处理。如果未满的话,那么直接插入到链表的头部;如果已满的话,那么将链表尾结点删除,将新的数据结点插入到链表的头部。

    由于不管缓存有没有满,都需要遍历一遍链表,因此这种方式实现的时间复杂度是 O(n)。

    另外联系生活:比如自己容量有限,清除掉自己觉得没用的东西。

  2. Java 中的 LinkedHashMap 容器,使用的就是双向链表这种数据结构。

  3. 空间换时间或者时间换空间的思想:对于执行较慢的程序,可以通过消耗更多的内存(空间换时间)来进行优化;而消耗过多内存的程序,可以通过消耗更多的时间(时间换空间)来降低内存的消耗。比如双向链表中,就是空间换时间的思想,通过拿出另一个指针域来存储前驱结点地址,从而使得有些操作很方便。比如缓存结构中,也还是空间换时间的思想。先把数据加载到内存或者更快的缓存上,虽然带来了空间上消耗,但是速度却上去了。

  4. Linux 内核很多地方也是用到了链表的。

5. 总结

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

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

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

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

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

巨人的肩膀

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