个人学习站

深色模式

01 · 复杂度与数组、链表 ​

复杂度是这一模块的"度量尺"，数组和链表是"最基础的两个极端"。看懂它们的取舍，后面的所有结构都只是"在这两端之间做混合"。

一句话本质 ​

  • 复杂度：不看秒数，看"数据量翻倍时，耗时怎么变"。
  • 数组 vs 链表：一个把数据摆得紧凑、靠位置直接算地址；一个把数据撒开、靠指针一个个跳。

生活类比：连排座位 vs 寻宝纸条 ​

数组 = 电影院的连排座位

[A][B][C][D][E][F]
 0  1  2  3  4  5
  • 知道第 3 排在哪，走几步就到 > 随机访问 O(1)
  • 中间要插一个人 > 后面所有人往后挪 > 插入 O(n)
  • 座位是连着的，一排人坐一起，服务员一次能服务好几个 > 缓存友好

链表 = 寻宝游戏

[A|>]  [B|>]  [C|>]  [D|>]  [E|∅]
 ^      ^
 每张纸条写着下一张在哪
  • 想找第 4 张 > 必须从第 1 张开始，一张张跟 > 查找 O(n)
  • 想在 B 后面插一张 > 只需改两个指针 > 插入 O(1)（前提是你已经站在 B 那里）
  • 每张纸条藏在不同地方，跑来跑去很费腿 > 缓存不友好

核心机制 ​

一、复杂度：怎么"看出来" ​

O(1)     常数      哈希查找、数组按下标访问
O(log n) 对数      二分、平衡树查找      < 数据翻倍，只多一步
O(n)     线性      遍历、链表查找
O(n log n)         快排、归并           < 排序的下界
O(n²)    平方      双重循环、冒泡
O(2ⁿ)    指数      暴力枚举子集

看出来的三个口诀：

  1. 看到"每次砍一半"> log n（二分、树）
  2. 看到"单层循环"> n，"嵌套两层"> n²
  3. 看到"递归里每次分成两半各做一遍"> n log n（归并、快排）

只保留最高阶，忽略常数：3n² + 100n + 5 > O(n²)。因为 n 足够大时，低阶项和常数可以忽略。

但工程里常数很重要：同样是 O(n log n)，快排通常比归并快 2~3 倍（缓存友好、常数小）。所以面试答"复杂度相同"之后，补一句"实际快排更快，因为内存访问模式更好"，会很加分。

二、数组的地址计算（为什么是 O(1)） ​

数组起始地址 base = 0x1000，每个元素 4 字节
访问 a[3]：
  地址 = base + 3 × 4 = 0x1000 + 12 = 0x100C

一次乘加就出地址，不需要遍历。这就是 O(1) 的本质——不是"快"，是"计算量不随 n 增长"。

二维数组：a[i][j] 的地址 = base + (i × 列数 + j) × 元素大小。所以按行遍历（i 在外层）比按列遍历快得多——因为按列遍历会不断跳过整行，缓存命中率极低。

三、链表的几种形态 ​

单链表：    A > B > C > ∅            只能前进
双链表：    A ⇄ B ⇄ C > ∅            能前进能后退（多一个指针，空间翻倍）
循环链表：  A > B > C > A            尾接回头

哨兵节点（dummy head）：在头部加一个空节点，让"在头部插入"和"在中间插入"的代码统一，不用特判。这是写链表题的实用技巧。

四、数组 vs 链表：完整对比 ​

操作数组链表说明
按下标访问O(1)O(n)数组的核心优势
头部插入O(n)O(1)数组要整体后移
尾部插入O(1) 摊销O(1)数组扩容时是 O(n)，但摊销后 O(1)
中间插入O(n)O(1)**前提是已定位到位置，找位置本身是 O(n)
删除O(n)O(1)*同上
查找值O(n)O(n)都要遍历（除非有序）
内存开销小（无指针）大（每节点 1~2 个指针）
缓存友好好差这是实测差距的主要来源
扩容需重新分配 + 拷贝天然支持

"中间插入 O(1)"是个陷阱：你只知道"改指针是 O(1)"，但找到那个位置要 O(n)。所以链表插入的完整复杂度是 O(n)。面试常在这里挖坑。

五、为什么数组实测快这么多（接 OS 篇） ​

CPU 读内存不是按字节读，是按"缓存行"（通常 64 字节）读
  > 读 a[0] 时，a[1]~a[15] 也一起进了缓存
  > 遍历数组时，后面 15 次访问全部命中缓存

链表节点散落在堆上
  > 读 A 节点时，B 节点在完全不同的地址
  > 每次跳转都是一次缓存未命中 > 等内存（约 100 个时钟周期）

差距量化：
  数组遍历 1 亿个元素：约 0.1 秒
  链表遍历 1 亿个元素：约 1~2 秒（10 倍以上差距）
  虽然都是 O(n)

这就是"复杂度相同但实际差 10 倍"的经典案例。也是为什么 Java 的 ArrayList 在大多数场景下比 LinkedList 快——尽管教科书说链表插入快。

为什么这么设计 ​

反事实 1：如果数组不连续 ​

那就不叫数组了。"连续"是数组能 O(1) 访问的唯一前提——因为只有连续，才能用"基址 + 偏移"算出地址。一旦允许分散，就必须额外存映射关系（那就是哈希表或页表了）。

反事实 2：如果链表节点连续 ​

那它就成了数组（或者说"用数组实现的链表"）。链表的全部价值就在于"插入删除不影响其他元素的位置"——而这就要求节点不能连续（否则挪动一个会影响后面所有）。

反事实 3：如果数组不预留空间 ​

每次插入都重新分配 + 拷贝，插入 n 次就是 O(n²)。所以 ArrayList 会按 1.5 倍扩容，用"浪费一点空间"换"摊销 O(1)"。

摊销分析：扩容一次 O(n)，但平均到 n 次插入上，每次是 O(1)。这就是"摊销 O(1)"的含义。

面试怎么问 ​

Q：数组和链表的区别？

别只答"一个连续一个不连续"。要按操作答：随机访问数组 O(1)、链表 O(n)；插入删除链表理论上快但定位仍 O(n)；再加一句实测差距来自缓存局部性——这句是区分度所在。

Q：为什么数组随机访问是 O(1)？

因为地址可以算出来：base + index × size，一次乘加，与 n 无关。链表必须从头遍历，因为节点地址不连续、无法计算。

Q：链表插入是 O(1) 吗？

分两种说法："已知前驱节点时，插入本身 O(1)"；"从头找位置再插入是 O(n)"。完整答案要区分这两层，否则会被追问打脸。

Q：ArrayList 扩容为什么是 1.5 倍而不是 2 倍？

1.5 倍（Java）比 2 倍（C++ vector）更"温和"：2 倍容易导致"上一次扩容释放的空间 + 这次需要的空间"都装不下（因为总和超过可用内存），1.5 倍能让释放的空间被复用。这是经验性的工程取舍，不是理论最优。

追问链：

数组和链表区别？
  > 数组为什么 O(1)？（地址可计算）
    > 那链表为什么不行？（不连续，地址不可算）
      > 链表插入真的 O(1) 吗？（定位仍 O(n)）
        > 既然链表插入快，为什么实际更慢？（缓存不友好 + 指针开销）
          > 那什么时候真的该用链表？（频繁在已知位置插入删除，如 LRU 的双向链表）

和其他知识的连接 ​

  • < 来自 虚拟内存：让每个程序都以为自己独占一台机器：缓存行、TLB、内存布局，是"数组实测更快"的底层原因
  • > 影响 栈、队列与哈希表：栈和队列都可以用数组或链表实现，选哪个取决于操作模式
  • > 影响 树与堆：完全二叉树用数组存储（下标 i 的孩子是 2i+1 和 2i+2），这就是堆的实现方式
  • > 影响 索引与 B+ 树：B+ 树的叶子节点用链表串联，就是为了范围查询能顺序扫
  • > 影响 工程实践：Java ArrayList vs LinkedList、Redis 的 quicklist（链表套数组）、Kafka 的日志段（顺序写 + 稀疏索引）

自测 3 问 ​

Q1：遍历 1 亿个元素，数组和链表都是 O(n)，为什么实测差 10 倍？

点开看答案

因为CPU 缓存。

CPU 读内存按"缓存行"（64 字节）为单位。数组连续，读 a[0] 时会把 a[0] 到 a[15]（假设 int）一起载入缓存，后面 15 次访问全部命中，几乎不花时间。

链表节点分散在堆的各个角落，每次 node = node->next 都跳到新地址，大概率缓存未命中，必须去主存取（约 100 个时钟周期）。而且 CPU 的硬件预取器能识别"顺序访问"提前加载，对随机跳转完全无能为力。

所以：复杂度衡量的是"操作次数"，不衡量"每次操作多贵"。缓存未命中的代价，是复杂度分析里被省略的那个常数。

Q2：ArrayList 的 add 是 O(1) 还是 O(n)？

点开看答案

摊销 O(1)。

  • 大多数情况下直接放到末尾，O(1)。
  • 容量满了要扩容：申请 1.5 倍的新数组 + 拷贝全部元素，这一次是 O(n)。

但扩容不是每次都发生。假设从容量 1 开始翻倍，n 次插入总共拷贝约 2n 次，平均到每次是 O(1)。这叫摊销分析。

注意：摊销 O(1) 不代表"每次都很快"。偶尔会有一次明显的卡顿（扩容），这对延迟敏感的系统是问题——所以有时会预分配容量（new ArrayList<>(10000)）。

Q3：什么场景下链表真的比数组好？

点开看答案

必须同时满足两个条件：① 频繁在已知位置插入/删除；② 不需要随机访问。

典型场景：

  1. LRU 缓存：哈希表 + 双向链表。哈希表 O(1) 定位节点，链表 O(1) 把节点移到头部/删除。
  2. 操作系统的进程就绪队列：进程频繁进出队列，不需要按位置访问。
  3. 大对象的容器：元素本身很大（拷贝代价高），链表只移动指针。

反例（常见误用）：LinkedList 做"频繁随机插入"——每次插入前都要遍历找位置，实际比 ArrayList 慢得多。Java 官方文档自己都说 LinkedList 很少是最佳选择。

类比失效处 / 易错点 ​

  • "电影院座位"会让人以为数组插入永远慢。尾部追加是摊销 O(1)，只有中间插入才 O(n)。
  • "链表插入 O(1)"漏掉了"定位"这一步。完整代价是 O(n)，除非你已经持有前驱指针。
  • 复杂度不是"实际耗时"。同样的 O(n log n)，快排和归并可能差 2~3 倍；同样的 O(n)，数组和链表差 10 倍。
  • ArrayList 扩容 1.5 倍 vs vector 2 倍：没有绝对优劣，1.5 倍更容易复用已释放的内存，2 倍扩容次数更少。别把某一个说成"标准答案"。
  • 链表不一定省内存。每个节点多一个指针（8 字节），如果存的是 int（4 字节），空间开销直接翻 3 倍。

✅ 验收清单 ​

  • 能说出 O(1) / O(log n) / O(n) / O(n log n) / O(n²) 各自的典型场景
  • 能"看出来"复杂度：给一段代码能说出是 O(n) 还是 O(n²) 还是 O(n log n)
  • 能写出数组地址计算公式，并解释"为什么随机访问是 O(1)"
  • 能完整对比数组和链表的 6 种操作复杂度，并指出"链表插入 O(1)"的陷阱
  • 能用缓存行解释"为什么数组实测比链表快 10 倍"
  • 能解释摊销 O(1) 的含义，并说出预分配容量的意义
  • 能举出一个"链表真的比数组好"的场景，并说清原因
  • 合上书，用自己的话讲 3 分钟，中途不卡壳