链表（一）基础与数组对比

p3（17 分钟）、p4（12 分钟）

从内存讲起#

用一个「程序员阿尔伯特与内存管理器」的故事讲数组的局限。

内存模型约定#

把内存从左往右水平绘制，每格 1 字节，地址随向右递增（200 → 201 → 202 …）。

自上而下还是从左到右关系不大，都只是看待内存的逻辑方式。

故事里的具体数值（全课地址演算的基准）#

对象	内存分配
`int X`	4 字节（典型架构 int = 4 字节），变量 X 在地址 217
`int A[4]`	数组总是一段连续内存，分配起始地址 201 到结束地址 216
访问 `A[3]`	其地址 = 213

「一块内存的地址 = 该内存块中第一个字节的地址。」

访问 A[3] 的地址是由「内存块起始地址 + 位置」算出来的，所以访问任意元素时间恒定，与数组规模无关。

想加第 5 个元素 → 请求扩展同一内存块 → 内存管理器拒绝（旁边已被其他变量占用）。只能新建内存块 + 复制 + 释放旧块。

结论：数组要么浪费未使用部分，要么再次新建 + 复制。

链表的核心思想#

不再要一大片连续区域，而是一次只申请一个元素所需的内存。

四个整数的列表分别申请：

因为是分别提出请求，得到的内存也许挨着、也许不挨着，更大的可能性是得不到相邻的内存位置。所以需要额外信息把这些块连接起来。

节点结构#

每块里设两部分：

1
一部分存数据（值）
2
另一部分存「下一块的地址」

链接字段填法：

节点	链接字段
204 块	存 217
217 块	存 232
232 块	存 242
242 块（最后一块）	填 0

为什么填 0：零是无效地址，零可被用来标记这是列表的末尾。

C 语言定义#

1
struct node {
2
    int data;
3
    struct node *link;    /* 也可叫 next */
4
};

内存占用：int 4 字节 + 指针 4 字节 = 每个节点 8 字节。

这块 8 字节空间称为一个节点。

逻辑视图#

1
6 ──→ 5 ──→ 4 ──→ 2 ──→ NULL

节点互相连接但不连续
第一个节点称头节点
关于链表我们始终保存的唯一信息，就是头节点的地址
最后一个节点的地址字段为空 / 0

遍历方式#

只能从头部开始，问第一个「下一个的地址」，再问第二个……

这就像玩寻宝游戏：先找第一个人拿第二个人的地址，再去第二个人拿第三个人的地址。

插入示例#

在末尾加数字 3：

1
① 先单独创建节点（3 @ 252）
2
② 把 252 填进「值为 2 的节点」的地址部分
3
③ 3 这个节点的地址部分置为空

数组 vs 链表#

开篇结论：不存在一种数据结构比另一种更好。取决于最常见的操作是什么、数据规模有多大。

访问元素的开销#

数组：恒定时间。

1
地址(i) = base + i × 每个元素字节数

具体演算：int 数组，base = 200，int 占 4 字节：

1
地址(i) = 200 + 4i
2
索引 0  →  200
3
索引 6  →  200 + 6×4 = 224

时间复杂度 O(1)。

链表：数据不在连续内存，唯一掌握的信息是首节点地址。

要访问某位置必须从头逐个走。最坏要遍历全部节点，平均会遍历 N/2 个元素 → 平均情况 O(n)。

结论：数组得分远超链表。若需求是频繁按位置访问，无疑数组更佳。

内存需求#

数组：创建前必须知道大小，大小固定。常见做法是建「足够大」的数组，于是部分位置空置，那里会有垃圾值。

1
7 个整数的数组里只存了 3 个整数，其余 4 个位置未使用
2
7 个整数的数组 = 7 × 4 = 28 字节

链表：不存在未使用的内存（一次只为一个节点申请），但指针变量带来的额外内存需求不可忽视。

1
3 节点链表 = 8 × 3 = 24 字节
2
再加一个元素：数组只多用 1 个位置（+4 字节）
3
              链表要多建 1 个节点（+8 字节）→ 32 字节

数据部分越大，链表越占优：

场景	数组	链表
数据是 int（4 字节），7 个元素	28 字节	3 节点 24 字节 / 4 节点 32 字节
数据是 16 字节的复杂类型，7 个元素	112 字节	4 节点 80 字节

如果列表的数据部分占用大量内存，链表肯定消耗更少的内存；否则取决于我们选择何种策略、以及保留多少未使用的数组空间。

内存碎片化#

数组要求一整块连续内存，想创建非常大数组时可能根本拿不到一大块可用内存。

链表可以以多个小块形式存在并可用。

这或许是一种罕见现象，但确实是一种可能性，也是链表得分之处。

数组的额外成本：大小固定，一旦填满就必须新建更大数组 + 复制，这也是链表不存在的一项成本。

插入一个元素的成本（三种情形）#

情形	数组	链表
开头插入	每个元素朝高索引移一位 → O(n)	创建新节点 + 调整头指针和新节点链接，不依赖列表大小 → O(1)
末尾插入	未满 O(1)；已满要新建数组并复制全部 → O(n)	要遍历整个链表再创建节点、调整链接 → O(n)
中间第 i 个位置	平均要移 N/2 个元素 → O(n)	也要遍历到该位置（虽然不用移动元素）→ 平均 O(n)

最容易写反的是「末尾插入」：

1
数组末尾：未满 O(1)   ← 数组快
2
链表末尾：O(n)        ← 链表慢（要走到尾巴）

删除一个元素同样存在这三种情形，复杂度也相同。

哪个更容易实现#

数组显然容易得多。

链表的实现尤其在 C/C++ 中更容易出现段错误（segfault）和内存泄漏，处理链表要格外小心。

三个维度的总结#

	数组	链表
访问元素	O(1) ✓	O(n)
内存效率（小数据）	可能浪费	无浪费但有指针开销
内存效率（大数据）	浪费多	✓ 占优
内存碎片	需要连续大块	✓ 可用小块
开头插入	O(n)	O(1) ✓
末尾插入	未满 O(1) ✓ / 满 O(n)	O(n)
中间插入	O(n)	O(n)
实现难度	✓ 简单	容易段错误 / 内存泄漏

坑#

「链表插入是 O(1)」是错的。这里的插入是 O(n)，因为要遍历到特定位置；定位是 O(n)，链接调整本身不费时。只有头部插入才是 O(1)。
末尾插入：数组未满 O(1)，链表 O(n)，这两个最容易写反。
指针的额外内存不可忽视，小数据时链表反而更费内存。
NULL 就是地址 0；链表唯一的标识是头节点地址，丢了头指针整条链就找不回来了。
链表在 C/C++ 里更容易段错误和内存泄漏，不是「更高级所以更好」。