1. 扩容
ArrayList扩容包括ensureCapacity（对外开放）和ensureCapacityInternal（内部隐式调用）两个接口：
1' 两者都调用ensureExplicitCapacity接口进行扩容
2' ensureExplicitCapacity在当前容量 < 指定的最小容量时，进行扩容
3' 扩容策略：新容量 = 旧容量 * 1.5
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认容量空数组：默认初始容量
private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组：指定容量为0
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 最大数组大小
transient Object[] elementData;
private int size;
public ArrayList() { // 未指定初始容量
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 分配默认容量空数组
}
public ArrayList(int initialCapacity) { // 指定初始容量
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity]; // 为elementData分配空间
} 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) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class); // 拷贝elementData
} else {
this.elementData = EMPTY_ELEMENTDATA; // 分配空数组
}
}
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
if (minCapacity > minExpand) { // 若elementData为默认容量空数组，则指定最小容量必须大于默认容量（10）才真正进一步扩容
ensureExplicitCapacity(minCapacity);
}
}
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// elementData为默认容量空数组，则在指定的最小容量和默认容量（10）中选择较大大者进行扩容
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); // 新容量 = 旧容量 * 1.5
if (newCapacity - minCapacity < 0) // 若刚计算出的新容量 < 指定的最小容量，则新容量 = 指定的最小容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // 新的容量 > 最大数组大小，则新容量 = 最大整数
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
... ...
}public class Arrays {
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] // Object[]类型
: (T[]) Array.newInstance(newType.getComponentType(), newLength); // 其它数组类型
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
return copy;
}
... ...
}2. 迭代器
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
... ...
public Iterator<E> iterator() {
return new Itr();
}
public ListIterator<E> listIterator() {
return new ListItr(0);
}
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
... ...
}1）ArrayList.Itr
private class Itr implements Iterator<E> {
int cursor; // 下次返回元素的位置
int lastRet = -1; // 当前返回元素的位置
int expectedModCount = modCount; // ArrayList.this.modCount
// 判断在迭代过程中是否调用过ArrayList方法修改过elementData
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
public boolean hasNext() {
return cursor != size;
}
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; // cursor++
return (E) elementData[lastRet = i]; // lastRet纪录当前返回元素的位置，cursor = lastRet + 1
}
public void remove() {
if (lastRet < 0) // 未调用过Itr.next || 未调用ListItr.previous || 已调用过Itr.remove || 已调用过ListItr.add
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet); // 删除lastRet处的元素
cursor = lastRet; // 不影响下次previous或next的调用
lastRet = -1;
expectedModCount = modCount; // ArrayList.remove方法将使modCount++
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
... ...
}2）ArrayList.ListItr
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() { // 下次调用next方法返回元素的位置
return cursor;
}
public int previousIndex() { // 下次调用previous方法返回元素的位置
return cursor - 1;
}
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i]; // lastRet纪录当前返回元素的位置，cursor = lastRet
}
public void set(E e) {
if (lastRet < 0) // 未调用Itr.next || 未调用ListItr.previous || 已调用Itr.remove || 已调用ListItr.add
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e); // 设置lastRet处的元素
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e); // 在cursor处添加新元素等价于：
// 1. 在用previous方法返回元素时：在lastRet前置位插入元素
// 2. 在用next方法返回元素时：在lastRet后置位插入元素
cursor = i + 1; // 下次调用previous方法则返回刚插入的元素，不影响下次next方法的调用
lastRet = -1;
expectedModCount = modCount; // ArrayList.add方法将使modCount++
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}