Java 源码--ArrayList - Java | 灰灰是菇凉 = huihui.coding@gmail.com

ArrayList 类继承了 AbstractList 抽象类，AbstractList 抽象类对于一些通用的方法提供了默认实现。ArrayList 类实现了接口 List、RandomAccess、Cloneable 和 Serializable。后三者都是语义标志接口，不提供任何实现，标记这个类具有某种功能。RandomAccess 标记类具有随机访问的功能，Cloneable 标记类具有克隆功能，Serializable 标记类具有序列化功能。

ArrayList 类底层是由数组实现的，使用一个 Object [] 类型的变量来保存这个 list 的值。这个值不参与序列化，类中重写了 writeObject () 和 readObject () 方法来序列化该值。

transient Object[] elementData;

变量 size 记录值的大小。

private int size;

ArrayList 有两个构造方法 —— 有参构造方法和无参构造方法。

无参构造时，将数组列表的值赋为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

	public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
	}

有参构造时，指定容量大于 0，就构造一个指定容量大小的数组，如果指定容量为 0，就将值赋为 EMPTY_ELEMENTDATA。

	private static final Object[] 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);
	}
	}

也可以根据一个集合构造一个数组集合，将集合转为数组直接赋值给 elementData。当值大小为 0 时，就将值赋为 EMPTY_ELEMENTDATA。

	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;
	}
	}

那么，无参构造和有参构造产生的空值有什么区别呢？从表面上看来是一样的，在变量 elementData 上有这样一句注释，“添加第一个元素时，任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将扩展为 DEFAULT_CAPACITY。”

DEFAULT_CAPACITY 指定为 10。

private static final int DEFAULT_CAPACITY = 10;

注释的意思是说，无参构造产生的空值在第一次添加元素时，将容量扩展至 10。那么我们来看下 add 方法。

add 方法首先将数组容量加 1，这就涉及到了 ArrayList 的扩容机制，我们一步步来看。

	public boolean add(E e) {
	ensureCapacityInternal(size + 1);
	elementData[size++] = e;
	return true;
	}

首先，判断目前数组的值是不是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，即该数组是不是无参构造出的空数组。如果是，就取 DEFAULT_CAPACITY 和 minCapacity 的最大值，否则就扩展至指定的容量。第一次添加元素时，minCapacity 为 1，也就是说将数组扩展至 10，如果是有参构造的空数组，就扩展至 1。

	private void ensureCapacityInternal(int minCapacity) {
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
	minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
	}

	ensureExplicitCapacity(minCapacity);
	}

接下来要判断扩展的容量是否足够存放数组的值，足够存放就开始扩容工作。第一次添加元素时，数组长度为 0，可以进入扩容工作。

	private void ensureExplicitCapacity(int minCapacity) {
	modCount++;

	if (minCapacity - elementData.length > 0)
	grow(minCapacity);
	}

grow 方法是 ArrayList 扩容机制的核心，可以看出，扩容的机制是扩展原来容量的 0.5 倍。如果扩容至 1.5 倍之后依旧无法达到指定容量大小或者大小超出了 int 类型的大小，就使用指定容量进行扩容。如果扩容容量大于数组最大容量，就扩容至 Integer 类型的最大值。最后重新申请一个数组，并进行数组的复制完成扩容工作。当第一次添加元素时，就数组的容量为 0，扩容至 1 或 10。

这里有一个疑问，既然 ArrayList 是数组来保存值的，数组的容量最大是 Integer.MAX_VALUE - 8（查资料说是需要空间来保存一些头部信息），那么为什么 ArrayList 的容量还可以扩大至 Integer.MAX_VALUE 呢？

	private void grow(int minCapacity) {
	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);
	}

	private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0)
	throw new OutOfMemoryError();
	return (minCapacity > MAX_ARRAY_SIZE) ?
	Integer.MAX_VALUE :
	MAX_ARRAY_SIZE;
	}

由此可以看出，EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 就是为了区分有参构造和无参构造的空数组，从而使用不同的扩容规则。

我们可以注意到，上面方法中有一个 modCount 变量加 1 的操作。这个变量是从父类 AbstractList 中继承来的，它标记一个 list 被修改的次数。它主要是为了在迭代器中判断 list 是否被其他操作改变，进入迭代器会保存一个 modCount 值的副本，如果 modCount 的值变了，就抛出异常。

protected transient int modCount = 0;

方法 trimToSize 将数组中多余容量释放。当使用容量小于数组容量时，如果使用容量为 0，将数组设为空值，否则重新生成一个长度为 size 的数组。

	public void trimToSize() {
	modCount++;
	if (size < elementData.length) {
	elementData = (size == 0)
	? EMPTY_ELEMENTDATA
	: Arrays.copyOf(elementData, size);
	}
	}

size 方法可以获取 list 的大小。

	public int size() {
	return size;
	}

isEmpty 方法判断 list 是否为空，即 size 是否为 0.

	public boolean isEmpty() {
	return size == 0;
	}

contains 方法判断数组是否包含参数。如果参数 o 在数组的位置不小于 0，就说明数组中存在参数。

	public boolean contains(Object o) {
	return indexOf(o) >= 0;
	}

indexOf 方法判断参数在数组中的位置。如果参数 o 为 null，那么在数组中找到一个 null 值的位置就好，不为空就是用 equals 方法找到数组中 o 的位置，找不到就返回 - 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 方法从后往前遍历，判断参数在数组中的位置。

	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;
	}

clone 方法克隆一个 list。注意，该克隆是浅克隆，数组元素并没有复制。

	public Object clone() {
	try {
	ArrayList<?> v = (ArrayList<?>) super.clone();
	v.elementData = Arrays.copyOf(elementData, size);
	v.modCount = 0;
	return v;
	} catch (CloneNotSupportedException e) {
	throw new InternalError(e);
	}
	}

toArray 方法将 list 转为数组。如果参数 a 的长度不够容纳 list 元素，就重新生成一个数组，否则就直接复制元素。a 中有空余位置的话将 size 位置置为 null。

	public Object[] toArray() {
	return Arrays.copyOf(elementData, size);
	}

	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] a) {
	if (a.length < size)
	return (T[]) Arrays.copyOf(elementData, size, a.getClass());
	System.arraycopy(elementData, 0, a, 0, size);
	if (a.length > size)
	a[size] = null;
	return a;
	}

get 方法返回指定位置的元素。首先检查 index 是否越界，然后返回数组 index 位置的元素。

	public E get(int index) {
	rangeCheck(index);

	return elementData(index);
	}

	@SuppressWarnings("unchecked")
	E elementData(int index) {
	return (E) elementData[index];
	}

	private void rangeCheck(int index) {
	if (index >= size)
	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	}

set 方法设置指定位置的元素。首先检查 index 是否越界，然后拿到 index 位置的旧值，将 index 位置的值设为新值，最后返回旧值。

	public E set(int index, E element) {
	rangeCheck(index);

	E oldValue = elementData(index);
	elementData[index] = element;
	return oldValue;
	}

add 方法向 list 中添加元素。不指定元素添加位置时默认添加到数组末尾，首先确保数组的容量，然后在数组后面添加一个元素，最后返回 true。指定元素添加位置时，首先检查指定位置是否越界，然后确保数组的容量，然后将 index 以及之后的元素向后移动一位，将 index 位置设为指定元素，最后返回 true。

	public boolean add(E e) {
	ensureCapacityInternal(size + 1);
	elementData[size++] = e;
	return true;
	}

	public void add(int index, E element) {
	rangeCheckForAdd(index);

	ensureCapacityInternal(size + 1);
	System.arraycopy(elementData, index, elementData, index + 1,
	size - index);
	elementData[index] = element;
	size++;
	}

	private void rangeCheckForAdd(int index) {
	if (index > size \|\| index < 0)
	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	}

remove 方法移除指定位置的元素或移除指定元素。当指定的是元素位置时，先检查指定位置是否越界，然后获取指定位置的旧值，将指定位置之后的元素向前移动一个位置，然后将最后一位设为 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;
	return oldValue;
	}

	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 方法清除 list 中的元素。将数组中的每个元素设为 null，并将大小设为 0。

	public void clear() {
	modCount++;

	for (int i = 0; i < size; i++)
	elementData[i] = null;

	size = 0;
	}

addAll 方法向 list 中添加集合。不指定位置时，默认向末尾添加集合元素。

	public boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray();
	int numNew = a.length;
	ensureCapacityInternal(size + numNew);
	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);

	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;
	}

removeAll 方法移除指定集合中的所有元素，retainAll 方法保留指定集合中的所有元素。这两个方法类似，只是逻辑是反的，Java 设计者很巧妙的运用了一个 boolean 类型的参数来区分两种逻辑，以便使同一个方法。在 try 中的 for 循环就已经将需要留下的元素放到了数组的前一部分，即 w 位置之前。注释说 contains 方法可能会有异常，当异常发生，就将没有遍历到的元素全部留下，这个逻辑我也不太明白。最后将 w 位置之后的元素设为 null，返回布尔值。

	public boolean removeAll(Collection<?> c) {
	Objects.requireNonNull(c);
	return batchRemove(c, false);
	}

	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;
	}

forEach 方法可以使用 lambda 表达对每一个元素进行相同的操作。在操作之前，会先拿到数组修改的次数，然后重新申请一个与 list 数组元素相同的数组进行操作。注意，此复制是浅复制，两个数组共用一套元素。最后判断 list 是否被其他操作改变了，如果被改变了就抛出异常。

	@Override
	public void forEach(Consumer<? super E> action) {
	Objects.requireNonNull(action);
	final int expectedModCount = modCount;
	@SuppressWarnings("unchecked")
	final E[] elementData = (E[]) this.elementData;
	final int size = this.size;
	for (int i=0; modCount == expectedModCount && i < size; i++) {
	action.accept(elementData[i]);
	}
	if (modCount != expectedModCount) {
	throw new ConcurrentModificationException();
	}
	}

removeIf 方法移除掉满足参数条件的元素。首先将满足参数条件的元素的位置放到一个 set 集合中，然后再遍历将其重新整合。

	@Override
	public boolean removeIf(Predicate<? super E> filter) {
	Objects.requireNonNull(filter);
	int removeCount = 0;
	final BitSet removeSet = new BitSet(size);
	final int expectedModCount = modCount;
	final int size = this.size;
	for (int i=0; modCount == expectedModCount && i < size; i++) {
	@SuppressWarnings("unchecked")
	final E element = (E) elementData[i];
	if (filter.test(element)) {
	removeSet.set(i);
	removeCount++;
	}
	}
	if (modCount != expectedModCount) {
	throw new ConcurrentModificationException();
	}

	final boolean anyToRemove = removeCount > 0;
	if (anyToRemove) {
	final int newSize = size - removeCount;
	for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
	i = removeSet.nextClearBit(i);
	elementData[j] = elementData[i];
	}
	for (int k=newSize; k < size; k++) {
	elementData[k] = null;
	}
	this.size = newSize;
	if (modCount != expectedModCount) {
	throw new ConcurrentModificationException();
	}
	modCount++;
	}

	return anyToRemove;
	}

replaceAll 方法对数组的每个元素执行传入方法。

	@Override
	@SuppressWarnings("unchecked")
	public void replaceAll(UnaryOperator<E> operator) {
	Objects.requireNonNull(operator);
	final int expectedModCount = modCount;
	final int size = this.size;
	for (int i=0; modCount == expectedModCount && i < size; i++) {
	elementData[i] = operator.apply((E) elementData[i]);
	}
	if (modCount != expectedModCount) {
	throw new ConcurrentModificationException();
	}
	modCount++;
	}

sort 方法使用传入的比较方法对数组进行排序。

	@Override
	@SuppressWarnings("unchecked")
	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++;
	}

ArrayList 拥有自己的两种迭代器，Itr 和 ListItr。

Itr 实现了接口 Iterator，定义了三个变量，cursor，代表下一个元素的位置，lastRet，代表上一个元素的位置，expectedModCount，数组之前的修改次数。

	int cursor;
	int lastRet = -1;
	int expectedModCount = modCount;

Itr 迭代器有 4 个方法，hasNext ()，next ()，remove ()，forEachRemaining ()。

hasNext 方法判断可以向后迭代。

	public boolean hasNext() {
	return cursor != size;
	}

next 方法返回下一个元素，并将 cursor 和 lastRet 向前移动一个位置。

	@SuppressWarnings("unchecked")
	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;
	return (E) elementData[lastRet = i];
	}

remove 方法移除掉上一个遍历过的元素，并将 cursor 指向上一个元素的位置，将 lastRet 设为 - 1。

	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();
	}
	}

forEachRemaining 方法遍历所有剩下的元素。在使用 Iterator 迭代器使用 next 方法循环 list，如果没有循环完整个 list，可以使用该方法循环完整个 list。

	@Override
	@SuppressWarnings("unchecked")
	public void forEachRemaining(Consumer<? super E> 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++]);
	}

	cursor = i;
	lastRet = i - 1;
	checkForComodification();
	}

	final void checkForComodification() {
	if (modCount != expectedModCount)
	throw new ConcurrentModificationException();
	}

ListItr 继承了 Itr 类，实现了接口 ListIterator。除了提供了一个构造方法之外，还添加了向前遍历的方法。

ListItr 的构造方法可以为迭代器指定开始迭代的位置。

	ListItr(int index) {
	super();
	cursor = index;
	}

hasPrevious 方法判断是否可以向前迭代。

	public boolean hasPrevious() {
	return cursor != 0;
	}

nextIndex 方法返回下一个迭代元素的位置。

	public int nextIndex() {
	return cursor;
	}

previousIndex 方法返回前一个迭代元素的位置。

	public int previousIndex() {
	return cursor - 1;
	}

previous 方法返回前一个迭代的元素。

	@SuppressWarnings("unchecked")
	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];
	}

set 方法设置上一个遍历过的元素值为 e。

	public void set(E e) {
	if (lastRet < 0)
	throw new IllegalStateException();
	checkForComodification();

	try {
	ArrayList.this.set(lastRet, e);
	} catch (IndexOutOfBoundsException ex) {
	throw new ConcurrentModificationException();
	}
	}

add 方法向 cursor 位置添加一个元素，并将 cursor 指向下一个位置，将 lastRet 设为 - 1。

	public void add(E e) {
	checkForComodification();

	try {
	int i = cursor;
	ArrayList.this.add(i, e);
	cursor = i + 1;
	lastRet = -1;
	expectedModCount = modCount;
	} catch (IndexOutOfBoundsException ex) {
	throw new ConcurrentModificationException();
	}
	}

接下来就是一个子列表 SubList。

SubList 继承 AbstractList 抽象类，实现 RandomAccess 接口，有四个属性，在构造方法中可以看出这四个属性的意义。

	private final AbstractList<E> parent;
	private final int parentOffset;
	private final int offset;
	int size;

parent 就是母列表，parentOffset 是母列表的偏移，offset 是子列表相对于母列表的偏移，size 是子列表的大小，同时记录了母列表被修改的次数。

	SubList(AbstractList<E> parent,
	int offset, int fromIndex, int toIndex) {
	this.parent = parent;
	this.parentOffset = fromIndex;
	this.offset = offset + fromIndex;
	this.size = toIndex - fromIndex;
	this.modCount = ArrayList.this.modCount;
	}

SubList 提供了列表简单的操作，set，get，size，add，remove，removeRange，addAll，iterator，listIterator 等方法。注意，这些方法虽然在子列表调用的，但是都是直接操作母列表对应位置的元素的。比如 set 方法，会去修改母列表元素 offset+index 位置的元素的值。

	public E set(int index, E e) {
	rangeCheck(index);
	checkForComodification();
	E oldValue = ArrayList.this.elementData(offset + index);
	ArrayList.this.elementData[offset + index] = e;
	return oldValue;
	}

ArrayList 使用 subList 方法返回列表的子列表。注意，如果修改子列表的元素，母列表的元素也会被修改。

	public List<E> subList(int fromIndex, int toIndex) {
	subListRangeCheck(fromIndex, toIndex, size);
	return new SubList(this, 0, fromIndex, toIndex);
	}

最后，ArrayList 还有一个内部类 ArrayListSpliterator，这个以后再研究吧，目前有些看不懂。

IDEA Maven项目导入本地jar包

Java 源码--LinkedList