ArrayList底层基于数组实现容量大小动态变化，允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口，所以ArrayList 是支持快速访问、复制、序列化的。在频繁插入和删除场景中其性能不如LinkedList。
【1】核心属性和构造
① 核心属性
// 默认初始化数组大小 private static final int DEFAULT_CAPACITY = 10; //空的数组实例 private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //存储实际元素的数组 transient Object[] elementData; //实际元素的个数 private int size; //数组的最大容量 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
② 构造函数
实例化时指定初始化大小
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 是DEFAULTCAPACITY_EMPTY_ELEMENTDATA而不是EMPTY_ELEMENTDATA。
public ArrayList() { this.elementData = DEFAULTCAPACITY_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; } }
【2】核心方法实现
① add(E e)
代码如下所示，size表示实际元素的个数elementData[size++] = e表示先往elementData[size]位置放上e元素，然后size+=1
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
ensureCapacityInternal用来确保数组的大小，必要时会引起数组扩容。
private void ensureCapacityInternal(int minCapacity) { // minCapacity 最小为1 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }
ensureExplicitCapacity确保明确的容量，也就是判断minCapacity是否会导致扩容。如果会则触发grow引起扩容。
private void ensureExplicitCapacity(int minCapacity) { // modCount用来记录结构的改变，在fail-fast机制会用到 modCount++; // overflow-conscious code //如果溢出了，则扩容数组 if (minCapacity - elementData.length > 0) grow(minCapacity); }
② 数组的扩容
grow用来实现数组的扩容，默认是1.5倍扩容。即oldData*1.5=newData。
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // 1.5倍扩容 int newCapacity = oldCapacity + (oldCapacity >> 1); //如果newCapacity 小于minCapacity ，则重新赋值 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //如果newCapacity大于MAX_ARRAY_SIZE，则赋予Integer.MAX_VALUE 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); }
hugeCapacity是用来确定最大值的。如果容量大于MAX_ARRAY_SIZE那么就返回 Integer.MAX_VALUE，否则就采用MAX_ARRAY_SIZE。
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
③ 指定位置添加元素
public void add(int index, E element) { rangeCheckForAdd(index); //这个逻辑同上，需要注意的是会导致modCount++ ensureCapacityInternal(size + 1); // Increments modCount!! //size - index 也就是目标位置到最后的个数 //目标位置元素及后，往后顺延一个位置 System.arraycopy(elementData, index, elementData, index + 1, size - index); //index位置放上目标元素 elementData[index] = element; //总个数+1 size++; }
rangeCheckForAdd用来判断目标位置是否存在，不存在则抛出IndexOutOfBoundsException异常。
private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
如下这行代码会把index开始 (size-index)个数据，移动到index + 1位置及后续位置。
System.arraycopy(elementData, index, elementData, index + 1,size - index);
④ 获取元素
由于底层是数组，则根据index查找十分高效。
public E get(int index) { rangeCheck(index); return elementData(index); }
rangeCheck会判断index是否合适，不合适抛出IndexOutOfBoundsException异常。
private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
⑤ 移除指定位置元素
移除指定位置元素同样是导致结构发生了变化，modCount将会+1。
public E remove(int index) { //检测index是否合法 rangeCheck(index); //结构变化计数器+1 modCount++; //获取移除的元素 E oldValue = elementData(index); //计算需要移动的元素个数 int numMoved = size - index - 1; //数组拷贝 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); //数组的最后一个位置置为null elementData[--size] = null; // clear to let GC do its work //返回旧值--移除的那个元素 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; }
fastRemove方法如下所示，其与remove(int index)很类似，不过不再检测index，也不再获取index位置的对象。
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 }
