一、概述
ArrayList是java中十分常用的集合类，继承于AbstractList，并实现了List、RandomAccess、Cloneable和Serializable接口。ArrayList底层是使用数组来实现的，是一个动态的数组队列，它具有以下特点。
- 可以动态扩容、缩容
- ArrayList的操作不是线程安全的
- 允许元素重复，允许元素为空
ArrayList初始默认大小是10，每次扩容时是原大小的1.5倍，如果一开始就知道需要的Lsit长度，可以指定ArrayList的长度，减少扩容操作。
二、源码分析(JDK 1.8)
2.1 ArrayList属性
// 默认的容量
private static final int DEFAULT_CAPACITY = 10;
// 保存ArrayList中数据使用的数组
transient Object[] elementData
// ArrayList的元素个数
private int size;
此外还有一个成员变量modCount，这个变量用来记录修改次数，增删改的都会改变modCount的值。ArrayList是线程不安全的，如果在使用迭代器的过程中有其他线程修改了List，那么将抛出ConcurrentModificationException，是Fail-Fast策略的应用。
2.2 构造函数
// 构造一个初始容量为10的空列表
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 构造具有指定容量的空列表
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);
}
} // 构造一个包含指定容器元素的列表，按照容器迭代器返回的顺序排列
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;
}
}
ArrayList有三个构造函数，如上代码所示。
2.3 trimToSize()
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
trimToSize()方法可以将ArrayList的底层数组缩容到当前ArrayList中元素的个数(ArrayList的size值)，使用这个方法可以最小化ArrayList使用的存储空间。
2.4 添加
// 在列表尾部添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 在指定位置添加指定元素
public void add(int index, E element) {
rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
// 将集合c中元素添加到列表尾部
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;
}
add方法中都用到了ensureCapacityInternal方法，这个方法用于对ArrayList进行扩容。
2.5 扩容
// 扩容操作
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
} ensureExplicitCapacity(minCapacity);
} private void ensureExplicitCapacity(int minCapacity) {
modCount++; // overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 增加容量，使列表可以的容量至少满足minCapacity个元素
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);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
ensureExplicitCapacity()方法先判断当前数组的容量是否可以满足需求，如果不满足就使用grow进行扩容操作，每次扩容为原来的1.5倍。
2.6 删除
// 删除指定位置的元素，并返回被删除的元素
public E remove(int index) {
// 范围检查
rangeCheck(index); modCount++;
E oldValue = elementData(index);
// 需要移动的元素数
int numMoved = size - index - 1;
if (numMoved > 0)
// 等于0表示删除的是末尾的元素，不需要移动
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work return oldValue;
}
E remove(int index) 删除指定位置的元素
// 范围检查
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
删除前进行边界检查
// 删除列表中首次出现的指定元素，如果有多个只删除第一个
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 void fastRemove(int index) {
modCount++;
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
}
public boolean remove(Object o) 删除首次出现的指定元素，若有多个只删除第一个
// 删除指定范围的元素
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved); // clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
void removeRange(int fromIndex, int toIndex) 删除[fromIndex, toIndex)范围的元素
// 从列表中删除指定集合c中的元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
// 列表中保留指定集合c中的元素
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
// 从List的底层数组中删除或者保留指定集合中元素的值，complement为true是保留指定集合元素，为false是删除指定集合元素
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 {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// w==size表示全部元素保留，没有删除操作发生，否则返回true,并更改数组
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w; //新的大小为剩下元素的个数
modified = true;
}
}
return modified;
}
在try块中首先遍历数组，如果要保留集合c中的元素就把相同元素移到数组前段，如果要删除集合c中的数据就把不同元素移到数组前段，将剩下的数据保存在0到w之间，
第一个if语句是为了处理c.contains()抛出异常时执行；第二个if语句是处理w之后的空间。