数组，几乎是每个编程语言都有的一种数据类型，我相信大家肯定不陌生。它不仅仅是一种编程语言的数据类型，还是一种最基础的数据结构。在大部分编程语言中，数组都是从0开始编号的，但你是否下意识地想过， 为什么数组要从0开始编号，而不是从1开始呢？ 从1开始不是更符合人类的思维习惯吗？
&emsp 接下来可能需要你带着这种疑惑学习下去。

如何实现随机访问？

  什么是数组？我相信大家心中都有答案。数组——就是一种线性表存储一组具有相同类型的数据。
  这里定义几个关键词，理解这几个关键词就能掌握数组这个概念了。

• 第一线性表

  顾名思义，线性表就是像线一样排列的数据结构。每个线性表上的数据最多只有前和后，其实不只是数组，像队列、栈、链表等数据结构都是线性表结构。而它对立的概念是非线性表结构，比如二叉树、堆、图等，就像下图这样：

• 第二个是连续的内存空间和相同类型的数据

  正是因为这两个概念，所以数组才实现了随机访问这个杀手锏特性。但有利有弊，这个特性也让数组的增删改变得非常低效，比如删除或者插入，为了保证连续性就需要做大量的数据搬移工作。
  说到随机访问，你知道这是怎么实现的吗？
  其实非常简单，我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10] 来举例。在下图中，计算机给数组 a 分配了一块连续的内存空间 1000-1039，其中内存的首地址为 base_address = 1000。

  我们知道计算机会给每个内存空间分配一个地址，计算机通过内存地址来获取内存中的数据。当计算机需要随机访问数组中的某个元素时，就会通过寻址公式计算元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

  其中 data_type_size 表示数组中每个元素的大小。公式非常简单，大家应该一看就懂。
  实际上还有一个问题需要纠正，面试中大家问到：“数组和链表的区别？” 大家都会回答：“链表适合插入，时间复杂度 O(1); 数组适合访问，时间复杂度 O(1)。”其实这是不准确的，数组的查找时间并不是 O(1)，即使是使用二分查找法，时间复杂度也是O(logn)。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。

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

  前面讲到，数组为了保证内存的连续性，会导致插入、删除两个操作比较低效。现在我们就来聊一下，为什么会造成这种情况。
  我们来看一下插入操作。
  假设数组的长度为n，现在，如果我们需要将一个数据插入到数组中的第k个位置。为了把第k个位置腾出来，给新来的数据，我们需要将第k ～ n这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢？你可以自己先试着分析一下。
  很明显，最坏的情况是 O(n)，从第一位开始就需要往后移，但是我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为(1+2+…n)/n=O(n)。
  这是数组有序的情况，但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数组插入到第k个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第k位的数据搬移到数组元素的最后，把新的元素直接放入第k个位置。
  为了更好地理解，我们举一个例子。假设数组a[10]中存储了如下5个元素： a， b， c， d， e。
  我们只需要将c放入到a[5]，将a[2]赋值为x即可。最后，数组中的元素如下： a， b， x， d， e， c。
  利用这个技巧我们就可以将时间复杂度降到 O(1)
  跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？

  为了避免d， e， f， g， h这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

警惕数组的越界访问问题

  这是老生常谈也是新手经常出现的问题。在C语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的，数组越界在C语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。
  但并非所有的语言都像C一样，把数组越界检查的工作丢给程序员来做，像Java本身就会做越界检查，比如下面这几行Java代码，就会抛出java.lang.ArrayIndexOutOfBoundsException。

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