Hello 算法第 4 章小结精读：数组、链表、列表与缓存的要点回顾与深度问答

2026-09-06 18:11:58作者：董斯意

本文是基于《Hello 算法》（hello-algo）仓库中第 4 章《数组与链表》小结的整理与扩写。该小结服务于全书的**数组与链表（Array & Linked List）**章节，将连续存储与分散存储、数组的随机访问、链表的高效增删、动态数组实现下的列表、以及内存与缓存对二者性能的差异影响等关键结论浓缩为"要点回顾"，并收集了十余个具有代表性的高频问题。跟随本文，读者可以快速复核本章全部核心知识点，并从仓库源码（Python / C 实现）中获得可运行、可验证的佐证，理解栈与堆分配、元素类型一致性、删除节点指针处理、O(1) 插入删除的真实前提、列表扩容与空间浪费，以及 Python 对象引用模型的底层原理。

一、章节目录与阅读定位

在仓库的英文版目录配置中，第 4 章由六个小节构成，本文对应其中的 4.5 Summary 部分：

4.1 Array（数组）
4.2 Linked List（链表）
4.3 List（列表）
4.4 Random-Access Memory and Cache（内存与缓存）
4.5 Summary（小结）
4.6 Exercises（练习）

因此，小结不仅是"复习题"，更是对前四节内容的结论性收束。下文先完整展开"要点回顾"，再逐题讲解"问答"部分，并在关键处对照仓库中的可运行代码进行验证。

二、要点回顾：核心结论的完整梳理

小结把全章压缩成一组相互印证的判断，它们构成了后续章节（栈、队列、二叉树、图等）的地基。

1. 数组与链表：互补的两种存储形态

数组与链表是两种最基础的数据结构，分别代表了数据在计算机内存中的两种存储方式：连续存储与分散存储，二者的优缺点互为补充。

数组支持随机访问且占用内存更少；但插入与删除元素效率低，且初始化后长度不可变。
链表通过修改引用（指针）实现高效的节点插入与删除，并可灵活调整长度；但节点访问效率低、内存占用更高。常见链表类型有单向链表、环形链表、双向链表。

从仓库实现可以看出这种"引用操作"的直观形态。以 Python 版链表操作为例，插入只需改写两处 next 引用，删除只需跳过被删节点：

def insert(n0: ListNode, P: ListNode):
    """在链表的节点 n0 之后插入节点 P"""
    n1 = n0.next
    P.next = n1
    n0.next = P

def remove(n0: ListNode):
    """删除链表的节点 n0 之后的首个节点"""
    if not n0.next:
        return
    # n0 -> P -> n1
    P = n0.next
    n1 = P.next
    n0.next = n1

而在 C 版链表实现中，删除节点后还需显式 free(P) 释放内存，体现了两种语言在内存管理上的差异。与之对应，Python 版数组操作与 C 版数组操作中的插入/删除都需要用循环把元素整体后移或前移，复杂度为 $O (n)$ ——这正是"数组插入删除低效"的代码级证据。

2. 列表：动态数组封装的产物

列表（List）是一种有序的元素集合，支持插入、删除、查找与修改，通常基于动态数组实现，既保留了数组的优势，又允许长度灵活调整。 很多语言标准库中的 list（Python）、ArrayList（Java）、vector（C++）、List（C#）都由动态数组实现，详见列表章节的论述。

"列表的出现极大提升了数组的实用性，但也可能浪费部分内存空间"——这是小结强调的一个副作用。仓库的 Python 版 MyList 自实现列表是绝佳的例证：构造时预分配 _capacity = 10 的底层数组并维护独立的 _size 记录当前元素数，同时把 _extend_ratio = 2 作为扩容倍数。这意味着在元素不足容量上限时，底层数组依然存在未被使用的"空位"，即空间浪费的来源。

3. 内存与缓存：为什么数组通常更快

程序运行时数据主要存放于内存中。数组的存储空间效率更高，链表的空间使用更灵活。缓存通过缓存行、预取、空间局部性与时间局部性等机制为 CPU 提供快速数据访问，显著提升程序执行效率。而 数组因缓存命中率更高，整体效率通常优于链表，因此选用数据结构时应结合具体需求与场景权衡。相关内容详见内存与缓存章节。

三、Q & A 精讲：十余个高频疑点的逐题拆解

Q1：数组存储在栈上还是在堆上，会影响时间效率与空间效率吗？

两种位置的数组都占据连续的内存空间，数据操作效率基本相同。差异来自栈与堆自身的特性：

分配与释放效率：栈是相对较小的内存，分配由编译器自动完成；堆相对更大、可在代码中动态分配，更容易产生碎片，因此堆上的分配与释放通常比栈慢。
大小限制：栈内存相对较小，堆的大小一般受可用内存限制，因此大数组更适合放在堆上。
灵活性：栈上数组的大小必须在编译期确定，而堆上数组的大小可在运行时动态决定。

仓库中的 C 代码为上述第三点提供了直观对照：array.c 的 main() 里既有编译期定长的栈数组 int arr[5]，也有通过 malloc 在运行时按需分配堆数组的 extend() 函数——这正是"C 语言数组长度不可变"这一结论的出处，也是后续理解动态数组（列表）为何能"动态扩容"的关键起点。

Q2：为什么数组要求元素类型相同，而链表没有这个强调？

链表由节点组成，节点之间通过引用（指针）相连，每个节点可以存放不同类型的数据（如 int、double、string、object 等）。

而 数组元素必须是同类型，才能用"偏移量"公式定位元素位置。若数组同时包含 int（4 字节）与 long（8 字节），数组中同时存在两种"元素大小"，以下公式将无法成立：

# 元素地址 = 数组首地址（首元素地址）+ 元素大小 × 元素索引

这解释了为什么诸如 Python 的 array 模块、C 的原生数组等"真数组"都需要同构元素；而由 ListNode 引用串联而成的链表天然支持异构，节点结构只负责持有引用，参见 Python 链表节点定义。

Q3：删除节点 `P` 后，是否必须把 `P.next` 置为 `None`？

不是必须的。 从链表的视角看，从头节点遍历到尾节点已不会再遇到 P，即 P 已从链表中摘除；此时 P 指向哪里都无关紧要，不会影响链表本身。

不过从不同角度存在取舍：从算法解题的角度，只要程序逻辑正确，指针保持连接即可；从标准库实现的角度，显式断开更安全、更清晰——如果不断开且被删节点未被正确回收，可能影响后继节点的回收。这一点在 C 语言的 removeItem 中体现得很典型：它将 P 从链上摘下后立即 free(P)，从根上规避了"悬挂引用"与回收问题。

Q4：链表插入/删除的时间复杂度是 $O (1)$ ，可插入和删除前都要花 $O (n)$ 查找，为什么不写 $O (n)$ ？

如果先查找再删除，总时间复杂度的确是 $O (n)$ 。 链表 $O (1)$ 插入删除的优势体现在需要"已知前驱节点"的场景中。

小结给出的典型应用是双端队列（deque）：维护始终指向头、尾节点的指针变量，每次在两端插入、删除均为 $O (1)$ ，这正是链表适合实现队列/双端队列的原因，可参见栈与队列章节中的 deque 讲解以及仓库中基于数组与基于链表实现的对照代码。

Q5："链表定义与存储方式"示意图中，浅蓝色指针节点占用一个内存地址，还是与节点值均分？

该示意图是定性表示，定量分析须结合具体情形：

不同类型的节点值占用空间不同，如 int、long、double 以及实例对象等。
指针变量占用内存大小取决于操作系统与编译环境，通常为 8 字节或 4 字节。

因此图中"指针域与数据域并置"的画法只用于说明逻辑结构，并不代表二者在实际内存中的占用比例相同。

Q6：在列表末尾追加元素总是 $O (1)$ 吗？

不总是。 当追加元素使长度超过容量时，列表必须先扩容：系统分配一块新内存，并把原列表所有元素搬移过去，此时时间复杂度变为 $O (n)$ 。

仓库的 MyList.add() 正是这一逻辑的实现：

def add(self, num: int):
    """在尾部添加元素"""
    # 元素数量超出容量时，触发扩容机制
    if self.size() == self.capacity():
        self.extend_capacity()
    self._arr[self._size] = num
    self._size += 1

其 extend_capacity() 新建长度为原容量 _extend_ratio 倍的新数组并整体拷贝——一次扩容的开销为 $O (n)$ 。这也是"均摊后追加仍近似 $O (1)$ ，但单次追加可能达到 $O (n)$ "的原因所在。

Q7："列表提升数组实用性却浪费内存"，浪费指 capacity、length、扩容系数等额外变量吗？

空间浪费主要有两方面：一是列表通常设置一个初始容量，我们可能无法完全利用；二是为避免频繁扩容，扩容一般按系数进行（如 ×1.5），结果会留下许多通常填不满的空位。

从源码结构看，这种"预留"策略体现得非常直接：MyList 初始化即分配 capacity = 10 的底层数组（_arr: list[int] = [0] * self._capacity），即使只加入 1 个元素，那 9 个空位也已占用内存；扩容时一次性翻倍（_extend_ratio = 2），同样带来预留空位。可见"容量 × 长度"（capacity vs size）正是开销的本质来源。

Q8：Python 中 `n = [1, 2, 3]` 的三个元素地址连续，但 `m = [2, 1, 3]` 各元素 id 不连续，还与 `n` 中相同，`m` 还算数组吗？

依然算。 可以这样理解：若把列表元素换成链表节点 n = [n1, n2, n3, n4, n5]，这 5 个节点对象通常也散落在内存各处；但给定列表索引，仍可在 $O (1)$ 内取得节点内存地址从而访问对应节点——因为数组存储的是对节点的引用，而非节点本身。

Python 与许多语言不同，数字被包装为对象，列表存储的不是数字本身而是对数字的引用。因此同一数字出现在两个列表中时 id 相同，这些数字的内存地址也不必连续。这实际上印证了前文要点：Python 的 list 本质是"对象引用的动态数组"，其底层连续存储的是引用，而非值本身。

Q9：C++ STL 已有 `std::list`（双向链表），为何算法书中不直接使用？

一方面，算法实现中通常优先用数组、仅在必要时用链表，主要有两点原因：

空间开销：每个元素需要额外两个指针（一个指向前驱、一个指向后继），std::list 通常比 std::vector 占用更多空间。
缓存不友好：数据不连续存放，std::list 的缓存利用率更低。总体而言 std::vector 性能更好。

另一方面，必须使用链表的场景主要是二叉树和图；栈与队列通常直接用语言提供的 stack、queue，而非链表。该结论与仓库中图、树的实现方式一致——例如图相关章节使用邻接链表结构存储顶点关系，正是链表"分散存储 + 灵活增删"特长的用武之地。

Q10：`res = [[0]] * n` 创建的是每个 `[0]` 都相互独立的二维列表吗？

不是。 该二维列表中所有 [0] 实际引用的是同一个对象，修改其中某个元素，会发现所有对应元素同步变化。

若希望二维列表中每个 [0] 相互独立，应使用 res = [[0] for _ in range(n)]：其原理是用列表推导初始化 $n$ 个彼此独立的 [0] 列表对象。

Q11：`res = [0] * n` 中每个整数 0 相互独立吗？

在本列表中，所有整数 0 都引用同一对象——这是因为 Python 对小整数（通常为 -5 到 256）采用缓存机制以最大化对象复用、提升性能。

尽管引用同一对象，每个元素仍可被独立修改：Python 整数是不可变对象，修改元素时只是让该元素改指另一个对象，而非改变原对象本身。但当元素是可变对象（如列表、字典、类实例）时，直接修改会改变对象自身，所有引用该对象的元素都会同步变化。这正是 Q10 中二维列表陷阱的根本成因，也是理解 Python 内存模型（引用 vs 值、可变 vs 不可变）必须厘清的一对概念。