什么是数组？

数组是线性表的一种结构。它使用一段连续的内存空间，存储相同类型的数据。

特点

数组最明显的特点：

• 随机访问

低效的插入和删除
为了保证内存数据的连续性，插入和删除操作都需要移动插入或删除位置数据之后的数据，以保证操作后的数据具有连续性，同时也使得查找数组中的某个元素变得很高效。

高效的查找数组中某个位置的数据

//计算数组第i个数据的内存地址
a[i]_address = base_address + i * data_type_size

分析要严谨

对于一群无序的数据（数据既然无序，那么按照顺序一个一个往后挪就没有意义了，直接替换目标位置的数据到末尾即可），我们在插入时只需要将固定位置的数据换到最后即可。此时的时间复杂度为O(1)。

x插入到第3个位置.png

下面我要删除有序数组中的几个元素：
假设我们要删除某个数组中的3个元素，那我们需要挪动3次数据，每次挪动数据的时间复杂度为O(n)（这里考虑的是平均时间复杂度）。如果每次删除的时候，我们并不是立刻删除，而是将要删除的数据的位置记录下来，等到一定数量之后一起删除，那么我们在挪动数据的时候就只需要挪动1次数据。时间是原来的1/3.

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

  
  删除3个元素.png

为什么数组的下标是从0开始的？

我们可以从两方面开始分析：时间，空间

• 时间
  如果从0开始，在计算第k个元素的时候计算如下：

a[k]_address = base_address + k * type_size

如果从1开始，在计算第k个元素的时候计算如下：

a[k]_address = base_address + (k-1)*type_size

很明显，计算第k个元素，从1开始比从0开始多一步-1操作，对于cpu来说就是一次减法指令。

• 空间
  我们都知道计算机的计数方式是二进制，那就必定存在0号位置。
  0-7（十进制）可以由000-111（二进制）表示；
  1-8（十进制）需要由001-1000（二进制表示）；
  既然有000可以表示一位数，为什么不用呢？