数据结构与算法之美：05 | 数组

如何实现随机访问

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

• 线性表（Linear List）：数据排成像一条线一样的结构，每个线性表上的数据最多只有前和后两个方向。除了数组，链表、队列、栈等也是线性表结构。
  
  相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为非线性表中，数据之间并不是简单的前后关系：
  
• 连续的内存空间和相同类型的数据
  线性表+连续的内存空间和相同类型的数据两个限制带来了随机访问的优点。这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

随机访问：根据下标随机访问，知道首地址以及下标就能计算下标对应元素的地址，顺便说一句，c++里面的vector,deque, array以及string也是能够随机访问的。

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

低效的“插入”和“删除”

容易理解，因为要保证内存数据的连续性。

对于插入操作：

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

如果数组中的数据是有序的，在某个位置 k 插入一个新的元素时，就必须按照上面的方法搬移 k 之后的数据。但如果数组数据没有规律，如果要将某个数据插入到第 k 个位置，为了避免大规模数据搬移，有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新元素直接放入第 k 个位置，这样在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)。

对于删除操作：

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

在某些特殊场景下，并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，可以先记录下已经删除的数据。每次删除操作并不是真正地搬移数据，只是记录数据已经被删除，数组没有更多空间存储数据时，再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

警惕数组越界

课后思考

二维数组内存寻址：

对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为：
address = base_address + ( i * n + j) * type_size