数组 vs 链表 对比
两种基础线性数据结构的多维度对比分析
核心差异
| 维度 | 数组 (Array) | 链表 (Linked List) |
|---|---|---|
| 内存布局 | 连续内存空间 | 离散内存块，通过指针连接 |
| 随机访问 | $O(1)$ - 支持 | $O(N)$ - 不支持 |
| 头部插入/删除 | $O(N)$ - 需要搬移 | $O(1)$ - 只需修改指针 |
| 尾部插入/删除 | $O(1)$ 均摊（动态数组） | $O(N)$ 单链表 / $O(1)$ 双链表（有尾指针） |
| 中间插入/删除 | $O(N)$ - 需要搬移 | $O(N)$ 查找 + $O(1)$ 修改指针 |
| 空间开销 | 无额外开销（静态）/ 少量元信息（动态） | 每个节点需要额外指针空间 |
| 缓存友好性 | 高 - 连续内存，预取友好 | 低 - 跳跃访问，缓存不友好 |
适用场景
优先选择数组
- 频繁随机访问：需要通过索引快速访问元素
- 元素数量稳定：不会频繁增删
- 内存敏感：不希望额外的指针开销
- 缓存敏感：需要良好的局部性原理
优先选择链表
- 频繁插入删除：特别是头部操作
- 不确定大小：无法预估元素数量
- 不需要随机访问：顺序访问即可
- 实现其他数据结构：栈、队列、图邻接表等
时间复杂度对比
| 操作 | 数组 | 单链表 | 双链表 |
|---|---|---|---|
| 查/改（给定索引） | $O(1)$ | $O(N)$ | $O(N)$ |
| 查（给定值） | $O(N)$ | $O(N)$ | $O(N)$ |
| 头部插入/删除 | $O(N)$ | $O(1)$ | $O(1)$ |
| 尾部插入/删除 | $O(1)$ 均摊 | $O(N)$ * | $O(1)$ ** |
| 中间插入/删除 | $O(N)$ | $O(N)$ | $O(N)$ |
* 单链表尾部操作需要遍历到末尾 ** 双链表如果有尾指针，尾部操作是 O(1)