数组

一、数组的本质

• 线性数据结构，物理存储、逻辑存储均连续，是相同数据类型元素的集合
• 最小单元：数组元素，通过下标（索引）定位

二、数组的类型

• 静态数组
  • 特点：声明时固定容量，运行中无法修改大小
  • 例子：C语言中直接声明的数组int arr[5];
• 动态数组
  • 特点：容量可动态扩容，底层仍基于静态数组实现
  • 例子：JavaScript的Array、Java的ArrayList
• 多维数组
  • 分类：二维数组（数组的数组）、三维及以上数组
  • 特点：逻辑上是表格/立体结构，物理上仍为连续存储

三、数组的核心操作

• 访问元素
  • 方式：通过下标直接访问，下标从0开始
  • 核心：根据下标计算内存地址，直接定位
• 插入元素
  • 分类：头部插入、尾部插入、指定位置插入
  • 核心：尾部插入（容量足够）仅需赋值；其他位置插入需移动后续元素
• 删除元素
  • 分类：删除头元素、删除尾元素、删除指定位置元素
  • 核心：尾部删除仅需修改长度；其他位置删除需移动后续元素填补空位
• 查找元素
  • 方式：顺序查找（遍历比对）、二分查找（有序数组）
  • 特点：有序数组可使用二分查找提升效率

四、数组的核心特性

• 访问效率：O(1)（下标直接定位，随机访问能力）
• 插入/删除效率：O(n)（非尾部操作需要移动元素）
• 内存特性：需预分配连续内存空间，可能存在空间浪费
• 适用场景：频繁查询、数据量固定/变化少、需要随机访问的场景