数组与链表

数组和链表的理论基础与对比

一、数组（Array）

1. 基本概念
   • 连续的内存空间，存储相同类型元素。
   • 通过索引直接访问元素（时间复杂度 O(1)）。
   • 大小固定，需预分配内存；扩容需重新分配内存并拷贝数据。
2. 核心操作复杂度
   • 访问：O(1)（随机访问）
   • 插入/删除：O(n)（需移动元素）
   • 尾部插入/删除：O(1)（若无需扩容）
3. 内存分配
   • 需要连续内存块，可能因空间不足导致扩容失败。
   • 缓存友好（局部性原理，预加载相邻数据）。
4. 典型应用
   • 需频繁随机访问的场景（如矩阵、排序后的数据）。
   • 数据量固定或变化较少的场景。

---

二、链表（Linked List）

1. 基本概念
   • 由节点（Node）组成，每个节点包含数据和指向下一个节点的指针。
   • 内存非连续，动态分配节点。
   • 常见类型：单链表、双向链表、循环链表。
2. 核心操作复杂度
   • 访问：O(n)（需从头遍历）
   • 插入/删除：O(1)（若已知操作位置的前驱节点）
   • 头/尾操作：O(1)（双向链表尾部操作更快）
3. 内存分配
   • 动态分配，无需连续内存，空间利用率灵活。
   • 缓存不友好（节点分散，预加载效率低）。
4. 典型应用
   • 频繁插入/删除的场景（如队列、栈、哈希表冲突链）。
   • 数据量动态变化（如 LRU 缓存淘汰算法）。

---

三、对比总结

| 特性 | 数组 | 链表 | |——————|———————————–|———————————–| | 内存连续性 | 连续内存 | 非连续内存 | | 访问速度 | O(1)（随机访问） | O(n)（顺序访问） | | 插入/删除 | O(n)（需移动元素） | O(1)（已知前驱节点时） | | 内存分配 | 预分配固定大小，可能浪费空间 | 动态分配，按需扩展 | | 缓存友好性 | 高（局部性原理） | 低（节点分散） | | 适用场景 | 频繁查询、数据量固定 | 频繁增删、数据量动态变化 |

---

四、选择建议

1. 选数组：需快速随机访问、数据量稳定、内存空间充足。
2. 选链表：需频繁增删、数据规模不确定、内存碎片化场景。

通过理解两者的底层逻辑，可在不同场景中选择更优的数据结构。