本文将从源码级别研究集合中的ArrayList，这里研究的是jdk8的源码，我们只关注一些常用的方法。我们从其构造方法入手。
构造方法：
//构造一个初始化容量为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 c) {
//将传入的集合转为数组，放入存有ArrayList元素的数组缓冲区
elementData = c.toArray();
if ((size = elementData.length) != 0) { //传入的集合中有元素
if (elementData.getClass() != Object[].class)
//这一步保证c.toArray()转化出来数组是Object[]类型。
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//传入的集合是空集合，此时elementData 替换为空数组。
this.elementData = EMPTY_ELEMENTDATA;
}
}
添加元素之set(int,E)方法，在指定索引位置添加
//将指定索引位置index的元素替换为element
public E set(int index, E element) {
//检查给定的索引是否在范围内
rangeCheck(index);
//保存旧值
E oldValue = elementData(index);
//替换索引位置为index处的元素为element
elementData[index] = element;
//将旧值即被替换的元素返回。
return oldValue;
}
//这个方法不检查索引为负，总是在数组访问前立即调用。索引为负时，抛出ArrayIndexOutOfBoundsException
private void rangeCheck(int index) {
if (index >= size)
//索引越界，抛出IndexOutOfBoundsException
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
添加元素之add(E)方法，从集合尾部添加
//在list集合尾部追加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算容量，当添加第一个元素时，任何具有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将扩展为 DEFAULT_CAPACITY，若不是空的ArrayList则返回minCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //这里代表是
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 传入的最小容量超出当前elementData的长度，需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
扩容方法grow(int ):
//扩容来保证能容纳最小容量的元素数
private void grow(int minCapacity) {
// 保存原数据的长度
int oldCapacity = elementData.length;
// 扩容后的容量为原来的1.5倍，oldCapacity >> 1相当于原来的容量除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
//扩容后的容量仍然比传入的minCapacity小，则将minCapacity作为扩容后的容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//扩容后的容量超过了要分配数组的最大大小Integer.MAX_VALUE - 8
//此时若minCapacity > MAX_ARRAY_SIZE 则扩容后的容量为Integer.MAX_VALUE，否则为Integer.MAX_VALUE - 8
newCapacity = hugeCapacity(minCapacity);
// minCapacity 通常与数组大小接近
//最终扩容为newCapacity容量大小的数组
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;
}
指定索引位置添加元素
//按指定索引位置index添加元素element
public void add(int index, E element) {
rangeCheckForAdd(index);
//确保扩容后的数组容量为size+1
ensureCapacityInternal(size + 1);
//数组中的元素从索引位置index处后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//指定索引位置放入要添加的元素element
elementData[index] = element;
//数组长度加1
size++;
}
//索引位置大于数组大小或索引位置小于0；抛出IndexOutOfBoundsException
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
返回此列表中第一次出现的指定元素的索引indexOf(Object)：
//返回此列表中第一次出现的指定元素的索引
public int indexOf(Object o) {
if (o == null) { //指定元素为null
for (int i = 0; i < size; i++) //遍历
if (elementData[i]==null) //一旦找到列表中第一个为null的元素，返回其下标
return i;
} else { //指定元素非空
for (int i = 0; i < size; i++) //遍历
if (o.equals(elementData[i])) //一旦找到列表中的指定元素，返回其下标
return i;
}
return -1;
}
lastIndexOf方法是从后往前遍历我们在这就不看了。
trimToSize方法将ArrayList的容量大小修改为list的当前大小
public void trimToSize() {
modCount++;
if (size < elementData.length) { //ArrayList中实际包含的元素数量小于分配的数组的容量
//实际的元素数量为0时直接分配一个空数组，不为0时按实际包含的元素数量进行分配
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
接下来我们看一下上面的这个迭代器：
//返回listIterator（0） public ListIteratorlistIterator() { return listIterator(0); } //按正确的顺序返回列表中的迭代器 public ListIterator listIterator(final int index) { //index < 0 或者 index > size() 抛出IndexOutOfBoundsException rangeCheckForAdd(index); //构建List return new ListItr(index); } //ListItr 类继承了Itr实现了ListIterator接口 private class ListItr extends Itr implements ListIterator { ListItr(int index) { //初始化cursor 为index cursor = index; } //此列表元素反向遍历列表时，有更多元素则返回true public boolean hasPrevious() { return cursor != 0; } //返回下一位置元素的索引，若list迭代器位于列表末尾，则返回列表大小 public int nextIndex() { return cursor; } //返回前一位置元素的索引，若list迭代器位于列表开头返回-1 public int previousIndex() { return cursor - 1; } @SuppressWarnings("unchecked") //用于逆向遍历 public E previous() { //并发修改检查，若不是预期的modCount则抛出ConcurrentModificationException checkForComodification(); //记录前一个（也即下一个）元素位置的光标 int i = cursor - 1; if (i < 0) //前一位置没有元素 throw new NoSuchElementException(); //初始化elementData 为ArrayList的elementData Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) //前一个元素的索引大于等于数据的长度，抛出ConcurrentModificationException throw new ConcurrentModificationException(); //光标移到下一个元素的位置 cursor = i; //将最后一个位置的索引指向下一个元素，并返回下一个元素。 return (E) elementData[lastRet = i]; } ...... }
迭代器iterator()迭代遍历
public Iteratoriterator() { return new Itr(); } private class Itr implements Iterator { int cursor; // 下一个元素的索引 int lastRet = -1; // 最后一个元素的索引，没有返回-1 int expectedModCount = modCount; //迭代包含更多元素，返回true；换句话说next返回元素而不是抛出异常，返回true public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); //记录下一个元素索引 int i = cursor; if (i >= size) //下一个元素大于等于list的实际数量，即没有这个元素 throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) //下一个元素的索引超出了存储ArrayList元素的数组缓冲区的长度，存在并发操作 throw new ConcurrentModificationException(); //光标后移 cursor = i + 1; //下一个元素变为最后一个元素，并返回下一个元素 return (E) elementData[lastRet = i]; } //删除指定位置的元素，并将后续元素向左移动 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(); } } @Override @SuppressWarnings("unchecked") //对每个剩余元素执行给定的操作，直到所有元素都已处理或该操作引发异常 public void forEachRemaining(Consumer consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { //没有剩余元素 return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { //有剩余元素且不存在并发操作 //剩余元素执行给定操作 consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); } //ArrayList提供的fail-fast快速失败机制，集合遍历过程中结构发生了改变触发fail-fast，抛出ConcurrentModificationException final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
