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

数组的一个特点就是连续的内存空间和相同类型的数据。所以数组可以快速随机访问，但是删除，插入操作变得低效。

计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数据中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data type_size

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

对于已经排序好的数组，使用二分法查找，时间复杂度为 O(log n)，而对于未排序的数组进行查找，时间复杂度是 O(n)。

插入

假设数组的长度为n，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，我们需要将第 k ~ n 部分的数据都顺序地往后挪一位。

时间复杂度分析

如果在数组的末尾插入元素，那就不需要移动数据了，这时的最好时间复杂度为O(1)。

如果在数组的开头插入元素，那就要将所有的元素依次往后挪一位，这时候最坏时间复杂度为O(n)。

因为每个位置插入的概率都是一样的，所以平均时间复杂度为O(n)。

 1+2+3+...+n    (n+1) * n     n+1
------------- = ---------- = -----
      n            2 * n       2

删除

如果数组的长度为n，我们需要删除第 k 个位置的数据，为了内存的连续性，我们需要将 k ~ n 部分的数据都往前挪一位。

时间复杂度分析

跟插入一样，如果删除数组的末尾元素，则最好情况时间复杂度为O(1)；如果删除开头的数据，则最坏的时间复杂度为O(n)；平均时间复杂度为O(n)。

越界问题

不同的语言的数组越界会有不同的处理。

C语言：

int main(int argc, char* argv[]) {
  int i = 0;
  int arr[3] = {0};
  for(; i <= 3; i++) {
    arr[i] = 0;
    printf("hello world\n");
  }
  return 0;
}

在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。所以 a[3] 也会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量 i 的内存地址，那么 a[3]=0 就相当于 i=0，所以就会导致代码的无限循环。

而像 Java 本身就会做越界检查，下面的 Java 代码，就会抛出 java.lang.ArrayIndexOutOfBoundsException。

int[] a = new int[3];
a[3] = 10;

更有甚者，像 JavaScript 中就没有越界错误，如果索引超出范围，则会直接引起数组大小的变化。

var arr = [1, 2, 3];
arr 5 = 'a';
arr;  // [1, 2, 3, undefined, 'a']

偏移

Q: 为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始？

因为从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移”。如果用 a 表示数组的首地址，a[0] 就是偏移为 0 的位置，也就是首地址，a[k] 就表示偏移 k 个 type_size 的位置。所以计算 a[k] 的内存地址，计算公式：

a[k]_address = base_address + k * type_size

如果数组从 1 开始计算，那么计算公式：

a[k]_address = base_address + (k - 1) * type_size

参考链接