基本概念

数组：

  • 是一种线性表数据结构。
  • 用连续的内存空间存储同类型的数据。
  • 拥有随机访问的特性（可直接通过下标访问）。很适合查找操作。
  • 插入、删除数据的效率低（操作需要大量的数据搬移）。

线性表与非线性表

线性表

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。
链表、队列、栈等也是线性表结构。
image.png

非线性表

与线性表相对的概念，例如二叉树、堆、图等。在非线性表中，数据之间不是简单的前后管理。
image.png

随机访问

由于数组的线性表、连续内存空间存储同类数据这两个特点。数组拥有了随机访问的特性。

随机访问 - 概念

首先了解下什么是随机访问和非随机访问：

  • 随机访问：不需要按顺序访问，可以直接通过下标访问。
  • 非随机访问：访问第n个数据时，必须先访问前n-1个数据。如链表。

    随机访问 - 数组如何实现随机访问

    我们使用一个 长度为10 的数组 a 作为示例：
    image.png
    计算机给数组 a 分配了一块连续的内存空间： 1000~1039
    其中，内存块的首地址为 base_address = 1000

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

  1. a[i]_address = base_address + i * data_type_size

data_type_size 表示数组中每个元素的大小，此处存储的为 int 类型，因此大小为 4 个字节。

例如我们查找 a[1] 时，通过公式得出：
a[1]_address = 1000 + 1 * 4 = 1004
通过上图即可看出就是 a[1] 所在的内存地址。

随机访问 - 时间复杂度

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1) 。
但查找一个随机的元素，时间复杂度为 O(logn)，即便用二分查找也是如此。

低效的插入与删除

插入操作

有序数组的插入

在一个有序的数组中，假设数组长度为 n，将一个数据插入到数组中的第 k 个位置。
为了将第 k 个位置腾出，我们需要将第 k~n 的元素按顺序后移一位，此时的时间复杂度为：

最好时间复杂度（在最后一位插入）：O(1)
最坏时间复杂度（在第一位插入）：O(n)
平均时间复杂度：(1+2+...+n) / n ，即 O(n)

乱序数组的插入

若数组中的数据没有规律，仅当做一个存储数据的集合，还有个简单的方法：
将第 k 位的数据搬移至数组最后，将新元素放入位置 k 中。

例如数组 a[10] 存储了如下 5 个元素：a、b、c、d、e
要将 x 插入至第三个元素，仅需将 c 放至 a[5]，a[2] 赋值为 x：
image.png
最后数组元素如上：a、b、x、d、e、c
在特定场景下使用该技巧，则插入的时间复杂度就降为：O(1)

删除操作

假设要删除第 k 个位置的数据，为保证内存连续性，需要搬移数据。

最好时间复杂度（删除最后一位）：O(1)
最坏时间复杂度（删除第一位）：O(n)
平均时间复杂度：O(n)

但我们可以将多次的删除操作集中执行，效率就能提高很多：
数组 a 中存储了 8 个元素：a、b、c、d、e、f、g、h，现在一次删除 a、b、c 三个元素。
image.png
为避免后续的元素被连续搬移三次，我们可以先记录下已删除的数据。每次的操作不真正的搬移数据，仅记录数据已被删除，当数组没有更多存储空间时，再真正执行删除操作。减少删除导致的数据搬移。

这也是 标记清除垃圾回收算法 的核心思想。

数组的访问越界

首先分析如下代码：

  1. int main(int argc, char* argv[]){
  2.     int i = 0;
  3.     int arr[3] = {0};
  4.     for(; i<=3; i++){
  5.         arr[i] = 0;
  6.         printf("hello\n");
  7.     }
  8.     return 0;
  9. }

运行结果并非打印三行 “hello”，而是会无限打印，这是为何？

在C语言中，除了访问受限的内存，所有的内存空间都能自由访问。
根据前面的数组寻址公式，a[3] 被定位到某块不属于数组的内存地址。刚好该地址为 i 的内存地址。
那么 a[3]=0 就相当于 i=0，因此导致死循环。

容器

数组本身在定义时需要预先指定大小（因为需要分配连续的内存空间）。

当我们给一个大小为 10 的数组存储第 11 个数据时，会进行如下操作：

  • 重新分配一个更大的空间
  • 将原来的数据复制进新的空间
  • 将新的数据插入

但在其他语言如 Java 中，就可以使用 ArrayList 容器，都支持动态扩容，还有很多数组操作的封装。
但是由于扩容、内存申请、数据搬移较耗时，因此在创建时最好还是事先指定数据大小。

在平时的业务开发中，可以直接使用编程语言提供的容器类。
但若涉及到特别底层的开发，直接使用数组可能会更合适。

为何数组从 0 开始？

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

  • 下标表示的是 当前数据内存地址 相对于 内存首地址 的 偏移量。
  • 若从 1 开始，则每次寻找内存地址都会 多一次 减法运算。
  • C 语言设计者使用 0 计算，之后的语言为了减少新的学习成本等。

下标表示内存地址偏移量：
可以通过上述随机访问的例子得知公式：
a[i]_address = base_address + i * type_size

当访问 a[0] 时，即 i=0。那么 a[0] 的访问地址就为 1000 + 0*4 = 1000 。
当访问 a[1] 时，即 i=1。那么 a[1] 的访问地址就为 1000 + 1*4 = 1004 。

所以，“下标” 最确切的定义应该是 “偏移（offset）”。
当访问 a[x] 时，根据公式，就代表此处的内存地址偏移了 x 个类型单位。那么从 0 开始就很合理了。

从 1 开始计数的结果：
如果数组从 1 开始计数，则计算内存时的公式会变成如下：
a[k]_address = base_address + (k-1) * type_size

可以看出，此时每次数组寻址时，都要多做一次减法运算，对于CPU来说，就是多一次减法指令。