采用数组方式存储数据，可以添加null元素，此数组元素数大于实际存储的数据以便增加插入元素，都允许直接序号索引元素，但是插入数据要涉及到数组元素移动等内存操作，所以插入数据慢，查找有下标，所以查询数据快
看了这几篇文章，一个系列的，讲的非常好，感谢作者，下面我只进行一些要点的补充以及总结。
https://zhuanlan.zhihu.com/p/27873515
https://zhuanlan.zhihu.com/p/27878015
https://zhuanlan.zhihu.com/p/27938717
https://zhuanlan.zhihu.com/p/28016098
ArrayList是线程不安全的，相比于Vector，Vector在真正操作数据的函数都需要加入synchronized关键字
ArrayList的缓存：
主要是利用static和final的变量特性，不需要我们new，JVM会提前初始化好，并且static变量只有唯一一份，无论多少该类有多少个对象，因而，每次使用ArrayList的无参构造函数new新的对象，作者为了避免我们反复的创建无用数组，所有新new出来的ArrayList底层数组都指向缓存在方法区里的Object[]数组，其实是指向了最根本的DEFAULTCAPACITY_EMPTY_ELEMENTDATA静态数组。
ArrayList允许存在null元素
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
比如其indexOf方法，只要在size范围内，如果存在即可
ArrayList的add(E e)：
先确保容量，使用ensureCapacityInternal()，默认容量DEFAULT_CAPACITY为10，不得不上图
1.jpg
2.jpg
这里，grow方法，ArrayList的数组拓展为原数组的1.5倍（使用length，size表示实际的元素有多少个，length是数组带有的属性）。
稍微提一下，这里利用到了Arrays的copyOf方法，其底层实现有native关键字，表示是非java语言实现的，因而，如果有数组拷贝，建议使用java自带的此方法
ArrayList的add(int index, E element)：
判断下标是否合法，先确保容量，再将index及其后的元素往后复制，再插入
主要关注时间复杂度：如果我们不指定位置直接添加元素时(add(E element))，元素会默认会添加在最后，不会触发底层数组的复制，不考虑底层数组自动扩容的话，时间复杂度为O(1) ，在指定位置添加元素(add(int index, E element))，需要复制底层数组，根据最坏打算，时间复杂度是O(n)。
add()都需要考虑确保容量问题
EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别：
DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA数组的区别在于当第一个元素被加入进来的时候它知道如何扩张；可以看到在无参构造函数中，代码
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
在这里其实是构造了一个初始容量为 10 的空列表，为何？看add函数便知，在源码中函数add(E e)中的第一行代码中的所在的函数就是这句话的实现，当中调用ensureCapacityInternal，代码在此处确定了容量至少为10（即默认容量）
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
==其实依旧不是很明白，有大神知否？==
ArryList的remove()：
有两种形式
- remove(int index)——检查下标合法，进行元素删除，并且拷贝后面的元素覆盖，将最后一个元素置为null
- remove(Object o)——先判断o是否为空，在size范围内如果有空，fastRemove后返回true，如果不为空，使用equals判断，其他情况返回false。注意：使用此方法进行删除元素，一般需要重写equals
最终，remove都只是将elementData[i]=null，clear也是一样，但clear需要遍历每一个元素赋值为null，而不是直接将elementData=null，
时间复杂度：如果底层数组长度为n，当我们用下标方式去删除元素时，如果删除的是最后一个元素，不会触发数组底层的复制，时间复杂度为O(1)。如果删除第i的元素，会触发底层数组复制n-i次，根据最坏情况，时间复杂度为O(n)。
fastRemove其实只是将代码提取出来，做了拷贝工作而已（在ArrayList中，fastRemove只是给remove方法使用）
ArrayList的RangeCheck()：
应用于一下几个函数（add函数使用rangeCheckForAdd）
- get(int index)
- set(int index, E element)
- remove(int index)
比较需要关注的，在RangeCheck里面，没有检查index是否<0，因为这些方法在调用了rangeCheck()方法后，会马上调用elementData(int index)方法来获取指定位置元素的值。（个人表示不咋理解为啥要这么弄，有理解的朋友麻烦讲讲？）这两个方法调用保证了0 < index < size()
ArrayList的get()和set()：
由于是数组，底层数组存/取元素效率非常的高，时间复杂度是O(1)
clone()
实现clone()需要有Cloneable接口，否则抛出CloneNotSupportedException，ArrayList的clone只是浅复制，也就是引用的元素本身是跟原本同样的
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
ArrayList的优劣势：
下标的标索引、存/取快
查找（非下标查询），插入和删除元素效率似乎不太高，时间复杂度为O(n)，尤其是在有大量数据的时候。
插入和删除元素效率->找LinkedList
查找元素效率不高->找HashMap
网友评论