# 数组

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

这个定义里有几个关键词，下面分别解释一下：

# 线性表

『 线性表 』就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

它相对立的概念是『 非线性表 』，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

『 连续的内存空间和相同类型的数据 』

举例来说，声明一个长度为 10 的 int 类型数组。计算机给数组分配了一块连续内存空间 1000 ～ 1039，其中，内存块的首地址为 base_address = 1000。

计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。因为数组中每个元素在内存中都是连续的，所以这支持计算机对数组元素进行『 随机访问 』，也就是直接访问任何位置的任何元素。

当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址。然后通过地址去访问数据。在数组中，根据下标随机访问的时间复杂度为 O(1)。

Address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小。在这个例子里，数组中存储的是 int 类型数据，每个元素占 4 个字节。

但在数组中删除，或插入数据的操作是低效的。因为数组内的元素在内存中是连续的。插入，和删除一个元素会打破这种连续。所以就需要做很多数据搬移的工作。

🌰 例子：

假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k ～ n 这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢？

如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 $O(1)$ 。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 $O(n)$ 。因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为：

(1+2+…n)/n=O(n)

从数组存储的内存模型上来看，“下标” 最确切的定义应该是 “偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置，也就是首地址，a[k] 就表示偏移 k 个 type_size 的位置