今天我们来聊一种最基础的数据结构，在每一种编程语言中基本上都会有这种数据类型，相信大家都听说过，使用过，它就是数组。

定义

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

数组的定义，画个图看起来可能就比较直观了：

Java 中使用 int[] a = new int[5]创建一个 int 类型的数组，在内存中是怎么分配内存空间的呢？如下图所示：假如此数组的占用内存块的首地址为100，一个int类型占用4个字节。

如上图所示，因为数组是一种线性表，因此数组上的数据最多只有向前和向后两个方向。因为数组用一组连续的内存空间，因此实际内存分配时会提供一组连续的内存空间，同时因为存储的是一组相同类型的数据，因此数组中每个数据占用的空间是相同的，数组中各数据的内存地址也能很方便的计算出来。

随机访问

计算机是通过内存地址来访问内存中的数据的，而基于上述数组的定义，计算机访问数组内的数据时能够实现随机访问。

例如我们需要读取a[3]的数据，计算机首先会通过寻址公式计算出a[3]的内存地址：

100+3*4=112

其中100为数组a的首地址，3为数组的下标，4为数组中每个元素的大小，这个例子中数组中的数据为int类型，而int类型占4个字节。

计算机计算出a[3]的地址后，即可通过地址直接读取a[3]的数据。此时通过数组下标来访问数组内数据的时间复杂度为O(1)。

低效的插入

事物都有两面性，由于数组使用了连续的内存空间来存储同一类型的数据，从而使数组拥有了优秀的随机访问能力，但是它损失的则是插入和删除的效率。

还是以int [] a=new int[5]为例子，当数组中已存在a[0]=1，a[1]=3，a[2]=4时，这个时候我们需要将2插入到a[1]的位置，为了保证连续性，那我们需要做的操作为：

1、将3、4往后挪一位，变成a[2]=3，a[3]=4。

2、将2赋值为a[1]，a[1]=2，最终变为a[0]=1，a[1]=2，a[2]=3，a [3]=4。

之前聊过，判断一个算法的好坏，可以用时间复杂度来表示。根据我们之前介绍的内容我们来分析下数组插入操作的时间复杂度：

1、如果插入的位置是数组的最末尾，那数组直接插入就可以了，这个时候的时间复杂度为O(1)，因此数组插入的最好时间复杂度为O(1)。

2、如果插入的位置是数组的第一位，那数组中所有的数据都需要依次往后移动一位，那数组插入的最坏时间复杂度为O(n)。

3、由于我们在数组中每个位置插入数据的概率是一样的，均为1/n。因此数组插入操作的平均时间复杂度为（1+2+3+...+n）/n= O(n)。

如果数组是有序的，那数组的插入就必须按照上面的步骤进行，保证插入后的数组仍然是有序的。如果数组本身就是乱序的，对存储数据的顺序没有要求，那针对数组的插入有一个技巧能提高插入的效率：即将需要插入的那个位置的数据放到数组的末尾，然后把数据插入指定位置。举例如下：

还是以上面的例子为例，我们需要将2插入到a[1]的位置，我们可以这么做：

1、将a[1]的值赋值给最末尾的a [3]，即a [3]=3

2、将2赋值给a[1]，即a[1]=2，最终数组变为：a[0]= 1,a[1]=2, a[2] = 4,a[3]=3

这样数组的插入操作的时间复杂度就降为了O(1)。

低效的删除

删除操作其实和插入操作类似，插入操作是将数组中的数据后移一位，然后在指定位置插入数据。而删除则是将数组中的数据前移一位，然后删除最末尾的数据。

以int [] a =new int[5]为例，当数组中已存在a[0]=1，a[1]=2，a[2]=3,a[3]=4时，我们删除a[1]，需要如下步骤：

1、将a[1]后的数据全部前移一位，即a[1]=3，a[2]=4。

2、删除最后一位，即a[3]=0。

我们来分析删除操作的时间复杂度。和插入操作类似，如果删除的是数组最末尾的数据，则时间复杂度为 O(1)。如果删除的是数组的第一位数据，则时间复杂度为 O(n)。平均时间复杂度也为O(n)。

当然，在某些特定的场景下，删除操作也是可以优化的：

例如现在数组中有1，2，3，4，5，6，7，现在需要依次删除3，4，5，为了避免6，7这两个数据移动三次，可以先将3，4，5进行标记，记录数据已经被删除。当数组没有更多空间存储数据时，再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据移动。JVM 中标记清除垃圾回收算法的核心思想就在于此。

今天我们介绍了一种最基础的数据结构，介绍了它的定义，描述了它的适用场景。在平时的开发过程中，我们一般都是直接使用编程语言提供的容器类来使用数组，比如 java 中的 ArrayList。使用容器类可以让我们很方便的使用数组，像插入、删除操作，容器类中都有对应的封装方法，不用让我们亲自编写数组中数据的移动。但是容器类的封装在实现上有一定程度的性能损耗，比如自动拆箱、封箱，因此在开发特别底层的软件时，直接使用数组可能会更加适合。