数据结构之数组

数组的定义

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

线性表

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。

不仅是数组，链表、队列、栈等也是线性表结构。

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

随机访问

所谓随机访问，就是指根据下标随机访问数组元素。

当我们创建一个数组后，计算机会分配给它一块连续内存空间。假定内存块的首地址为 base_address = 1000。当计算机需要随机访问数组中的某个元素时，它会通过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

其中 i 是数组索引，data_type_size 表示数组中每个元素的大小（例如 int 类型数据的大小为 4 个字节）。

高效的查找操作

数组和链接最大的区别在于数组的查询效率高，链表的插入和删除效率高。但这里的查询效率高仅是指根据下标随机访问元素。

当我们根据下标随机访问数组元素时，查询的的时间复杂度为 O(1)。

而当我们要具体查找数组里的某个值时，时间复杂度取决于用什么算法（例如用二分查找查询排好序的数组，时间复杂度是 O(logn)）。

低效的插入和删除操作

插入操作

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

如果在末尾插入元素，则不需要移动数据，时间复杂度为 O(1)；如果在开头插入元素，时间复杂度为 O(n)。因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为 (1+2+...n)/n=O(n)。

优化：如果数组中的数据是有序的，就必须要这么操作。但如果数组中的数据是无序的，则可以取巧来优化：直接将第 k 位的数据搬移到数组的最后，把新的元素直接放入第 k 个位置。利用这种处理技巧，在特定场景下，在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)。这个处理思想在快排中也会用到。

删除操作

跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。

优化：在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率就会提高很多。
例如要依次删除三个元素，为了避免后续数据被搬移三次，可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。这也是 JVM 标记清除垃圾回收算法的核心思想。

支持动态扩容的容器

数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。当我们需要插入更多的元素时，需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。

我们平时用高级语言编写代码时，往往不需要关心底层的扩容逻辑，因为这些语言都提供了容器类（比如 Java 中的 ArrayList、Python 中的 list），它们将很多数组操作的细节封装起来（在插入、删除数据时的搬移操作），并且还支持动态扩容。

需要注意的是，因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建容器的时候事先指定数据大小。

对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

（完）