ArrayList是Java开发中使用比较频繁的一个类，通过对源码的解读，可以了解ArrayList的内部结构以及实现方法，清楚它的优缺点，以便我们在编程时灵活运用。

目录

ArrayList

源码分析

类结构

成员变量

几个构造方法 

常用方法

总结

---

ArrayList

源码分析

类结构

ArrayList 实现于 List、RandomAccess 接口。可以插入空数据，也支持随机访问。

 JDK1.8源码中的ArrayList类结构定义如下：

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
}

其中：

1. 实现了List接口是一个数组队列拥有了List基本的增删改查功能；
2. 实现了RandomAccess接口拥有随机读写的功能，RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。稍后，我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率
3. 实现了Cloneable接口，即覆盖了函数clone()，可以被克隆；
4. 实现了Serializable接口并重写了序列化和反序列化方法，使得ArrayList可以拥有更好的序列化的性能；

和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。

成员变量

serialVersionUID

定义序列化ID，主要是为了表示不同版本兼容性。

    private static final long serialVersionUID = 8683452581122892189L;

DEFAULT_CAPACITY 

默认的数组存储容量（ArrayList底层是数组结构），初始容量。

    /*** Default initial capacity.*/private static final int DEFAULT_CAPACITY = 10;

EMPTY_ELEMENTDATA

当指定数组的容量为0时，使用这个常量进行赋值（初始化）。

   /*** Shared empty array instance used for empty instances.*/private static final Object[] EMPTY_ELEMENTDATA = {};

DEFAULTCAPACITY_EMPTY_ELEMENTDATA

默认无参构造函数时，使用这个常量进行赋值（初始化）。

    /*** Shared empty array instance used for default sized empty instances. We* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when* first element is added.*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

elementData

真正存放数据的对象数组，transient 标识不被序列化。

    /*** The array buffer into which the elements of the ArrayList are stored.* The capacity of the ArrayList is the length of this array buffer. Any* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA* will be expanded to DEFAULT_CAPACITY when the first element is added.*/transient Object[] elementData; // non-private to simplify nested class access

size

数组中真实元素的个数，该值小于或者等于 elementData.length。

   /*** The size of the ArrayList (the number of elements it contains).** @serial*/private int size;

几个构造方法 

ArrayList相当于动态数据，其中最重要的两个属性分别是: elementData 数组，以及 size 大小。

带int类型的构造函数

ArrayList(int initialCapacity)

构造函数一：构造具有指定初始容量的空列表，指定了容量的大小。

    /*** 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);}}

分析：

1. 如果初始容量>0，就初始 存放数据的 数组对象 elementData；
2. 如果初始容量=0，就初始 上面的 EMPTY_ELEMENTDATA 空数组；

无参构造函数

 ArrayList()

构造函数二：默认无参构造函数，初始化长度为 10。

    /*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

带Collection对象的构造函数

ArrayList(Collection<? extends E> c)

构造函数三：传入集合参数的构造函数。

构造一个包含指定元素的列表集合，按迭代器返回的顺序。

    /*** 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) {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;}}

分析：

将传入的 集合 转成 Array。

1. 将 默认 常量长度 Size 赋值成 传入数组的长度，判断是否为空；
2. 若 长度为 0，则 初始化一个 空数组  EMPTY_ELEMENTDATA；
3. 若 长度大于 0，判断这个 类是否是 Object，然后 根据 长度 和类型 将传入的 LIst，通过 Arrays.copyOf()方法赋值到elementData。

常用方法

增加元素

boolean add(E e)

在调用 add() 方法的时候，将指定的元素追加到此列表的末尾：

    /*** Appends the specified element to the end of this list.** @param e element to be appended to this list* @return <tt>true</tt> (as specified by {@link Collection#add})*/public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}

在 扩容之前 会 调用 以下方法，为了 确保本身内部存储容量

void ensureCapacityInternal(int minCapacity)

/*** 确保 容量大小*/private void ensureCapacityInternal(int minCapacity) {// 确保最终容量（先 计算容量大小）ensureExplicitCapacity(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++;// overflow-conscious code// 判断数组真实元素个数加1后的长度与当前数组长度大小关系// 如果小于0，返回，如果大于0，则调用grow（minCapacity）方法if (minCapacity - elementData.length > 0)grow(minCapacity);}

添加元素主要做的功能就是进行扩容校验，将插入的值放到尾部，并将 size + 1。

    /*** Default initial capacity.*/private static final int DEFAULT_CAPACITY = 10;

从0开始和默认值比较，如果大于 10，则用 size+1。

add(E e) 方法总结：

1. 先判断容量；
2. 再讲新增的值赋给索引+1的数组；
3. 最终return true；

add(E e)分析：

1. ensureCapacityInternal（size+1）方法，在该方法中首先判断了当前数组是否是空数组，如果是则比较加入的个数与默认个数(10)比较，取较大值，否则调用2方法。
2. ensureExplicitCapacity(int minCapacity)方法，在该方法中首先是对modCount+1，判断数组真实元素个数加1后的长度与当前数组长度大小关系，如果小于0，返回，如果大于0，则调用3方法。
3. grow(minCapacity)方法，使用 oldCapacity + (oldCapacity >> 1)是当前数组的长度变为原来的1.5倍，再与扩容后的长度以及扩容的上限值进行对比，然后调用4方法。
4. Arrays.copyOf(elementData, newCapacity)方法，该方法的底层就是调用

   System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));

   方法，把旧数据的数据拷贝到扩容后的新数组里面，返回新数组。
5. 然后再把新添加的元素赋值给扩容后的size+1的位置里面。

根据索引增加方法

void add(int index, E element)

如果是调用 add(index,e) 在指定位置添加的话，将指定元素插入此列表中的指定位置，当前位于该位置的元素（如果有）以及后面的所有位置的元素向后移动一个位置：

    /*** Inserts the specified element at the specified position in this* list. Shifts the element currently at that position (if any) and* any subsequent elements to the right (adds one to their indices).** @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws IndexOutOfBoundsException {@inheritDoc}*/public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size + 1);  // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;}

同样的也需要扩容校验，接着对数据进行复制，目的是把 index 位置空出来放本次插入的数据，并将后面的数据向后移动一个位置。

    /*** A version of rangeCheck used by add and addAll.*/private void rangeCheckForAdd(int index) {if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

add(int index,E element)方法分析：从源码中可以看出，与add(E e)方法大致一致，主要的差异是增加了一行代码：System.arraycopy(elementData, index, elementData, index + 1, size - index)，从index位置开始以及之后的数据，整体拷贝到index+1开始的位置，然后再把新加入的数据放在index这个位置，而之前的数据不需要移动。（这些动作比较消耗性能）java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)，参数含义如下：（原数组，原数组的开始位置，目标数组，目标数组的开始位置，拷贝的个数）void grow(int minCapacity)

最终的扩容代码如下：

    /*** The maximum size of array to allocate.* Some VMs reserve some header words in an array.* Attempts to allocate larger arrays may result in* OutOfMemoryError: Requested array size exceeds VM limit*/// 初始化 存储最大值，Integer.MAX_VALUE = 2147483647 = 2的32次 -1，然后-8private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.** @param minCapacity the desired minimum capacity*/private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//   右移运算符，num >> 1,相当于num除以2，也就是扩充 原来的 1.5倍。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);}/** * 最大容量判断*/private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

删除元素（根据下标）

E remove(int index)

此方法为 根据下标删除

    /*** Removes the element at the specified position in this list.* Shifts any subsequent elements to the left (subtracts one from their* indices).** @param index the index of the element to be removed* @return the element that was removed from the list* @throws IndexOutOfBoundsException {@inheritDoc}*/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);// 把 size-1 的元素 赋值为 null，方便 GC 回收。elementData[--size] = null; // clear to let GC do its workreturn oldValue;}

E remove(int index) 方法总结：

1. 删除此列表中指定位置的元素。
2. 将任何后续元素向左移位（从索引中减去一个）。

删除元素（根据元素）

boolean remove(Object o)

此方法根据 对象删除

    /*** Removes the first occurrence of the specified element from this list,* if it is present.  If the list does not contain the element, it is* unchanged.  More formally, removes the element with the lowest index* <tt>i</tt> such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>* (if such an element exists).  Returns <tt>true</tt> if this list* contained the specified element (or equivalently, if this list* changed as a result of the call).** @param o element to be removed from this list, if present* @return <tt>true</tt> if this list contained the specified element*/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 remove method that skips bounds checking and does not* return the value removed.*/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}

remove(）方法总结：

remove方法与add正好是一个相反的操作，移除一个元素，会影响到一批数字的位置移动，所以也是比较耗性能。

核心代码都是调用了java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)方法。

查询（获取元素）

 E get(int index)

    /*** Returns the element at the specified position in this list.** @param  index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {// 检查是否越界rangeCheck(index);// 返回指定位置上的元素return elementData(index);}@SuppressWarnings("unchecked")E elementData(int index) {return (E) elementData[index];}

E get(int index) 方法总结：

1. 首先检查是否越界；
2. 返回指定位置上的元素。

修改（设置元素）

E set(int index, E element)

    /*** Replaces the element at the specified position in this list with* the specified element.** @param index index of the element to replace* @param element element to be stored at the specified position* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E set(int index, E element) {// 检查是否越界rangeCheck(index);// 获取老的元素值（原下标上的内容）E oldValue = elementData(index);// 在指定位置上赋值新的元素值elementData[index] = element;// 最终 返回老的元素值（原下标上的内容）return oldValue;}

E set(int index,E element) 方法总结：

• 用指定的元素替换此列表中指定位置的元素。

清空方法

void clear()

    /*** Removes all of the elements from this list.  The list will* be empty after this call returns.*/public void clear() {modCount++;// clear to let GC do its work// 将每个元素至为null，便于GC回收for (int i = 0; i < size; i++)elementData[i] = null;// 将此数组 重新赋值为 0size = 0;}

void clear()方法总结：

1. 从此列表中删除所有元素。
2. 此调用返回后，列表将为空。

删除多余无效容量

 void trimToSize()

/*** Trims the capacity of this <tt>ArrayList</tt> instance to be the* list's current size.  An application can use this operation to minimize* the storage of an <tt>ArrayList</tt> instance.*/public void trimToSize() {// 修改次数加1modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}

void trimToSize()方法总结：

1. 将此<tt> ArrayList </ tt>实例的容量调整为列表的当前大小。
2. 应用程序可以使用此操作来最小化<tt> ArrayList </ tt>实例的存储。
3. 将elementData中空余的空间（包括null值）去除，例如：数组长度为10，其中只有前三个元素有值，其他为空，那么调用该方法之后，数组的长度变为3。

是否包含

boolean contains(Object o)

    /*** Returns <tt>true</tt> if this list contains the specified element.* More formally, returns <tt>true</tt> if and only if this list contains* at least one element <tt>e</tt> such that* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.** @param o element whose presence in this list is to be tested* @return <tt>true</tt> if this list contains the specified element*/public boolean contains(Object o) {return indexOf(o) >= 0;}/*** Returns the index of the first occurrence of the specified element* in this list, or -1 if this list does not contain the element.* More formally, returns the lowest index <tt>i</tt> such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,* or -1 if there is no such index.*/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;}

contains(Object o)方法总结：

• 如果此列表包含指定的元素，则返回<tt> true </ tt>。
• 其中 调用 indexOf()方法，返回此列表中第一次出现的指定元素的索引，如果此列表不包含该元素，则返回-1。

contains(Object o)方法分析：

• 该方法分两种情况:null值和非null的遍历，如果查询到就返回下标位置，否则就返回-1，然后与0比较，大于0就存在，小于0就不存在。

总结

新增其实就是判断元素能发装下，装不下就进行扩容，扩容就是数组复制的过程。由此可见 ArrayList 的主要消耗是数组扩容以及在指定位置添加数据，在日常使用时最好是指定大小，尽量减少扩容。更要减少在指定位置插入数据的操作。

基于数组实现的List在随机访问和遍历的效率比较高，但是往指定位置加入元素或者删除指定位置的元素效率比较低。

• ArrayList自己实现了序列化和反序列化的方法，因为它自己实现了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法
• ArrayList基于数组方式实现，无容量的限制（会扩容）
• 添加元素时可能要扩容（所以最好预判一下），删除元素时不会减少容量（若希望减少容量，trimToSize()），删除元素时，将删除掉的位置元素置为null，下次gc就会回收这些元素所占的内存空间。
• 线程不安全
• add(int index, E element)：添加元素到数组中指定位置的时候，需要将该位置及其后边所有的元素都整块向后复制一位
• get(int index)：获取指定位置上的元素时，可以通过索引直接获取（O(1)）
• remove(Object o)需要遍历数组
• remove(int index)不需要遍历数组，只需判断index是否符合条件即可，效率比remove(Object o)高
• contains(E)需要遍历数组
• 使用iterator遍历可能会引发多线程异常

 

部分内容来源于网络，仅供交流学习，如侵联删；

参考文章：https://blog.csdn.net/cb_lcl/article/details/81204114