上一篇文章ArrayList实现分析（一）——对象创建
)主要是介绍了ArrayList对象创建的三种方式的实现原理，下面重点介绍一下ArrayList提供的常用操作的实现原理。
添加元素
ArrayList主要提供了两大类的添加元素的方法：添加单个元素和添加多个元素:
下面的两个方法是添加单个元素
//在ArrayList尾部追加新元素e
public boolean add(E e)
//在index索引指向的位置添加新元素element，原List中处于index索引位置的元素及其后面的元素向右移
public void add(int index, E element)
下面看add(E e)的实现逻辑：
public boolean add(E e) {
// 判断elementData数组是否需要进行扩容，当前并且对modCount字段进行加1
ensureCapacityInternal(size + 1);
//把的新值E增加到elementData数组最后一位
elementData[size++] = e;
return true;
}
首先需要调用ensureCapacityInternal来判断是否需要对elementData数组进行扩容。具体实现如下：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
第一个构造函数表示创建一个空的ArrayList，第二个构造函数创建一个初始大小为initialCapacity的ArrayList，第三个构造函数表示使用一个集合对象来创建一个ArrayList对象。
无论调用哪个构造函数，在内部都是使用elementData指向ArrayList存储的数据元素。
ArrayList添加更新元素
ArrayList列表提供了add方法添加元素，add方法有四个重载方法：
public boolean add(E e)
public void add(int index, E element)
public boolean addAll(Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c)
这四个重载方法一共分为两类，一类是往ArrayList队列尾添加元素，另一类是往队列指定的索引位置添加元素。首先看第一个add方法的具体实现：
public boolean add(E e) {
// 判断elementData数组是否需要进行扩容，当前并且对modCount字段进行加1
ensureCapacityInternal(size + 1);
//把的新值E增加到elementData数组最后一位
elementData[size++] = e;
return true;
}
ensureCapacityInternal方法的实现如下：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果elementData是空,那么就返回默认值和minCapacity最大的值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
由上面的源码可知，首先执行calculateCapacity方法，来获取添加新元素之后list的大小，然后执行ensureExplicitCapacity进行数组大小的扩容，这里需要对modCount做加一操作，记录了该list对象的变更次数。然后判断当前数组的大小是否可以容纳新的数据。如果不能，则需要进行对数组elementData进行扩容。那些重点看一下grow的实现原理：
private void grow(int minCapacity) {
// overflow-conscious code注意下面可能溢出
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);
}
对数组的进行扩展的算法：首先通过老数组计算第一次新数组的大小（newCapacity）=老数组大小+老数组大小/2，当扩展后的newCapacity仍然小于minCapacity，那么执行newCapacity=minCapacity，让新数组的大小等于minCapacity。如果newCapacity大于MAX_ARRAY_SIZE，那么执行hugeCapacity，找到最大的newCapacity,然后利用Arrays.copy把旧数组数据复制到新数组中，新数组的大小是newCapacity，使用elementData指向新的数组，最后完成数组扩容。
注意：MAX_ARRAY_SIZE是数组可分配的最大大小，有些VM会给数组保留8个字节的数组头部，因此MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8
下面说一下public void add(int index, E element) 与add方法逻辑基本相同，add方法是往队列尾增加元素，该方法是往指定的index位置增加元素，并且把原来index只有的所有数据都往后移动一个位置，具体实现如下：
public void add(int index, E element) {
//对索引index合法性进行判断
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
//把index后的所有元素进行后移操作
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
rangeCheckForAdd会对index的合法性进行判断，ArrayList虽然是可以动态变化的集合对象，但是它不允许在超过ArrayList大小的位置插入新数据。
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
ensureCapacityInternal方法实现如上面介绍的，对数据进行扩容。然后 调用System.arraycopy把扩展后的elementData中的index之后的所有数据往右边移动一位，最后把新原始赋值到index位置上。
下面介绍一下批量添加元素的方法实现addAll：
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
addAll的实现方式和add类似，都是需要ensureCapacityInternal进行数据扩展,如果是addAll(int index, Collection<? extends E> c)，需要把index后的元素向elementData右边移动numNew个大小。根据源码分析，应该尽量避免使用add(index,e)和addAll(index,c)操作，因为这样会有大量的数据移动操作。
下面介绍set(int index, E element)方法，该方法的作用是用新元素element替换ArrayList中index的位置上的旧元素，并且返回旧元素，实现如下：
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
根据源码内容，set方法的实现比较简单。
下面介绍sort方法，这个方法是通过传入的Comparator对象，对list进行排序：
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
在sort方法中，首先先获取当前的modCount值，然后再调用 Arrays.sort方法完成对list中的原始数组按照Comparator的要求进行排序，在sort返回之前，检查一下list是否被其他线程进行了修改过，如果有其他线程对list进行过修改，抛出ConcurrentModificationException异常，最后修改modCount。
下面介绍一下lastIndexOf方法和indexOf方法，lastIndexOf是获取list中出现当前元素的最后一个索引值，indexOf是在list中出现当前元素出现的一个索引值。
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
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;
}
由上面的源码可知，如果是lastIndexOf方法，从后向前遍历list，如果是indexOf方法，从前往后遍历list。
还有一个比较重要的方法： retainAll(Collection<?> c) ,该方法的作用是从当前list中删除c中不包含的元素，也就是获取与c的交集，具体实现如下：
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
由上面源码可知，retainAll核心的实现在batchRemove方法中，batchRemove方法在ArrayList中有两个地方使用到：removeAll(Collection<?> c)和retainAll(Collection<?> c)。batchRemove有两个参数，第一个参数c是list，第二个参数是布尔型，当在removeAll中使用的时候，传入false，表示需要从当前ArrayList中删除掉c中所有元素。在retainAll方法中调用的batchRemove传入的是true，表示需要保留c中出现的元素。下面列出核心代码，
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
上面的代码是根据complement的值，对elementData进行数据删除等处理，通过elementData[w++] = elementData[r];把需要保留的元素放到elementData数组的左边。下面的代码是当该list被其他线程操作使得当前的ArrayList增加了数据量，把新增元素的追加到保留的数据元素中。
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
然后是是对elementData中需要删除的元素的所在位置进行赋null。这样的可以使得GC在合适的是对垃圾数据进行清理。
