数组（一）

数组，是一个存储多个相同类型数据，有序的数据结构。

我们不用自己去实现一个数组，先看看Java8的数组是怎么实现的！

首先映入眼帘的是ArrayList的成员变量和构造方法

默认初始容量为10。两个空实例DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA。这两个空实例的不同在于第一次添加元素时，需要开辟多少空间（在add方法里体现出来）。

1、add(E e)

首先判断是否需要扩容，然后在数组尾部添加元素。

如果数组是无参构造出来的，则使用默认容量10进行比较是否需要扩容。

modCount是指该数组被更新的次数。

一些VM在数组中保留一些header ward。试图分配较大的数组可能导致OutOfMemoryError：请求的数组大小超过VM限制。

扩容是扩容到原来数组的1.5倍。

两个if是处理扩容的空间太大或太小的情况

最后的Arrays.copyOf是将原来的数组元素复制到新的数组里面！时间复杂度是O(n)。但是扩容不是每次都发生的，而是在第n次添加的时候才会触发，那将这一次触发扩容操作均摊给前面的那n-1次添加，那么add的时间复杂度是O(1)。

2、add(int index，E e)

在指定位置添加元素。

首先判断添加的位置是否超出数组范围，然后判断是否扩容，接着第index及index位置后的元素都向后挪一位，最后把元素添加到指定位置index上。时间复杂度为O(n)。

3、remove（int index）

删除指定位置的元素。

首先判断指定的位置是否越界，然后将index后面的元素都往前挪一位，最后将最后一位元素设置为null。时间复杂度为O(n)

由于篇幅很长，ArrayList的查找和更新就不说了，他们都是根据数组的索引下标进行查找和更新的，时间复杂度都是O(1)。

总结一下，数组的查找、更新操作都是O(1)，在尾部添加、删除尾部元素在均摊复杂度下也是O(1)，在头部或者数组的中间某个位置添加删除，他们的时间复杂度都是O(n)！在这种情况下，我们有什么办法能对其进行优化呢？请看下集。