线性表全景：数组与链表的本质与工程权衡

摘要

线性表是所有数据结构的起点，也是技术面试中覆盖最广、变体最多的考察领域。本文不追求堆砌定义，而是从存储模型的底层物理本质出发，深入推导数组与链表各自的时间复杂度为什么是那个形状，理解它们的设计权衡与适用场景，并为后续 38 道 LeetCode 题的解法建立统一的思维底座。

第 1 章什么是线性表，它解决了什么问题

1.1 从”一列数据”说起

在写代码之前，先想象一个场景：你需要管理一批学生的成绩，按照学号顺序依次存放。这批数据有一个共同特征——它们之间存在前驱与后继的关系：第 1 个元素之前没有元素，最后一个元素之后没有元素，中间任意一个元素都有且仅有一个前驱和一个后继。

这种”一对一”的关系，就是线性关系，对应的存储结构就叫线性表（Linear List）。

线性表的形式化定义

线性表是由 $n$ （ $n \geq 0$ ）个具有相同数据类型的元素组成的有限序列，记作 $L = (a_{1}, a_{2}, \dots, a_{n})$ 。当 $n = 0$ 时，称为空表。

线性表解决的根本问题是：如何在计算机中有序地存储和操作一批同类型数据。这是最基础的需求，几乎所有上层数据结构（栈、队列、哈希表等）都在某种意义上是线性表的特化形式。

1.2 线性表的两条实现路线

现实中，线性表有两种截然不同的物理实现策略：

路线一：把元素连续地摆放在内存中 → 得到数组（Array） 路线二：用指针把元素串联起来，允许分散存放 → 得到链表（Linked List）

这两条路线并不是”哪个更好”的问题，而是在不同约束下的不同设计权衡。理解它们各自好在哪、坏在哪，是解所有线性表面试题的底层逻辑。

第 2 章数组：连续内存的红利与代价

2.1 数组的物理模型

数组要求所有元素在内存中连续存放。假设数组 int[] a 的起始地址是 base，每个 int 占 4 字节，那么第 i 个元素的地址就是：

$addr (a [i]) = base + i \times 4$

这个公式非常关键，它意味着：给定下标 $i$ ，CPU 可以在 $O (1)$ 时间内直接计算出目标地址，然后一次内存访问就能拿到数据。 这就是数组随机访问的本质——不是什么魔法，而是一道简单的乘法。

内存地址:  0x100  0x104  0x108  0x10C  0x110
           ┌─────┬─────┬─────┬─────┬─────┐
数组内容:  │  5  │  3  │  8  │  1  │  9  │
           └─────┴─────┴─────┴─────┴─────┘
下标:        [0]   [1]   [2]   [3]   [4]

设计哲学：为什么下标从 0 开始？

很多语言（C、Java、Python）的数组下标都从 0 开始，这不是习惯问题，而是数学上最自然的选择。如果从 1 开始，地址公式就变成 base + (i-1) * size，多了一次减法。从 0 开始，公式直接是 base + i * size，CPU 执行更高效。Dijkstra 在 1982 年专门写过一篇短文论证这一点。

2.2 数组操作的复杂度分析

读取（Random Access）： $O (1)$

前面已经解释清楚了，就是一次地址计算 + 一次内存读取。不论数组有多大，时间恒定。

末尾追加（Append）：均摊 $O (1)$

往数组末尾塞一个元素，直接在 a[n] 的位置写数据即可，是 $O (1)$ 。

但这里有个前提：数组有剩余空间。如果数组满了怎么办？动态数组（如 Java 的 ArrayList、Python 的 list）会触发扩容（Resize）：申请一块更大的内存（通常是 2 倍），把所有旧数据复制过去，再插入新元素。这次扩容是 $O (n)$ 的。

虽然偶尔会有一次 $O (n)$ 的扩容，但由于扩容是指数级稀少的（每次扩容后要等很久才会再次满），用**均摊分析（Amortized Analysis）**可以证明：每次追加操作的平均代价仍然是 $O (1)$ 。

均摊分析的直觉

想象你每次追加元素时，“预存”一点代价用于未来的扩容。容量为 $n$ 的数组扩容到 $2 n$ ，需要复制 $n$ 个元素。但在此之前，你已经做了 $n$ 次追加，每次预存了”1 单位”代价，恰好凑够了这 $n$ 次扩容的开销。所以均摊下来每次追加仍是 $O (1)$ 。

中间插入/删除： $O (n)$

这是数组最大的软肋。在位置 i 插入一个新元素，需要把 a[i] 到 a[n-1] 的所有元素整体向后移动一格：

插入前: [5, 3, 8, 1, 9]
在位置 2 插入 7:
    需要把 [8, 1, 9] 整体右移一格
插入后: [5, 3, 7, 8, 1, 9]

最坏情况是插入到下标 0（头部），需要移动全部 $n$ 个元素，复杂度是 $O (n)$ 。删除同理，删掉位置 i 的元素后，需要把后面所有元素左移填坑。

搜索（线性扫描）： $O (n)$

如果数组无序，只能逐个遍历比较。如果有序，可以用二分查找压缩到 $O (lo g n)$ ，但这已经是特化场景了。

2.3 数组的 CPU 缓存亲和性

数组还有一个常常被忽视的优势：CPU 缓存友好性（Cache Locality）。

现代 CPU 有 L1/L2/L3 多级缓存。当 CPU 读取内存中某个地址的数据时，不只是读那一个字节，而是将附近一块连续内存（通常是 64 字节，称为一个 Cache Line）一起载入缓存。

对于连续存储的数组，访问 a[0] 时，a[1]、a[2]… 也跟着进了缓存。下一次访问 a[1] 时，直接从缓存命中，不需要再次访问主内存（缓存访问约 4ns，主内存访问约 100ns，差了 25 倍）。

链表的节点散落在内存各处，访问下一个节点几乎每次都是 Cache Miss，需要重新到主内存取数据。这是在处理大规模数据时，数组往往比链表快得多的深层原因。

第 3 章链表：指针串联的灵活与代价

3.1 链表的物理模型

链表中，每个元素被包装成一个节点（Node），节点除了存储数据本身，还存储了一个指向下一个节点的指针：

// 单链表节点的经典定义
class ListNode {
    int val;       // 数据域：存储实际值
    ListNode next; // 指针域：指向下一个节点，末尾节点的 next 为 null
}

链表的节点不需要在内存中连续，它们可以散落在堆内存的任意位置，只要通过 next 指针能找到下一个就够了。

内存中的样子（节点地址不连续）：

0x200: [val=5 | next→0x350]
0x350: [val=3 | next→0x180]
0x180: [val=8 | next→0x420]
0x420: [val=1 | next→null]

逻辑上的链表: 5 → 3 → 8 → 1 → null

链表有一个特殊角色：头节点指针（head），它存储第一个节点的地址。失去 head，整条链表就找不到了（会被垃圾回收掉）。

生产避坑：不要弄丢 head

在操作链表时，如果直接移动 head 指针而没有保存原始头节点，就会永久丢失链表的入口。这是初学者最常见的错误之一。标准做法是：始终保留一个指向原始头节点的引用，用额外的遍历指针来移动。

3.2 链表操作的复杂度分析

随机访问： $O (n)$

链表没有地址计算公式，要访问第 $i$ 个元素，只能从 head 开始，顺着 next 指针一步步数过去，走 $i$ 步。这就是链表随机访问慢的根本原因——不是因为指针”查找”慢，而是因为链表的存储结构根本不支持随机寻址。

头部插入/删除： $O (1)$

在链表头部插入一个新节点，只需要：

新建节点，令 newNode.next = head
令 head = newNode

两步操作，与链表长度无关，是真正的 $O (1)$ 。删除头节点同理：head = head.next，一步搞定。

任意位置插入/删除（已知前驱节点）： $O (1)$

这是链表最大的优势，也是它存在的核心理由。如果你已经持有了目标位置的前驱节点 prev，在其后插入一个节点只需要：

newNode.next = prev.next;  // 新节点的 next 指向原来的后继
prev.next = newNode;       // 前驱的 next 改为指向新节点

就是两次指针赋值， $O (1)$ 。这与数组插入形成鲜明对比——数组需要搬移所有后续元素，而链表只需要修改两个指针。

但实际中插入/删除往往是 $O (n)$

注意”已知前驱节点”这个前提。如果你只知道”在值为 k 的节点之前插入”，那就需要先遍历找到那个节点，遍历本身是 $O (n)$ 。所以面试题里说链表插入是 $O (1)$ ，是特指已定位到插入点之后的操作代价，不含查找代价。

3.3 单链表 vs 双向链表

本专栏聚焦单链表，因为 LeetCode 中 90% 的链表题都是单链表。但值得了解双向链表的存在：

特性	单链表	双向链表
节点额外空间	1 个指针（`next`）	2 个指针（`prev` + `next`）
向前遍历	不支持，必须从头重来	直接 `node.prev`
删除已知节点（无需前驱）	$O (n)$ （需找前驱）	$O (1)$
典型应用	大多数 LeetCode 题	LRU Cache、`java.util.LinkedList`

LRU Cache 必须用双向链表，原因就在于”删除任意已知节点”必须是 $O (1)$ ，单链表做不到。这是第 13 篇文章会深入讲解的内容。

第 4 章全面对比：何时选数组，何时选链表

4.1 时间复杂度横向对比

操作	数组（Array）	链表（Linked List）
随机读取 `a[i]`	$O (1)$ ✅	$O (n)$ ❌
头部插入	$O (n)$ （移位）	$O (1)$ ✅
尾部追加	均摊 $O (1)$ ✅	$O (n)$ （无尾指针）/ $O (1)$ （有尾指针）
中间插入（已知位置）	$O (n)$ （移位）	$O (1)$ （已知前驱）/ $O (n)$ （需找前驱）
删除中间元素	$O (n)$ （移位）	$O (1)$ （已知前驱）/ $O (n)$ （需找前驱）
按值搜索	$O (n)$ / 有序时 $O (lo g n)$	$O (n)$
内存占用	紧凑，无额外开销	每个节点需要存指针（8 字节/64位）

4.2 空间模型的差异

数组有一个隐性代价：需要预先声明容量，或在扩容时申请一块新的连续内存。如果你声明了容量为 100 的数组但只用了 10 个，剩下 90 个槽位就浪费了。如果需要更多，动态数组会扩容到 200，意味着在复制完成前内存中同时存在旧的 100 个和新的 200 个，峰值内存是 3 倍。

链表则是”用多少申请多少”，理论上没有浪费。但每个节点需要额外存储一个指针（64 位系统上是 8 字节），如果节点的数据本身很小（比如存一个 byte），指针的开销反而比数据本身大 8 倍。

4.3 工程场景下的选择依据

选数组的场景：

需要频繁按下标随机访问（如矩阵运算、滑动窗口）
数据规模相对固定，或可以接受均摊扩容代价
追求 CPU 缓存性能，数据量大时遍历性能优先
典型：C++ std::vector、Java ArrayList、Python list

选链表的场景：

频繁在任意位置插入/删除，且插入点已知（如文本编辑器的光标操作）
数据量不可预知，不想预分配内存
需要 $O (1)$ 的头部/尾部操作（如 LRU Cache）
典型：java.util.LinkedList（实际上极少有场景比 ArrayList 更优）

设计哲学：为什么现代工程中链表很少独立使用？

在实际工程里，ArrayList（动态数组）几乎统治了所有”序列”需求，LinkedList 反而是个冷门选择。根本原因是 CPU 缓存的力量。现代 CPU 的 L1 缓存命中速度比内存快 25-50 倍。数组由于 Cache Locality，即使某些操作理论复杂度高，实测性能往往碾压链表。

但在面试中，链表题占了相当大的比重，原因是它考察的是指针操作能力和边界条件处理，是检验候选人基本功的有效工具。理解这一点有助于你在刷题时抓住考点。

第 5 章面试中的线性表解题思维框架

这一章建立你后续刷题的通用思维模式。不同的题目表面形式各异，但底层逻辑高度收敛。

5.1 数组题的核心模式

模式一：双指针（Two Pointers）

绝大多数数组的原地修改题，本质都是双指针：用一个”慢指针”标记”可写入位置”，用一个”快指针”扫描数组。

场景：Remove Duplicates from Sorted Array
慢指针 slow：下一个可以被写入的位置
快指针 fast：当前扫描到的元素

[1, 1, 2, 3, 3]
 s                 fast=0: a[fast]=1，写到 a[slow]，slow++, fast++
    s              fast=1: a[fast]=1，和前面相同，fast++（不写）
    s              fast=2: a[fast]=2，写到 a[slow]，slow++, fast++
       s           fast=3: a[fast]=3，写到 a[slow]，slow++, fast++
          s        fast=4: a[fast]=3，和前面相同，fast++（不写）
结果: [1, 2, 3, ...]，前 slow 个元素有效

模式二：二分搜索（Binary Search）

处理有序数组时，优先考虑是否可以用二分。二分的关键不是”找到一个值”，而是确定不变量（Invariant）：在每次迭代中，明确哪半部分不可能是答案，从而安全地收缩搜索区间。二分的边界条件（< vs <=、mid+1 vs mid）是面试的高频失误点，需要用一套统一的模板来规避。

模式三：哈希表辅助（Hash Map）

当需要在 $O (1)$ 时间内查询”某个值是否存在”或”某个值的下标”时，用哈希表以空间换时间。Two Sum 是最典型的例子。

模式四：贪心扫描

有些题目可以通过一次或两次线性扫描，在每一步做出当前最优决策来得到全局最优解。Gas Station、Trapping Rain Water 都属于这一类。

5.2 链表题的核心模式

模式一：哑节点（Dummy Node / Sentinel Node）

链表题最常见的边界问题是”头节点需要被删除或修改”。此时引入一个虚拟的哑节点 dummy，令 dummy.next = head，操作完成后返回 dummy.next，可以统一对头节点和非头节点的处理逻辑，消除大量 if (head == null) 的特判代码。

ListNode dummy = new ListNode(0);  // 哑节点，值无所谓
dummy.next = head;
// ... 所有操作都通过 dummy 或 dummy.next 进行
return dummy.next;  // 返回真正的头节点

模式二：快慢双指针（Fast & Slow Pointers）

用两个速度不同的指针在链表上移动：

找链表中点：慢指针每次走 1 步，快指针每次走 2 步，快指针到末尾时慢指针在中点
找倒数第 k 个节点：快指针先走 k 步，然后快慢同步，快指针到末尾时慢指针在倒数第 k 个
检测环：如果有环，快指针终将追上慢指针（Floyd 判圈算法）

模式三：迭代反转（Iterative Reversal）

反转链表是链表题的基本功，迭代做法用三个指针 prev、curr、next，每次将 curr.next 指向 prev，然后整体向前推进。这个范式在 Reverse Linked List II、k-Group 反转等变体中反复出现。

模式四：分拆再合并

遇到复杂链表操作（Reorder List、Merge Sorted Lists），往往可以拆分成几个子问题：找中点、反转后半段、合并两个链表，逐个击破。

5.3 复杂度分析的习惯

面试时，解完题后主动说出时间复杂度和空间复杂度，体现工程素养。分析技巧：

时间复杂度：数清楚每个元素/节点被访问了几次。每次访问是 $O (1)$ 的话， $n$ 个元素访问 $k$ 次就是 $O (kn) = O (n)$ （ $k$ 是常数时）
空间复杂度：区分”原地（in-place）算法”（只用 $O (1)$ 额外空间）和需要额外哈希表/数组的 $O (n)$ 方案。面试官常问”能否用 $O (1)$ 空间实现？“

第 6 章 Java 中的线性表实现细节（面试备查）

6.1 数组相关

Java 中的原生数组是固定长度的：

int[] a = new int[10];  // 长度固定为 10，不可扩容

动态数组用 ArrayList：

List<Integer> list = new ArrayList<>();  // 初始容量 10
list.add(1);  // 均摊 O(1)
list.get(0);  // O(1)
list.remove(0);  // O(n)，需要移位

ArrayList 的扩容策略：新容量 = 旧容量 × 1.5（通过位运算 oldCapacity + (oldCapacity >> 1) 实现）。这比 2 倍扩容更节省内存，但在极高频追加场景下扩容次数略多。

6.2 链表相关

LeetCode 链表题使用的节点定义（Java）：

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

这是一个标准的单链表节点，面试时不需要自己定义，题目会提供。

6.3 本专栏的代码风格约定

为了在面试场景中写出简洁、可读的代码，本专栏代码遵循以下约定：

变量命名：单链表遍历指针统一用 cur（current），前驱用 prev，快慢指针用 fast/slow
不追求极致压缩代码行数，优先可读性和逻辑清晰度
每道题先讲思路推导，再给出代码，代码附关键注释
Python 用户：本专栏以 Java 为主，但所有算法逻辑是语言无关的，Python 版本仅在思路上有微小差异（如 Python 没有整数溢出问题）

第 7 章读完本篇后，你应该已经清楚的问题

在进入具体题目之前，用几个问题检查一下自己的理解：

为什么数组随机访问是 $O (1)$ ？ 不是”因为有下标”，而是因为连续内存 + 地址公式允许直接计算。
为什么数组中间插入是 $O (n)$ ？ 不是因为”要找到位置”，而是因为找到位置之后还要移动后面所有元素。
为什么链表随机访问是 $O (n)$ ？ 不是因为”慢”，而是因为链表的存储结构物理上就不支持随机寻址，只能顺序遍历。
链表插入/删除真的是 $O (1)$ 吗？ 有条件的：必须已知插入位置的前驱节点。如果还需要先遍历查找，那整体是 $O (n)$ 。
哑节点有什么用？ 消除头节点的特殊情况，让代码逻辑统一，减少 if 判断和 bug。
数组和链表，面试中谁更重要？ 两者同等重要，但考察的能力不同：数组考察边界处理和索引控制，链表考察指针操作和多步骤逻辑推进。

下一篇预告

02 数组双指针：原地修改数组的核心范式将进入第一个具体题目模块，深入讲解”Remove Duplicates from Sorted Array”系列和”Remove Element”——这三道题是数组原地操作的经典模板，也是双指针范式最清晰的呈现。我们会从”为什么不能开一个新数组”的约束出发，推导出双指针的必然性，而不是直接告诉你”用双指针”。

汀的知识碎片

文章导航

01 线性表全景：数组与链表的本质与工程权衡

线性表全景：数组与链表的本质与工程权衡

摘要

第 1 章什么是线性表，它解决了什么问题

1.1 从”一列数据”说起

1.2 线性表的两条实现路线

第 2 章数组：连续内存的红利与代价

2.1 数组的物理模型

2.2 数组操作的复杂度分析

2.3 数组的 CPU 缓存亲和性

第 3 章链表：指针串联的灵活与代价

3.1 链表的物理模型

3.2 链表操作的复杂度分析

3.3 单链表 vs 双向链表

第 4 章全面对比：何时选数组，何时选链表

4.1 时间复杂度横向对比

4.2 空间模型的差异

4.3 工程场景下的选择依据

第 5 章面试中的线性表解题思维框架

5.1 数组题的核心模式

5.2 链表题的核心模式

5.3 复杂度分析的习惯

第 6 章 Java 中的线性表实现细节（面试备查）

6.1 数组相关

6.2 链表相关

6.3 本专栏的代码风格约定

第 7 章读完本篇后，你应该已经清楚的问题

下一篇预告

On this page

汀的知识碎片

文章导航

01 线性表全景：数组与链表的本质与工程权衡

线性表全景：数组与链表的本质与工程权衡

摘要

第 1 章 什么是线性表，它解决了什么问题

1.1 从”一列数据”说起

1.2 线性表的两条实现路线

第 2 章 数组：连续内存的红利与代价

2.1 数组的物理模型

2.2 数组操作的复杂度分析

2.3 数组的 CPU 缓存亲和性

第 3 章 链表：指针串联的灵活与代价

3.1 链表的物理模型

3.2 链表操作的复杂度分析

3.3 单链表 vs 双向链表

第 4 章 全面对比：何时选数组，何时选链表

4.1 时间复杂度横向对比

4.2 空间模型的差异

4.3 工程场景下的选择依据

第 5 章 面试中的线性表解题思维框架

5.1 数组题的核心模式

5.2 链表题的核心模式

5.3 复杂度分析的习惯

第 6 章 Java 中的线性表实现细节（面试备查）

6.1 数组相关

6.2 链表相关

6.3 本专栏的代码风格约定

第 7 章 读完本篇后，你应该已经清楚的问题

下一篇预告

On this page

第 1 章什么是线性表，它解决了什么问题

第 2 章数组：连续内存的红利与代价

第 3 章链表：指针串联的灵活与代价

第 4 章全面对比：何时选数组，何时选链表

第 5 章面试中的线性表解题思维框架

第 7 章读完本篇后，你应该已经清楚的问题