1 序
首先从最常用的集合类开始，从算法的角度上来看，ArrayList属于线性表的一种。其父类List接口，则属于接口Collection分支下的一系。简单画图示意它们之间的关系。
首先看一下list接口的描述
一种有序集合，这个接口的使用者对插入其中的元素有着精确的控制。通过下标来访问和检索集合中的元素。
特点
- 允许重复元素
- 有序
- 允许插入null
- 源码基于JDK1.8
后续的详细介绍在list专门撰写，这里切入主题ArrayList。
2 ArrayList
可调整大小的集合。允许插入null。内部提供了控制集合容量大小的方法。这个类的实例适合快速随机访问操作。
对于这个集合的操作效率，其size/isEmpty/get/set/iterator/listIterator操作的时间复杂度都是O(1)，需要注意的是其add操作的时间复杂度是O(n)。这里可以根据场景恰当选择容器，比如与LinkedList的使用做对比。
ArrayList的实例都有一个容量(capacity)。这个容量是集合中用于存放元素的数组的大小。
好好解析一下这一句话：
- ArrayList可以包含一个集合容量值
- ArrayList实例保存元素使用的是相对更基础、更快速的数组
- 回到前一步，数组可是有固定的长度的
向ArrayList添加元素时，其容量会自动增加。
3 代码
3.1 构造函数
- 默认构造函数
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
这个构造函数是我们在绝大多数情况下的默认选择。初始化对象的时候，集合内部用户保存元素的数组对象被赋值，注意赋值得到的数组对象是一个长度为零的数组。
由这个构造函数完成初始化的ArrayList对象的初始size都是0，当我们第一次向这个集合对象添加元素的时候，会执行一次扩容到DEFAULT_CAPACITY。
- 指定容量的构造函数
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
这个构造可以让我们在初始化的时候就指定集合的容量，size就等于我们给出的构造入参。当然如果入参为0的时候，内部的数组对象长度也会是0。如果传入负数的话，就会抛出一个参数非法异常。
需要注意的是，这里并没有用前一个构造函数使用的0长度数组对象DEFAULTCAPACITY_EMPTY_ELEMENTDATA，而是另一个对象EMPTY_ELEMENTDATA。
所以现在会发现，类里面有两个静态的长度为0的数组。默认的构造使用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，指定长度的构造函数，在入参为0的情况下使用的是EMPTY_ELEMENTDATA。
- 复制集合元素
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
这里主要是使用了集合接口的方法toArray，先将集合转换为对象数组，然后再根据这数组的长度进行对应的填充动作。
特别一点的在于这里所返回对象数组的元素顺序。实现集合接口的实例都有遍历器，注释很清楚的说明了，返回的元素顺序是按照遍历器的返回顺序执行。这里是可以利用的一个点。
3.2 增删改查
这里的一系列方法均涉及到了来自抽象类AbstractList的一个字段modCount。这个字段主要是为了实现fail-fast机制。java.util包下的集合工具大多不是线程安全的，当一个线程正在修改集合时，需要有一个手段来检测到当前集合正在被操作，其他正在进行遍历操作的线程得以检测到。
遍历器iterator中会频繁操作这个字段，除此之外，ArrayList里面也有很多地方会更新这个值。比如扩容、删除操作等等。
1 add()
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
方法的第二行很好理解，向对象数组添加一个元素。关键是第一行的方法。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
ensureCapacityInternal将添加元素后的对象数组长度作为参数传入，首先判断这个集合是不是仅仅是一个只做了初始化操作的集合，判断的方法就是直接判断容器数组还是不是初始化时的对象DEFAULTCAPACITY_EMPTY_ELEMENTDATA。如果是的话，判断并得到一个当前数组长度与默认数组长度(10)取大的值。将计算得到的容器数组长度值传入方法传入方法ensureExplicitCapacity。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
累加一个来自抽象类的字段modCount，再将入参minCapacity与当前数组长度做对比，大于的话，执行grow方法。
add方法要执行成功，定容数组就一定需要有额外的空间来保存新加入的元素，所以这里首先需要判断保存元素的定容数组是否size够用。如果不够用，那么就需要扩容。这一步就是ArrayList可调整大小中，增大容量的核心方法了。
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
// 获取当前容器数组的大小size
int oldCapacity = elementData.length;
// 预计执行扩容操作的新的容器数组size,其值为原有数组长度的1.5倍,这里使用了位运算-带符号右移,结果为 '原有长度+原有长度的一半'
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果预计扩容值大于了定义的数组长度最大值,执行hugeCapacity方法
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 创建一个指定新长度的数组,并将原有数组的内容复制进去
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 原有的值长度已经超过最大值
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 三目运算,当前数组长度与可允许的最大数组长度值二者间取较小值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
扩容时，新数组的大小指定策略为，当容量已经不够时，新数组大小为原有数组长度的1.5倍。数组的最大长度是
Integer.MAX_VALUE - 8
长度的计算策略是：当前长度加上当前长度的一半，使用了右位移运算符，右移一位即除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);
扩容使用的方法
Arrays.copyOf(elementData, newCapacity);
将原有数组拷贝到一个指定新长度的对象数组中。
2 public add(int index, E element)
public void add(int index, E element) {
// 检查参数index合法性,如果小于0或者大于当前数组size则抛出数组越界异常
rangeCheckForAdd(index);
// 增加数组长度,在原有的长度基础上加一,调用的方法在前面已经分析过,有可能执行扩容操作
ensureCapacityInternal(size + 1); // Increments modCount!!
// 一个nativi方法执行数组拷贝操作
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 向指定位置插入新的元素
elementData[index] = element;
size++;
}
向集合的指定位置插入一个元素，注意这个操作可能抛出的异常，比如一个长度为0的集合，如果要向其第10个位置插入元素就会报错。指定位置已经有元素了，那么该位置及其后面的元素全部后挪一位腾出空间。
3 remove
按元素删除
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
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;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
// modCount统计字段累加
modCount++;
// 获取要删除的元素的下标
int numMoved = size - index - 1;
// 下标安全性检查，然后调用一个native方法执行数组复制操作
if (numMoved > 0)
// 拷贝原数组中被删除位置元素之后的所有遗留元素，拷贝到新数组中的位置为这些元素当前位置再整体前移一位。
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 拷贝后将空出来的最后一位元素位置置空方便GC回收
elementData[--size] = null; // clear to let GC do its work
}
删除目标元素，这个删除方法会首先判断目标对象是不是null对象。空对象的匹配是==而非空对象的匹配是obj.equals()。注意这个方法的删除数组中匹配的第一个元素。也就是说如果list列表中有多个相同元素的时候，这个删除操作也只会删除一个元素。这里和ArrayList设计原则有关了，因为ArrayList是允许插入null并且允许重复插入元素的一种集合对象。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
与按元素删除操作对应的还有一个删除指定位置下标的元素。整体逻辑是一样的。没有了先找寻目标元素下标的操作。因为这个方法需要啊返回被删除的元素，所以会先拿到这个元素的值然后再执行数组拷贝操作。
4 clear()
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
清空列表，将对象数组的所有运用指向null。然后GC会回收掉没有任何引用指向的对象。并且更新ArrayList中记录列表数据长度的size字段的值为0。
5 addAll(Collection<? extends E> c)
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
// 集合转数组,数组顺序由集合遍历器决定
Object[] a = c.toArray();
// 新生成的数组的数据长度
int numNew = a.length;
// 执行数组扩容检查,新的容器数组长度为原list列表长度+新增数组长度
ensureCapacityInternal(size + numNew); // Increments modCount
// 数组拷贝
System.arraycopy(a, 0, elementData, size, numNew);
// 更新类中的长度size字段值
size += numNew;
return numNew != 0;
}
这个方法，一看入参构造就可以想起前面提到的一个构造函数。API介绍中说明了是将当前collection集合中的所有元素添加到当前list列表的尾部。新加入元素的顺序由其colltion集合的遍历器决定。
6 addAll(int index, Collection<? extends E> c)
4 查询系列方法
4.1 包含关系查询
这其中包含了多个方法
4.1.1 indexOf(Object o)
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
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;
}
获取指定元素在容器中的位置。如果列表中没有包含这个指定的元素则返回-1。看了源码还是会注意到一点：对于在列表中已经存在的多个元素，这个检查只会返回在列表顺序中的符合条件的第一个元素的位置。如果这个元素位置之后还有匹配的元素，那么这个检查方法是没有查找到这些元素的位置的。
就是对保存元素的数组进行的遍历操作，分为null类型元素和非null类型元素的遍历两种。
4.1.2 contains(Object o)
/**
* Returns <tt>true</tt> if this list contains the specified element.
* More formally, returns <tt>true</tt> if and only if this list contains
* at least one element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return <tt>true</tt> if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
包含关系查询，如果包含某个指定的第一个元素，那么用前面刚刚看到的indexOf方法就可以很方便的检测到。这里的复用很灵活。
4.1.3 lastIndexOf(Object o)
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
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;
}
从列表末尾开始查询满足指定元素的第一个的位置。
与indexOf相对应的、循环方向相反的操作。
4.1.4 get()
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
获取指定下标的元素。
这两个方法比较简单。对于以元素下标为入参的查询操作，都需要首先检查下标参数。
3.3 值得注意的一些内容
1 tirmToSize()
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
减小对象数组对空间的浪费。这个方法平时都没有注意到，其实看了源码会发现也是一个很灵巧并且也足够 方便的方法。在list本身的基础长度够大的情况下，一次扩容操作可能会产生空间的浪费，所以执行了扩容操作后，可以调用该方法。
2 subList
这个方法会返回一个原集合的视图对象，注意这个视图对象是Arraylist的一个内部类。视图类的大多操作都做了modification异常检查。并且视图类的操作会影响到外部类的内容，从外部类的add、remove操作也会影响到原来的类。所以使用这个类的时候一定要谨慎。因为返回的视图并不是已有list对象的拷贝。
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
/* private class SubList extends AbstractList<E> implements RandomAccess {
* 内部类的一个视图实现
*/
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
// 原list列表拷贝
this.parent = parent;
// 下标信息拷贝
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
// 用于并发异常检查的modCCount字段
this.modCount = ArrayList.this.modCount;
}