数组 (Array)
数组是一种将相同类型的数据元素存储在连续内存空间中的基础数据结构。
1. 核心定义 (Definition)
数组是一种将相同类型的数据元素存储在连续内存空间中的基础数据结构。
每个元素都可以通过索引（通常是整数）直接访问
2. 结构特征 (Structural Characteristics)
- 逻辑结构：线性结构。数据元素之间存在一对一的前驱和后继关系（除了首尾元素）。
- 物理结构：顺序存储。利用物理地址的连续性来表示逻辑上的相邻关系。由于每个元素占用相同大小的内存，可以通过基地址和偏移量直接计算出任意元素的物理地址。
3. 基本操作与复杂度分析 (Operations & Complexity)
| 操作 (Operation) | 时间复杂度 (Time) | 空间复杂度 (Space) | 简要说明/原理 |
|---|---|---|---|
| 随机访问 (Access) | O(1) | O(1) | 核心特性。利用公式 寻址地址 = 基地址 + 索引 * 元素大小 直接定位，速度极快。 |
| 查找 (Search) | O(n) | O(1) | 无序数组需进行线性遍历；若是有序数组，可使用二分查找将时间优化至 O(log n) 。 |
| 插入 (Insertion) | O(n) | O(1) | 在末尾插入为 O(1) ；在头部或中间插入时，需将其后方所有元素向后平移，平均需要移动一半的元素。 |
| 删除 (Deletion) | O(n) | O(1) | 在末尾删除为 O(1) ；在头部或中间删除时，需将其后方所有元素向前平移填补空缺。 |
注：这里的时间复杂度为平均情况。对于定长数组，插入和删除操作如果超出容量，还需要考虑扩容（动态数组）带来的时间开销。
4. 优缺点评估 (Pros & Cons)
- 优势 (Advantages)：
- 支持随机访问：只需给定索引，即可在 O(1) 时间内读取或修改元素。
- CPU 缓存友好：由于内存连续，具有极佳的空间局部性（Spatial Locality），CPU 预读（Prefetching）命中率高，实际遍历速度非常快。
- 局限 (Disadvantages)：
- 插入/删除效率低：为了保持内存连续性，必须进行大量的数据搬移。
- 大小固定：静态数组在声明时必须确定大小，可能导致内存浪费（声明过大）或溢出（声明过小）。（注：动态数组通过倍增机制缓解了此问题，但扩容时仍有性能抖动）。
5. 知识拓扑 (Knowledge Topology)
- 上位概念：线性表 (Linear List)。
- 下位变体：
- 多维数组 (Multi-dimensional Array)
- 动态数组 (Dynamic Array / 可变长顺序表)
- 横向对比：与 链表 (Linked List) 互为镜像互补。数组重于“状态的随机访问”，链表重于“节点关系的动态修改”。
6. 典型应用场景 (Use Cases)
- 高频读取、极少插入/删除的场景（如查找表、静态配置数据）。
- 矩阵与多维数据的数学表示和计算。
- 作为更复杂数据结构的底层物理实现：例如 哈希表（Hash Table）、堆（Heap）、动态数组（std::vector / ArrayList）。
7. 关联与对比 (Relations & Comparisons)
- 对比 链表：
- 数组：内存连续，随机访问快 O(1) ，增删慢 O(n) ，大小固定。
- 链表：内存分散，随机访问慢 O(n) ，已知节点时的增删快 O(1) ，大小动态。
- 进阶变体：
- 动态数组 (Dynamic Array)：内部封装了自动扩容机制的数组。
- 多维数组 (Multi-dimensional Array)：本质仍是线性存储（行优先或列优先），用于映射多维逻辑关系。
8. 通往实践的接口 (Link to Practice)
Info: 具体代码实现、语言特性及刷题应用，请跳转至以下实践笔记：
- 底层实现探索：动态数组的扩容机制与均摊复杂度分析（计划补充）
- 多语言特性：
- 常见算法：双指针技巧在数组中的应用（计划补充）、滑动窗口理论与实践（计划补充）