简单易懂的ArrayList源码分析
ArrayList是工作中使用频率很高的数组集合类，让我们来看看它的实现原理是什么。
ArrayList关键属性
//默认初始化容量大小private static final int DEFAULT_CAPACITY = 10;//空数组实例private static final Object[] EMPTY_ELEMENTDATA = {};//默认初始化大小的空实例，与EMPTY_ELEMENTDATA区分出来private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//ArrayList使用这个属性，Object[]数组存储它的数据transient Object[] elementData; // non-private to simplify nested class access//数组实际存储的元素个数private int size;
ArrayList的本质是一个Object[]数组。
ArrayList常用方法
首先，我们使用无参构造函数声明一个ArrayList。
List<String> list = new ArrayList(); //本质就是声明一个空数组。效果如同Object[] elementData = {}；
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
接着，使用add方法往集合中添加元素。
list.add("a");
添加一个元素需要以下步骤：
1. 计算数组所需的最小长度，应该是原数组的长度+1。如果是一个空数组，则默认取10跟原数组的长度+1中两者较大的那个。
2. 判断所需的最小长度是否大于现在的数组长度， 如果大于，需要扩充数组。
3. 创建一个新数组，大小是oldCapacity + (oldCapacity >> 1)。然后将原数组存储的内容复制到新数组，并将新数组赋值给elementData属性。
4. 往数组最后位置添加元素：elementData[size++] = e。
public boolean add(E e) {//先校验原有大小再加一个元素数组能否容纳下去，如果不能，创建一个更大的数组，并把原数组的内容复制进去ensureCapacityInternal(size + 1);//将元素添加到数组的最后一个位置elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {//数组最小容量是原数组元素个数+1ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {//如果数组里面还没有任何元素，则取【默认初始化大小10】，【最小容量】两者较大的那个if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {modCount++;// 如果所需的最小容量大于数组现在的大小，则需要对数组进行扩充if (minCapacity - elementData.length > 0)grow(minCapacity);}//扩充数组大小private void grow(int minCapacity) {//旧数组大小int oldCapacity = elementData.length;//新数组大小=旧数组大小+旧数组大小/2, 即每次扩充一半大小。int newCapacity = oldCapacity + (oldCapacity >> 1);//增大一半之后的大小如果小于需要的最小容量，则直接取最小容量的大小。if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//判断新的容量有没有超过最大值，因为数组的下标是整形，而整形的最大值是Integer.MAX_VALUE， 所以数组有大小限制if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);//创建一个新数组，并把原数组的内容复制过去elementData = Arrays.copyOf(elementData, newCapacity);}
如果我们希望将元素添加到数组指定位置，则使用
list.add(1, "b");
同add(E e)方法一样，首先校验数组的大小是否够用，如果不够用则扩大数组。
接着，将index之后的元素，复制到index+1的位置，即index之后的元素每个向后移动一位。
最后在index位置添加元素：elementData[index] = element
该方法涉及到迁移元素，需要将index位置之后的元素往后移动一位，空出index位置来插入元素，所以效率会低点。频繁往数组中间插入元素的集合，应该使用LinkedList。
public void add(int index, E element) {rangeCheckForAdd(index);//判断数组大小是否满足，不够则扩大数组ensureCapacityInternal(size + 1);//将index之后的元素，往后移动一位，空出index处的位置System.arraycopy(elementData, index, elementData, index + 1,size - index);//将元素添加到index位置elementData[index] = element;size++;}
添加元素之后，我们希望可以找出某个元素在数组中的位置，则使用
list.indexOf("b");
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;}
想要根据下标获取数组元素，则使用
list.get(i); 本质就是: 数组变量[index]
public E get(int index) {rangeCheck(index);return elementData(index);}E elementData(int index) {return (E) elementData[index];}
如果我们想删除某个元素，可以使用
list.remove("b");
同indexof方法，remove会先遍历数组，找到元素所在的位置index。然后将index之后的所有元素往前移动一位，这样子index位置就被覆盖了。再将最后那个多余的元素设置为null，size减1。
public boolean remove(Object o) {//遍历数组，一一对比找到元素所在位置indexif (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;//将数组index位置后面的元素往前移动一位if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);//清空最后一位，并将数组大小减1elementData[--size] = null; // clear to let GC do its work}
想要添加一个集合，使用
list.addAll();
addAll会将要添加的元素复制到elementData最后一个元素之后。
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);//变更sizesize += numNew;return numNew != 0;}
最后，我们可以使用clear来清空数组的元素
list.clear();
clear会遍历数组的每个元素，将每个元素设置为null，并将size置为0
public void clear() {modCount++;// 遍历数组，将每个元素设置为null，并将size设为0for (int i = 0; i < size; i++)elementData[i] = null;size = 0;}