数组与链表
数组与链表是两种最基础的线性数据结构,前者利用连续内存实现 O(1) 随机访问,后者通过指针串联获得 O(1) 插入删除。理解两者差异,是后续学习哈希表、栈、树等结构的前提。
数组(连续存储)
数组在内存中占用一段连续地址空间,元素按下标线性排列。得益于地址计算 base + i * sizeof(T),按下标访问的时间复杂度为 O(1),这是数组最大的优势。
- 随机访问:
arr[i]时间O(1)。 - 插入/删除:需移动后续元素,平均
O(n)。 - 空间局部性:连续存储对 CPU 缓存友好,遍历效率高。
数组大小通常在创建时固定(静态数组),需要动态扩容时可使用 list(Python)或 vector(C++),其内部按倍数(如 1.5 倍或 2 倍)扩容,均摊时间 O(1)。
链表(链式存储)
链表由若干节点组成,每个节点包含数据域与指针域,通过指针将离散的内存块串联起来。链表不支持按下标访问,必须从头节点沿指针逐个遍历,时间 O(n)。
常见类型:
- 单链表:每个节点含
next指针,只能向后遍历。 - 双链表:每个节点含
prev与next,支持双向遍历,删除已知节点时为O(1)。 - 循环链表:尾节点指针指向头节点,适合实现环形缓冲区。
插入与删除只需修改相邻节点的指针,时间 O(1),但前提是已经定位到操作位置(定位本身仍需 O(n))。
核心操作对比
| 操作 | 数组 | 单链表 |
|---|---|---|
| 按下标访问 | O(1) | O(n) |
| 头部插入/删除 | O(n) | O(1) |
| 尾部插入/删除 | O(1) 均摊 | O(n) 到尾;带尾指针 O(1) |
| 中间插入/删除 | O(n) | 定位 O(n) + 修改 O(1) |
| 内存占用 | 紧凑,无额外开销 | 需存储指针,空间略高 |
适用场景
- 优先选数组:频繁随机访问、数据量基本固定、对缓存友好性敏感(如科学计算、图像处理)。
- 优先选链表:频繁在任意位置插入/删除、数据规模动态变化、无法预知最大长度(如 LRU 缓存、操作系统任务队列、哈希桶的冲突链)。
实际工程中常将两者结合,例如哈希表的桶使用数组,桶内冲突元素用链表存储(JDK 8 之前 HashMap 即采用此结构);又如 ArrayList 底层是数组,LinkedList 名字是链表,使用时需根据操作模式选择,切勿盲目认为链表一定更快。