一文了解Java ArrayList （源码逐行解析）
介绍
ArrayList 是最常用的 List 实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。当从 ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。 ArrayList继承于AbstractList类，实现了List接口；他是一个数组队列，提供了相关的添加、删除、遍历的功能。 ArrayList实现了RandomAccess接口，说明其提供了随机访问的功能；RandomAccess接口是一个标记接口，用以标记实现的List集合具备快速随机访问的能力。所有的List实现都支持随机访问的，只是基于基本结构的不同，实现的速度不同罢了，这里的快速随机访问，那么就不是所有List集合都支持了。 ArrayList基于数组实现，数组带下标，可以实现常量级的随机访问，复杂度O(1). LinkedList基于链表实现，随机访问需要依靠遍历实现，复杂度为O(n) ArrayList实现了Serializable接口，这意味着ArrayList 支持序列化，能通过序列化去传输。 ArrayList实现了Cloneable接口，能被克隆。 其于Vector不同的是Vector是线程安全的，因此建议在单线程中才使用ArrayList，多线程中使用Vector。
结构图
源码逐行分析
属性
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{private static final long serialVersionUID = 8683452581122892189L;/*** 默认初始化容量*/private static final int DEFAULT_CAPACITY = 10;/*** 共享的空对象*/private static final Object[] EMPTY_ELEMENTDATA = {};/***一个空对象，如果使用默认构造函数创建，则默认对象内容默认是该值；区分上面的EMPTY_ELEMENTDATA，这个第一次添加add时会膨胀（扩容长度为10）*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** 保存添加到ArrayList中的元素。 * ArrayList的容量就是该数组的长度。 * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入* ArrayList中时，数组将扩容值DEFAULT_CAPACITY。 * 被标记为transient，在对象被序列化的时候不会被序列化。*/transient Object[] elementData; // non-private to simplify nested class access/*** 数组长度* @serial*/private int size;/*** 最大数组容量*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;复制代码有参构造函数
带int的有参
如果参数大于0则建立参数大小容量的数组 如果参数等于0则建立空数组 其它非法情况，抛异常
/*** 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);}}
复制代码带Collection对象的有参构造函数
如果Collection的长度大于0且Collection的类型为ArrayList.class，则直接赋值给成员属性elementData 如果Collection的长度大于0且Collection的类型不为ArrayList.class，则利用Arrays.copyOf方式赋值给elementData 如果Collection的长度等于0，则直接创建空数组
/*** 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) {Object[] a = c.toArray();if ((size = a.length) != 0) {if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData = EMPTY_ELEMENTDATA;}}
复制代码无参构造函数
使用默认的空数组
/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}复制代码方法
trimToSize
trimToSize() 方法用于将动态数组中的容量调整为数组中的元素个数。
public void trimToSize() {modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}
复制代码ensureCapacity
同样是修改动态数组的大小，但入参是最小容量。
public void ensureCapacity(int minCapacity) {int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)// any size if not default element table? 0// larger than default for default empty table. It's already// supposed to be at default size.: DEFAULT_CAPACITY;if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);}}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious codeint 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);}
复制代码size
public int size() {return size;}
复制代码isEmpty
public boolean isEmpty() {return size == 0;}
复制代码contains
如果传null，会返回第一个元素为null的索引； 如果传值，会返回第一个元素为该值的索引； 否则返回-1
public boolean contains(Object o) {return indexOf(o) >= 0;}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
如果传null，会返回最后一个元素为null的索引； 如果传值，会返回最后一个元素为该值的索引； 否则返回-1
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
利用Arrays.copyOf创建新的动态数组
public Object clone() {try {ArrayList<?> v = (ArrayList<?>) super.clone();v.elementData = Arrays.copyOf(elementData, size);v.modCount = 0;return v;} catch (CloneNotSupportedException e) {// this shouldn't happen, since we are Cloneablethrow new InternalError(e);}}
复制代码get
public E get(int index) {rangeCheck(index);return elementData(index);}//检查下标是否越界private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
复制代码set
确保set的位置小于当前数组的长度（size）并且大于0，获取指定位置（index）元素，然后放到oldValue存放，将需要设置的元素放到指定的位置（index）上，然后将原来位置上的元素oldValue返回给用户。
public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}//检查下标是否越界private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
复制代码add（在末尾添加元素）
在数组的末尾添加元素 总结：
- 按顺序添加元素
- 如果数组容量不足，则至少扩容到原数组容量的1.5倍
- 如果扩容后大于Integer.MAX_VALUE - 8，则直接把新的数组设置容量为Integer的最大值
public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private void ensureExplicitCapacity(int minCapacity) {//记录修改次数+1modCount++;// overflow-conscious code//如果当前数组容量不足则调用grow方法扩容if (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious code//记录旧数组的长度int oldCapacity = elementData.length;//新数组的长度为旧数组的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容后还小于入参，则直接赋值为入参if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//如果大于Integer.MAX_VALUE - 8，则设置为Integer的最大值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) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}
复制代码add（在指定位置添加元素）
public void add(int index, E element) {//检查入参合法性rangeCheckForAdd(index);//检查并进行扩容ensureCapacityInternal(size + 1); // Increments modCount!!//从index索引开始，所有元素向后挪一位，为新元素腾出位置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));}
复制代码add（添加一个集合元素）
将新数组中的元素按顺序添加到数组末尾
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（在指定位置添加集合元素）
public boolean addAll(int index, Collection<? extends E> c) {//检查参数合法性rangeCheckForAdd(index);Object[] a = c.toArray();int numNew = a.length;//检查容量并扩容ensureCapacityInternal(size + numNew); // Increments modCountint numMoved = size - index;//元素向后挪numNew位if (numMoved > 0)System.arraycopy(elementData, index, elementData, index + numNew,numMoved);//将新的集合添加到数组中System.arraycopy(a, 0, elementData, index, numNew);size += numNew;return numNew != 0;}复制代码remove（删除指定位置的元素）
public E remove(int index) {//检查索引合法性rangeCheck(index);modCount++;E oldValue = elementData(index);int numMoved = size - index - 1;//如果索引不是在数组末尾，则从索引index+1开始，每个元素往前挪一位if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);//设置末尾元素为nullelementData[--size] = null; // clear to let GC do its workreturn oldValue;}
复制代码remove（删除指定元素）
public boolean remove(Object o) {if (o == null) {//删除数组中为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;}//index+1索引开始的元素往前挪一位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}
复制代码removeAll
从该列表中删除指定集合中包含的所有元素
public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, 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++)// complement为true时，求并集；complement为false时，求差集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;}if (w != size) {// clear to let GC do its workfor (int i = w; i < size; i++)elementData[i] = null;modCount += size - w;size = w;modified = true;}}return modified;}
复制代码retainAll
仅保留此列表中包含在指定集合中的元素。
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++)// complement为true时，求并集；complement为false时，求差集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;}if (w != size) {// clear to let GC do its workfor (int i = w; i < size; i++)elementData[i] = null;modCount += size - w;size = w;modified = true;}}return modified;}