#技术派的书架#

提到数组，读者肯定不陌生，甚至还会很自信地说，数组很简单。编程语言中一般会有数 组这种数据类型。不过，它不仅是编程语言中的一种数据类型，还是基础的数据结构。尽管数 组看起来非常基础、简单，但深究起来，数组还有很多值得思考的地方。 例如，在大部分编程语言中，数组的下标是从 0 开始编号的。读者是否想过，为什么数组 的下标要从 0 开始编号，而不是从 1 开始呢？从 1 开始编号不是更符合人类的思维习惯吗？读 者可以带着这些问题学习本节的内容。

数组的定义

什么是数组？数组是一种线性表数据结构，它用一组连续的内存空间存储一组具有相同类 型的数据。在数组的这个定义中，包含了 3 个关键词。 数组的定义中的第一个关键词是“线性表”（linear list）。顾名思义，线性表指的是数据排 列成像一条线一样的结构。线性表中的数据只有前、后两个方向。其实，除数组之外，本章要 讲到的链表、栈和队列都是线性表结构，如图 2-1 所示。 与线性表相对立的概念是非线性表，如树、图等，如图 2-2 所示。之所以称为非线性表， 是因为数据之间并不是简单的前后关系。从图 2-1 和图 2-2 可以直观地看出线性表和非线性表 的区别。

数组的定义中的第二个关键词和第三个关键词是“连续的内存空间”和“相同类型的数 据”。正是因为这两个限制，数组才有了一个重要的特性：随机访问。不过，有利就有弊，这 两个限制也让数组的很多操作变得非常低效。例如，要想在数组中插入或者删除一个数据，为了保证数组中存储数据的连续性，我们需要做大量的数据搬移工作。

寻址公式和随机访问特性

随机访问”具体指的是：支持在 O(1) 时间复杂度内按照下标快速访问数组中的元素。我 们用一个长度为 10、int 类型的数组 a[10]（代码实现为 int[]a = new int[10]）来举例。假设计算机给数组 a[10] 分配了一块连 续内存空间，其中，内存空间的首地址 base_address=1000。数组 的内存存储模型如图 2-3 所示。 我们知道，计算机会给每个内存单元分配一个地址，目的是 方便计算机通过地址来访问内存中的数据。当计算机想要访问下 标为 i 的数组元素时，它首先通过下面的寻址公式（见式（2-1））， 计算出该元素存储的内存地址，然后根据地址访问对应的内存单元。

其中，data_type_size 表示数组中每个元素的大小。由于数组中存储的是 int 类型的数据 （int 类型占 4 字节的存储空间），因此 data_type_size 就等于 4。 在这里，作者要纠正一个“错误”。作者在面试应聘者的时候，常常会向应聘者询问数组 和链表的区别，很多应聘者回答：“链表适合插入、删除，对应的时间复杂度为 O(1) ；数组适 合查找，查找的时间复杂度为 O(1)。” 实际上，这种表述是不准确的，因为在数组中查找数据的时间复杂度并不为 O(1)。即便 是排好序的数组，用二分查找，时间复杂度也只能达到 O(logn)。因此，正确的表述应该是： 数组支持随机访问，根据下标访问元素的时间复杂度为 O(1)。

低效的插入和删除操作

在上文中，我们提到，为了保持内存数据的连续性，数组的插入、删除操作会比较低效。 现在我们就来解释一下为什么这两种操作会低效，同时探讨一下有哪些改进方法。 我们先来看插入操作。 假设数组的长度为 n。现在，假设我们需要将一个数据插入到数组中的第 k 个位置。为了 把第 k 个位置腾出来给新来的数据，我们需要将第 k ～ n 这部分元素顺序地往后移动一位。在 这种情况下，插入操作的时间复杂度是多少呢？读者可以自己先试着分析一下。 如果在数组的末尾插入元素，那么不需要移动数据，最好情况时间复杂度为 O(1)。但如果在 数组的开头插入元素，那么所有的数据都需要依次往后移动一位，最坏情况时间复杂度是 O(n)。 因为在每个位置插入元素的概率是相同的，所以平均情况时间复杂度为 (1+2+…+n)/n = O(n)。 如果数组中的数据是有序的，在某个位置（假设下标为 k 的位置）插入一个新的数据时， 就必须按照刚才的方法，搬移下标 k 之后的数据。但是，如果数组中存储的数据并没有任何规 律，那么数组只是被当成一个存储数据的集合。在这种情况下，为了避免大规模的数据搬移， 我们可以将第 k 位的数据搬移到数组的最后，然后把新数据直接放到第 k 个位置即可。为了更 好地理解这段描述，我们通过一个例子来进一步解释一下。 假设数组 a 中存储了 5 个元素：a、b、c、d 和 e。现在，需要将元素 x 插入到第 3 个位置。按照上面的处理思路，只需要将原本在第 3 个位置的 c 放入到 a[5] 这个位置，然后将 a[2] 赋 值为 x。最后，数组中的元素为 a、b、x、d、e 和 c，如图 2-4 所示。 利用这种处理技巧，在特定场景下，在第 k 个位置插入数据的时间复杂度就变成了 O(1)。 这种处理思路在快速排序中也会用到，在 3.5 节中具体讲解。 下面再看一下删除操作。 与插入操作类似，如果我们要删除第 k 个位置的数据，为了存储数据的连续性，那么也需 要搬移数据，不然中间就会存在已经删除的数据，数组中的数据就不连续了。因此，如果删除 数组末尾的数据，则最好时间复杂度为 O(1) ；如果删除数组开头的数据，则最坏时间复杂度 为 O(n) ；如果删除任意位置的数据，则平均时间复杂度为 O(n)。 实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多 次删除操作集中在一起执行，删除的效率就会提高很多。我们还是通过例子来解释。 假设数组 a[10] 中存储了 8 个元素：a、b、c、d、e、f、g 和 h。现在，我们要依次删除 a、 b 和 c，如图 2-5 所示。

为了避免 d、e、f、g 和 h 这几个元素被搬移 3 次，每次的删除操作并不真正地搬移数据， 而只是标记数据已被删除。当数组中没有更多的存储空间时，我们再集中触发执行一次真正的 删除操作，这样就大大减少了删除操作导致的数据搬移次数。 如果读者了解 JVM（Java 虚拟机），就会发现，这不就是 JVM 标记清除“垃圾”回收算法 的核心思想吗？没错。数据结构和算法的魅力就在于此。很多时候我们并不需要“死记硬背” 某个数据结构或算法，而是要学习其背后的思想和处理技巧。这些东西才是最有价值的。如果读 者细心留意，就会发现，无论是在软件开发还是架构设计中，总能找到数据结构和算法的影子。

警惕数组访问越界问题

在了解了数组的基本操作后，我们需要警惕数组访问越界的问题。首先，请读者分析一下 下面这段 C 语言代码的运行结果。

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

这段代码的运行结果并非是输出 3 行“hello world”，而是会无限循环输出“hello world”，这是为什么呢？实际上，上面这段代码是有bug的。数组大小为3，for循环的结束条件本应该是i < 3， 但被错误地写成 i <= 3。因此，当 i = 3 时，for 循环里的 a[i] = 0 这条代码语句访问 越界了。 根据前面提到的数组寻址公式，a[3] 会被定位到某块不属于数组 a 的内存地址上，而这 个地址正好是存储变量 i 的内存地址，那么 a[3] = 0 就相当于 i = 0，因此，就会导致代 码无限循环，一直输出“hello world”。 在 C 语言中，数组访问越界是一种未决行为，换句话说，C 语言规范并没有规定数组访 问越界时编译器应该如何处理。访问数组的本质就是访问一段连续内存，只要通过偏移计算得 到的内存地址是可用的，即便数组访问越界，程序就有可能不会报出任何错误。 数组访问越界一般会导致程序出现莫名其妙的运行错误，调试的难度非常大。除此之外， 很多计算机病毒也正是利用了数组越界可以访问非法地址的漏洞来攻击系统的。因此，在写代 码的时候，我们一定要警惕数组访问越界问题。 但并非所有的语言都像 C 语言一样，把数组越界检查的工作“交”给程序员来做。例如 Java 语言，它本身就会进行越界检查，如下面这两行 Java 代码，数组访问越界，运行时就会 抛出 java.lang.ArrayIndexOutOfBoundsException 异常。

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

容器能否完全替代数组

针对数组类型，很多编程语言提供了容器类，如 Java 中的 ArrayList、C++ STL 中的 vector。 在项目开发中，什么时候适合用数组？什么时候适合用容器？ 这里作者用 Java 语言来举例。如果读者是 Java 工程师，应该很熟悉 ArrayList，那么它与 数组相比，到底有哪些优势呢？ ArrayList 最大的优势是，可以将很多数组操作的细节封装起来，如上文提到的数组插入、 删除数据时的搬移操作。除此之外，它还有一个优势，就是支持动态扩容。 因为数组需要连续的内存存储空间，所以在定义的时候，需要预先指定内存空间大小。如 果我们申请了一个大小为 10 的数组，当第 11 个数据需要存储到数组中时，就需要重新分配一 块更大的内存空间，将原来的数据复制过去，然后将新的数据插入。 如果使用 ArrayList，我们就完全不需要关心底层的扩容逻辑，刚才提到的这些扩容细节 会封装在 ArrayList 中。 这里需要注意一点，由于扩容操作涉及内存申请和数据搬移，是比较耗时的，因此，如果 事先能确定需要存储的数据的大小，最好在创建 ArrayList 的时候，事先指定容器的大小，这 样就能避免在插入数据的过程中出现频繁的扩容操作。举例如下。

ArrayList<User> users = new ArrayList(10000); //事先指定容器大小

对于使用高级语言编程的读者，有了容器，数组是不是就无用武之地了呢？当然不是，有 些时候，用数组会更加合适，如下面几种情况。

• Java ArrayList 无法存储基本类型，如 int、long，需要封装为 Integer 类和 Long 类，而 自动装箱（autoboxing）、拆箱（unboxing）有一定的性能消耗，因此，如果特别关注 性能，或者希望使用基本类型，就可以选用数组。
• 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部 分方法，那么可以直接使用数组。

• 还有一个算是作者的个人喜好 ：当需要表示多维数组时，使用数组往往会更加直观，如 Object[][] array。而如果使用容器的话，那么需要这样定义 ：ArrayList> array。这样编写比较麻烦，可读性也不如 Object[][] array 强。

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

解答本节开篇问题

现在我们来看一下开篇的问题：为什么在大多数编程语言中，数组的下标从 0 开始编号， 而不是从 1 开始编号呢？ 从数组存储的内存模型来看，“下标”确切的定义应该是“偏移”（offset）。a[0] 就是相对 于首地址偏移为 0 的内存地址，a[k] 就是相对于首地址偏移 k 个 type_size 的内存地址。从 0 开 始编号，计算 a[k] 的内存地址只需要用式（2-2）

但是，如果从 1 开始编号，计算 a[k] 的内存地址的公式就会变为式（2-3）

对比上面两个公式，我们不难发现，如果数组下标从 1 开始编号，每次按照下标访问数组 元素，会多一次减法运算。数组是基础的数据结构，通过下标访问数组元素又是其基础的操 作，效率的优化就要尽可能做到极致。因此，为了减少一次减法操作，数组的下标选择了从 0 开始编号，而不是从 1 开始编号。 不过，这个理由可能还不够充分。作者认为，数组的下标从 0 开始编号还是有其历史原因的。 最初，C 语言设计者用 0 作为数组的起始下标，目的是在一定程度上减少 C 语言程序员学习其他编 程语言的成本，之后的 Java、JavaScript 等效仿了 C 语言，继续沿用了数组下标从 0 开始编号的方式。 当然，也并不是所有的编程语言中的数组下标都是从 0 开始编号，如 MATLAB。甚至， 一些语言支持负数下标，如 Python。

本文摘自《数据结构与算法之美》

20个经典数据结构与算法，100个真实项目场景案例，300多幅算法手绘图解，一本在手，算法全有，面试大厂不愁！

豆瓣评分9.5，极客时间畅销专栏集结成书，内容更新30%

下一篇

• 数组（下）：数据结构中的数组和编程语言中的数组的区别

喜欢请关注+评论+转发哦