数组

定义

数组（Array）是一种顺序存储结构数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

内存中的组织形式

数组的内存空间是一个整体，也就是说，数组中相邻元素之间的内存地址是紧密相林，不留缝隙的。

基于这种特性，可以利用公式快速地访问数组中的各个元素，即$LOC(i)=LOC(0)+i\ast L;$，换句话说，知道了数组第0个元素的地址，可以马上($O(1)$)得到目标位置元素的地址。

操作

查询和修改速度快，插入和删除速度慢

查询

• 时间复杂度O(1)
• 直接就寻址找到了

修改

• 时间复杂度O(1)
• 直接寻址找到目标位置后修改对应的值

插入

• 时间复杂度$O(N)$
• 插入到特定位置后，该位置后面的所有元素需要向后移动一位

删除

• 时间复杂度$O(N)$
• 删除某一个位置的元素后，该位置后面的所有元素需要向前补位。

当数组空间不够时

前面提到，数组在创建的时候是预先分配一整块内存空间的。

如果数组满了之后继续进行插入操作，那么计算机会执行下面的两种操作之一：

1. 数组直接原地扩充两倍（内存足够），然后执行新的插入操作
2. 内存不够数组直接原地扩充两倍，开辟一个新的内存空间，该内存空间能够存下两倍长度的原数组，后将原数组复制到新的空间中，继续完成插入操作。

以上两种的时间复杂度都是$O(N)$

特点

• 对数组中存储的数据做插入和删除操作，算法效率非常差；做查询和修改操作非常好。