在大部分编程语言中，数组都是从0开始编号的，但你是否下意识想过，为什么数组要从0开始编号，而不是1开始呢？ 从1开始不是更符合人类的思维习惯吗？下面以这个问题来学习数组。

数组的基本概念与特性

什么是数组？

什么是数组？估计你心中已经有了答案。不过，这里还是总结一下。数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。这里定义里有几个关键词，理解了这几个关键词，就能彻底掌握数组的概念了。

线性表（Linear List）。顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。除了数组，链表、队列、栈等也是线性表结构。

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

总结下数组的特性

• 第一是线性表（Linear List）。
• 第二是连续的内存空间和相同类型的数据。

正是因为这两个限制，它才有一个堪称“杀手锏”的特性 “随机访问” 。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一条数据，为来保证连续性，就需要左大量的数据搬移工作。

如何实现随机访问？

数组到底是如何实现根据下标随机访问数组元素的？例如：长度为 10 的 int 类型的数组 int[] a = new int[10]

1. 计算机给数组 a[10] ，分配了一块连续内存空间 1000 ~ 1039 ；
2. 内存块的首地址为 base_address = 1000 ；
3. 计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。

当计算机需要随机访问数组中的某个元素时，它会通过下面的寻址公式，计算出该元素存储的内存地址：a[i]_address = base_address + i * data_type_size

arr[i] 首地址 = 数组内存块首地址 + 数据类型大小 * i，其中 i 为偏移量，其中 data_type_size 表示数组中每个元素的大小。

上面这个例子里面：base_address ：内存块的首地址。data_type_size : 表示数组中每个元素的大小，比如目前数组中存储的是 int 类型数据，所以 data_type_size 就为 4 个字节。

数组时间复杂度

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

1. 数组是一种线性表；
2. 连续的内存空间和相同类型的数据。由于第二个性质，数组支持 “随机访问”，根据下标随机访问时间复杂度为 O(1)，但是在数组中删除、插入数据时需要做数据搬移工作。

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

1. 插入操作

假如数组的长度为 n，我们需要将一个数据插入到数据的第 k 个位置，则需要将 [k , n] 位元素都顺序地往后挪动一位。

• 最好的情况：时间复杂度为O(1)，此时在数组末尾插入元素。
• 最坏的情况：时间复杂度为O(n)，此时在数组开头插入元素。
• 平均的情况：时间复杂度为O(n)，因为在每个位置插入元素的概率相同，故（1+2+3+......+n）/ n = O(n)。

2. 删除操作

和插入操作一样，为了保证内存的连续性，删除操作也需要搬移数据。

• 最好的情况：时间复杂度为O(1)，此时删除数组末尾的元素。
• 最坏的情况：时间复杂度为O(n)，此时删除数组开头的元素。
• 平均的情况：时间复杂度为O(n)，因为删除每个位置的元素的概率相同，故（1+2+3+......+n）/ n = O(n)。

更高级用法

在某些特殊场景下，在不追求数组中数组的连续时，我们将多次删除操作集中在一起执行，会提高删除的效率？例如：假设有一个数组 a , 长度为 10，存储了 8 个元素，分别为 a,b,c,d,e,f,g,h 。现在我们依次删除 a,b,c 三个元素：

a = [a,b,c,d,e,f,g,h];

为了避免 d,e,f,g,h 这个几个数据会被搬移 3 次，我们先记录已经删除的数据（每次删除操作并不是真正的搬移数据，只是记录数据已经被删除）。当 a 数组没有空间存储数据时，这才触发依次真正的删除操作，这样就减少了删除操作导致的数据搬移。

上述这个操作其实就是 JVM标记清除垃圾回收算法 的核心思想。

3. 警惕数组访问越界

在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。如果疏忽会造成严重的后果。当然，Java语言会自动检测。

4. 总结

数组是最基础、最简单的数据结构。数组用一块连续的内存空间，来存储相同类型的一组数据，最大特点就是随机访问元素，并且时间复杂度为 O(1)。但是插入、删除操作也因此比较低效，时间复杂度为O(n)。

数组和链表的区别

• 数组支持随机访问，根据下标随机访问的时间复杂度为O(1)，注意数组查找，即便是排好序的数组，使用二分查找时间复杂度为O(logn)。
• 链表适合插入、删除、时间复杂度为O(1)

最后总结一下：为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢？

• 第一：历史原因， c 语言设计者用 0 开始计数数组下标，之后 Java、JavaScript等高级语言都效仿 C 语言，因此继续沿用从 0 开始计数的习惯。部分语言数组不是从 0 开始计数的，比如 Matlab，还有部分语言支持负数下标，如 Python。

• 第二：从数组存储的内存模型上来看，“下标”最确切的定义应该是 “偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置，也就是首地址，a[k] 就表示偏移 k 个 type_size 的位置，所以计算 a[k] 的内存地址只需要用这个公式：

a[k]_address = base_address + k * type_size但是，如果数组从1 开始计数，那我们计算数组元素 a[k] 的内存地址就会变为：a[k]_address = base_address + （k-1）* type_size

对比两个公式，不难发现，从 1 开始编号，每次随机访问数组元素都多来一次减法运算，对于 CPU 来说，就多来一次减法指令。

数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致，所以为来减少一次减法操作，数组选择来从 0 开始编号，而不是 1 开始。

部分图片来源于网络，版权归原作者，侵删。