数组(Array)

定义

数组是一种把相同类型元素存放在连续内存空间中的线性数据结构，通过下标（索引）直接定位元素。大多数语言的数组下标从 0 开始。

原理

由于元素连续存放且大小固定，第 i 个元素的地址等于首地址加上 i 乘以单个元素字节数，因此可以在常数时间内随机访问。代价是插入和删除中间元素时，需要移动后续所有元素以保持连续性。静态数组容量固定，动态数组（如 C++ 的 vector、Java 的 ArrayList）在容量不足时按倍数扩容并整体搬迁。

复杂度

• 按下标访问/修改：O(1)
• 查找指定值：O(n)
• 尾部插入（动态数组均摊）：O(1)
• 中间插入/删除：O(n)
• 空间复杂度：O(n)

应用场景

• 需要频繁随机访问、读多写少的场景
• 作为哈希表、堆、动态规划表等更复杂结构的底层存储
• 矩阵、图像像素、缓冲区等天然连续的数据