简述
链表通常是算法学习者学习完数组基础后紧接着学习的下一个初级数据结构。
链表本身的概念非常简单, 凡是「通过指针串联在一起的线性结构」都可以称之为链表。 链表的题一般集中在简单和中等题, 不过链表一般指的是题目传进来的数组结构, 而不是具体的解题方法, 这一点和数组类似。
但是基础不扎实的话在面试手写链表时很容易翻车。这并不算是危言耸听, 因为大多数时候, LeetCode这些平台为了实现自动化打分, 凡是涉及链表的题, 链表节点的数据结构都已经提供好了, 刷题的时候照着写就行。 这会导致很多刷题很久的应届毕业生在面试时需要手撕链表的时候才会发现, 自己好像从来没有亲手实现过链表。
链表基础
如上文所说, 链表基础很重要, 但实现起来真的不复杂, 只需要做好「增、删、访、查、初始化」, 掌握链表就如同掌上观纹一般清晰。
1. 初始化链表
链表的组成单位是节点(node)对象。每个节点都包含两项数据: 节点的“值”和指向下一节点的“引用”。基于这个定义, 我们可以写出如下代码:
class Node:
def __init__(self, val: int):
self.val: int = val
self.next: Node | None = None
初始化链表需要特别注意的其实就是头节点和尾节点, 因为头节点是访问整个链表的入口, 做题时轻易不可以乱修改这个指针。至于尾节点, 则需要确保指针指向空 (Python中的None, JS中的null, etc), 否则遍历链表时不知何时终止。
2. 删除节点
不同于数组中删除元素后还需要把其余元素重新排列以填充空缺的位置, 我们在链表中找到了需要删除的节点后, 只需要将其父亲节点的next指针直接指向下一个节点后, 删除后的链表就已经成型了, 被分离出来的节点可以当场destroy也可以另作他用。
3. 插入节点
和删除节点逻辑类似,在链表中添加元素只需要修改前后两个节点而已,让前面节点的next指向自己, 并让自己的next指向下一个节点。
4. 访问节点
不得不承认, 在链表中访问节点的效率较低。 不同于数组可以根据索引在O(1)时间内找到元素, 链表需要从头节点出发向后遍历, 知道找到目标节点, 然后访问。
5. 查找节点
链表中查找节点和访问节点的方法一致, 事实上, 访问节点 = 查找节点 + 访问节点 。
链表 vs. 数组
相信对于很多算法学习者和面试者来说, 判断是否应该使用链表的唯一条件就是题目是否要求使用链表。站在学习者的角度这个想法其实没有问题, 但如果作为一个软件工程师, 拿到一个需求后从零开始设计算法时又应该如何选择基本数据结构?
思考至此, 或许有些人会对链表的存在产生质疑: 数组的出现是因为其线性结构最符合计算机内存的结构, 那我们为什么需要多此一举, 搞出来链表这种「离散」但还是「线性」的数据结构呢?
在我看来, 有了这一层思考, 才算是真正开始学习链表的精髓了, 我们可以通过对比数组和链表来更加深入思考链表存在的意义。
链表的生存之道: 碎片内存大团结
首先, 我们回到计算机系统的层次考虑问题, 内存空间是所有程序的公共资源, 在一个复杂的系统运行环境下, 空闲的内存空间可能散落在内存各处, 就算再高级、智能的内存调度系统也无法避免这个现象的存在。
而根据数组篇第一章我们已经知道, 存储数组的内存空间必须是连续的。 那么考虑当数组非常大的情况时, 在某一次扩容向系统申请双倍空间时, 内存可能已经无法提供如此大的连续空间。 此时链表的灵活性优势就体现出来了: 通过指针有效链接碎片内存空间, 也可以形成线性数据结构, 而不需要依赖于连续的内存空间。
无可否认的是, 链表节点除了包含值, 还需额外保存一个引用(指针)。因此在相同数据量下, 链表比数组占用更多的内存空间。 因此也就有了我们第一条tradeoff: 「总占用内存 Vs 内存灵活性」
数组和链表性能对比
数组和链表都旨在实现一个「线性结构」, 而为了达成共同的目的, 两者又似乎才用了完全相反的存储策略, 导致了他们在操作效率上呈现对立的特点。
| 数组 | 链表 | |
|---|---|---|
| 存储方式 | 连续内存空间 | 分散内存空间 |
| 容量 | 长度不可变(除非扩容) | 可灵活拓展, 无上限 |
| 内存效率 | 占用内存少, 且cache命中率高 | 相同条件下占用内存更多 |
| 访问元素(索引) | O(1) | O(N) |
| 查找元素 | O(N) | O(N) |
| 添加元素 | O(N) | O(1) |
| 删除元素 | O(N) | O(1) |
| 遍历所有元素 | O(N) | O(N) |
很显然, 因为离散的结构, 链表在元素的访问上远不如数组高效, 但是在增加和删除元素时, 也不需要如数组一般需要操作整个臃肿的内存区块, 来维持线性。 因此也就有了我们第二条tradeoff: 「插入/删除的性能 Vs 查询的性能」
拓展知识: 物理层次的Tradeoff
学习过数据库相关知识的其实不陌生, 计算机物理结构中, 缓存因为离CPU更近, 所以其读写效率远高于内存, 远远高于硬盘, 但是代价就是容量非常小, 而且价格非常贵, 故肯定是没有办法把大量数据都存到缓存里。 所以如果从某个数据结构中读取数据时, 恰巧这部分内容在缓存中, 那效率会高到可怕, 这被称为「缓存命中」「缓存命中」。
这也成了我们第三条tradeoff: 「缓存命中率 Vs 空间利用率」
在算法的性能评估时很少有人提到缓存的事情, 我认为是合理的, 因为(理论中)通过界算法消耗时间和空间的上界来评估算法本身的性能, 其实更加公平。 但也不可以否认一个事实, 「(实际应用中)物理结构在很大程度上决定了程序对内存和缓存的使用效率」, 进而影响算法程序的整体性能。
而数组和链表对缓存的利用效率也是不同的。
- 占用空间: 链表元素比数组元素占用空间更多，导致缓存中容纳的有效数据量更少。
- 缓存行: 链表数据分散在内存各处，而缓存是“按行加载”的，因此加载到无效数据的比例更高。
- 预取机制: 数组比链表的数据访问模式更具“可预测性”，即系统更容易猜出即将被加载的数据。
- 空间局部性: 数组被存储在集中的内存空间中，因此被加载数据附近的数据更有可能即将被访问。
总体而言, 从「物理结构」上的角度考虑, 数组会具有更高的「缓存命中率」, 因此数组在实际应用中的效率通常会优于链表。但是这并不意味着数组在什么情况下都比链表强, 大多数时候数组与链表的选择主要取决于前两条tradeoff, 以及特定的应用场景和需求 (之后「栈」的篇章会举例讲)。
链表类型
链表基本上可以分为3种类型:
- 单链表
- 双链表
- 循环链表
分别适合解决不同的问题。
单链表
就是我们常说的普通链表, 也是最早的版本。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点(head),将最后一个节点称为尾节点,尾节点指向空 (None) 。
双链表
与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表, 双向链表更具灵活性，可以朝两个方向遍历链表, 但相应地也需要占用更多的内存空间。
循环链表
如果我们令单向链表的尾节点指向头节点（首尾相接）, 则得到一个环形链表。在环形链表中, 任意节点都可以视作头节点。
链表典型应用
设计不同的链表显然是为了解决不同的问题, 下面罗列一些常见的应用。
单链表
- 「栈与队列」: 当插入和删除操作都在链表的一端进行时，它表现的特性为先进后出，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现的特性为先进先出，对应队列。
- 「哈希表」: 链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
- 「图」: 邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。
- 「React - Hook」: 在React源代码中是通过链表实现Hook这个核心特性的, 我猜测原因是因为Hook可以更高效的删除和增加, 而并不需要关注查询。
双链表
适用于需要快速查找前一个元素和后一个元素的场景。
- 「高级数据结构」: 比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
- 「浏览器历史」: 在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
- 「LRU 算法」: 在缓存淘汰(LRU)算法中, 我们需要快速找到最近最少使用的数据, 以及支持快速添加和删除节点。这时候使用双向链表就非常合适。
循环链表
适用于需要周期性操作的场景，比如操作系统的资源调度。
- 「时间片轮转调度算法」: 在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法, 它需要对一组进程进行循环。每个进程被赋予一个时间片, 当时间片用完时, CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
- 「数据缓冲区」: 在某些数据缓冲区的实现中, 也可能会使用环形链表。比如在音频、视频播放器中, 数据流可能会被分成多个缓冲块并放入一个环形链表, 以便实现无缝播放。
不难发现, 适合使用链表来实现的很多应用, 尤其是「循环链表」相关的, 如果替换成数组会很麻烦。因此在选择数据结构的时候, 最先考虑的一定是「具体的应用场景和需求」, 如果有多个备选数据结构的话, 然后才开始考虑性能的tradeoff。
刷题经验总结
| 编号 | 名称 | 难度 | 链表技巧 |
|---|---|---|---|
| 203 | 移除链表元素 | 简单 | 「虚拟头节点」 + 「原地操作」 |
| 707 | 设计链表 | 中等 | 「虚拟头节点」 + 「原地操作」 |
| 206 | 反转链表 | 简单 | 「虚拟头节点」+ (「递归」 or 「原地操作」 + 「双指针」) |
| 24 | 两两交换链表中的节点 | 中等 | 「虚拟头节点」 + 「原地操作」 + 「模拟 (会比较复杂)」 |
| 19 | 删除链表的倒数第N个节点 | 中等 | 「虚拟头节点」 + 「双指针」 |
| 160 | 链表相交 | 简单 | 「虚拟头节点」 + (「双指针」or 「哈希集合」) |
| 142 | 环形链表II | 中等 | 「虚拟头节点」 + (「双指针」 or 「哈希表」) + 「数学」(面试可能会问背后的数学逻辑) |
技巧:「虚拟头节点」
链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了头结点的尴尬, 因为头结点没有前一个节点了。
每次对应头结点的情况都要单独处理, 所以使用虚拟头结点的技巧, 就可以解决这个问题。
因为有了虚拟头节点后, 可以将链表有意义的部分整体可以统一处理。
# 虚拟头节点法模板
#
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
# 创建虚拟头部节点以简化删除过程
dummy_head = ListNode(next = head)
# 遍历列表并删除值为val的节点
current = dummy_head
while current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
return dummy_head.next