Java ArrayList【笔记】
ArrayList
ArrayList基本结构
ArrayList 整体架构比较简单，就是一个数组结构
源码中的基本概念
index 表示数组的下标，从 0 开始计数
elementData 表示数组本身
DEFAULT_CAPACITY 表示数组的初始大小，默认是 10
size 表示当前数组的大小，类型 int，没有使用 volatile 修饰，非线程安全
modCount 统计当前数组被修改的版本次数，数组结构有变动，就会 +1
类注释中的说明
1.允许 put null 值，会自动扩容
2.size、isEmpty、get、set、add 等方法时间复杂度都是 O (1)
3.是非线程安全的，多线程情况下，推荐使用线程安全类Collections#synchronizedList
4.增强 for 循环，或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常
ArrayList的初始化方法
有三种，无参数直接初始化，指定大小初始化（给出的是数组的大小），指定初始数据初始化（给出的是数组元素，数组大小由元素个数来确定）
需要注意的是，ArrayList无参构造器初始化的时候，默认大小是空数组，并不是10，10是第一次add的时候的扩容的数组值
ArrayList新增以及扩容
新增就是往数组中添加元素，主要可以分成两步：第一步是判断是否需要扩容，如果需要的话先进行扩容的操作，第二步就直接进行赋值
以上两步的源码：
public boolean add(E e) {
//确保数组大小是否足够，不够执行扩容，size 为当前数组的大小
ensureCapacityInternal(size + 1); // Increments modCount!!
//直接赋值，线程不安全
elementData[size++] = e;
return true;
}
扩容的设计，如果初始化数组大小的时候，有给定过初始值，那么就以给定的大小为标准，不需要按照数组元素个数来确定数组的大小，我们在扩容的时候要记录数组被修改的情况，如果我们需要的最小容量大于目前的数组的长度，那么就扩容，需要将现有的数据拷贝进新的数组中
其中，如果扩容后的值小于期望值，那么扩容后的值就等于期望值，比如，我们需要16个，之前有10个，扩容以后有15个，还是不够，那么最后数组扩容后的大小就是16，但是，如果扩容后的值大于jvm所能分配的数组的最大值，那么就只能用 Integer 的最大值，然后通过复制进行扩容
源码：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
关于新增和扩容有一些事项：
1.扩容的规则并不是整倍整倍的增加，而是原来的容量加上容量的一半，也就是变成原来的1.5倍
2.ArrayList中的数组的最大值为Integer.MAX_VALUE，一旦超过了这个数值，jvm就不会给数组分配任何内存空间了
3.在新增的时候，允许null值
4.扩容实际上是由Arrays.copyOf(elementData, newCapacity)实现的，其本质就是数组之间的新建与复制，先建一个符合的数组，然后将以前的数组的数据全部复制过去
ArrayList删除
删除元素的方式有很多，以根据值删除的方式来进行说明
首先我们要找到需要删除的元素的索引的位置，如果要删除的值是 null，那么就找到第一个值是 null 的删除，如果要删除的值不为 null，那么就找到第一个和要删除的值相等的删除，寻找的操作是通过equals来判断值是否相等的，那么在判断值相等以后，再根据索引位置进行删除
需要注意，在新增的时候是没有对 null 进行校验的，是允许null值的，那么在删除的时候，其实也是允许删除 null 值的
而且因为寻找值在数组中的索引位置是通过 equals 来判断的，数组元素是基本类型的情况时就按照正常的比较就可以，但是，如果数组元素不是基本类型，这个时候就需要关注 equals 的具体实现才可以
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
在找到需要删除的索引的位置以后，就需要根据索引位置来进行删除操作，简单来说，在某一个元素被删除后，为了维护数组结构，需要把数组后面的元素往前移动，数组最后空出来的位置为null
numMoved 表示删除 index 位置的元素后，需要从 index 后移动多少个元素到前面去，至于为什么要减 1，是因为 size 从 1 开始算，index 从 0开始算，我们从 index +1 位置开始被拷贝，拷贝的起始位置是 index，长度是 numMoved
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null;
}
ArrayList迭代器
迭代器一般来说有三个方法：
1.hasNext 还有没有值可以迭代
2.next 如果有值可以迭代，迭代的值是多少
3.remove 删除当前迭代的值
hasNext的方法是比较简单的，如果下一个元素的位置和实际大小相等，就说明没有元素可以迭代了，不等的话，就还有可以迭代的
源码：
public boolean hasNext() {
return cursor != size;
}
next的方法则是在迭代的过程中需要判断版本号有没有被修改，如果有修改就报异常，没有修改的话就在本次迭代过程中找元素的索引位置，找到迭代的值，并为下一次的迭代进行准备
源码：
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
Remove的方法，如果上一次操作的时候，数组位置已经小于0了，这就说明数组已经删除完了，然后也要在迭代的过程中检测版本号有没有修改，修改了就要报异常
源码：
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
需要注意的是，remove中的lastRet = -1 的操作目的，是防止重复删除操作，且在删除元素成功，数组当前 modCount 就会发生变化，这里会把 expectedModCount 重新赋值，下次迭代时两者的值就会一致了
ArrayList线程安全
只有当 ArrayList 作为共享变量时，才会有线程安全问题，当 ArrayList 是方法内的局部变量时，是没有线程安全的问题的
一些问题
有一个 ArrayList，数据是 2、3、3、3、4，中间有三个 3，现在通过 for (int i=0;i<list.size ();i++) 的方式，需要把值是 3 的元素删除，请问可以删除干净么？最终删除的结果是什么，为什么？
删除代码如下：
List<String> list = new ArrayList<String>() {{
add("2");
add("3");
add("3");
add("3");
add("4");
}};
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals("3")) {
list.remove(i);
}
}
显而易见的，删不干净，因为没删除一个元素后，这个元素后面的元素就会往前移动，而此时循环的i是不会停下来的，会一直增长，这样就会漏掉一个
i为0的时候，不删除
i为1的时候，从0号位到了1号位，此时发现了3，进行删除操作，删除以后，元素前移，原本在2号位的3移动到了1号位，3号位的3移动到了2号位，4号位的4移动到了3号位，最后的位置变成了null
i为2的时候，从1号位到2号位，删除2号位的3，元素继续前移
i为3的时候，没有删除，结束，此时数组的情况是，0号位为2，1号位为3，2号位为4，3号位和4号位为null，这样就还剩一个3删不掉
可以发现，这种删除的话每次删除都会让后一个需要删除的遗漏
这种情况可以使用Iterator.remove () 方法来解决，因为 Iterator.remove () 方法在执行的过程中，会把最新的 modCount 赋值给 expectedModCount，这样在下次循环过程中，modCount 和 expectedModCount 两者就会相等，就不会出现遗漏的情况
这种情况对于 LinkedList 也是如此，虽然二者的底层结构不同，一个是数组，一个是双向链表
