ArrayList简介
ArrayList概述
- ArrayList是可以动态增长和缩减的索引序列，它是基于数组实现的List类。
- ArrayList封装了一个动态再分配的Object[]数组，每一个类对象都有一个capacity属性，表示它们所封装的Object[]数组的长度，当向ArrayList中添加元素时，该属性值会自动增加。如果想ArrayList中添加大量元素，可以使用ensureCapacity方法一次性增加capacity，可以减少增加重新分配的次数提高性能。
- ArrayList和Vector作为List类的两个典型实现，完全支持List中的全部功能。ArrayList和Vector的显著区别是，ArrayList的线程不安全的，当多个线程访问同一个ArrayList集合时，如果超过一个线程修改ArrayList集合，则程序必须手动保证该集合的同步性；但Vector是线程安全的。
- ArrayList UML类图
ArrayList.png
ArrayList的数据结构
分析一个类的时候，数据结构往往是它的灵魂所在，理解底层的数据结构其实就是理解这个类的实现思路。
ArrayList的数据结构其实就是数组，数组元素类型为Object类型，即可以存放所有类型的数据。所以我们对ArrayList类所有实例的操作底层都是基于数组的操作。
ArrayList源码分析
ArrayList类继承结构和层次关系
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
从代码片段和之前放上去的类图可以发现，ArrayList继承AbstractList，AbstractList继承AbstractCollection并且实现List。这里有一个思想，接口中全部都是抽象的方法，而抽象类可以有抽象方法，还可以有具体的实现方法，正是利用这一点，让AbstractList是实现List接口中一些通用的方法，而具体的类ArrayList就继承这个AbstractList，拿到一些通用的方法，然后自己再实现自己需要定制的方法，这样一来，让代码层次结构更清晰。减少重复代码。
ArrayList类中实现的接口
-
List<E>：查阅资料好像是当时作者的一个错误，因为不影响使用就保留到现在了。 -
RandomAccess：这是一个标记性接口，通过查看API文档，它的作用就是用来快速随机存取，有关效率的问题，在实现了该接口的话，那么使用普通的for循环来遍历，性能更高，例如ArrayList。而没有实现该接口的话，使用Iterator来迭代，这样性能更高，例如LinkedList。所以这个标记性接口只是为了让我们知道我们用什么样的方式去获取数据性能更好。 -
Cloneable：实现了该接口，就可以使用Object.clone()方法了。 -
Serializable：实现该序列化接口，表面该类可以被序列化，什么是序列化？简单的说，就是能够从类变成字节流传输，然后还能从字节流变成原来的类。
ArrayList中的属性
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 版本号
private static final long serialVersionUID = 8683452581122892189L;
/**
* 缺省容量
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空对象数组
* Shared empty array instance used for empty instances.
*/
private static final Object[] 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 = {};
/**
* 实际元素数组
* 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
/**
* 实际元素数组大小
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
/**
* 最大数组容量
* 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
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
ArrayList中的构造方法
ArrayList中有三个构造方法
/**
* 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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 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;
}
}
无参构造方法
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
虽然构造函数的注解上显示说明默认的构造函数会将初始化容量设置为10，但是实际上从代码看，初始化出来是一个空的Object数组，就是这个elementData。
有参构造方法
/**
* 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);
}
}
这个构造函数会给定一个初始化容量大小；若这个初始化容量大小大于0，则把参数当成初始化数组的大小，若这个初始化容量等于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) {
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;
}
}
这个其实是将Collection转换为ArrayList。
ArrayList中的核心方法
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;
}
/**
* 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++;
}
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
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;
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
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;
}
- boolean add(E e)
/**
* 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;
}
描述：默认直接在集合末尾添加元素。
分析：
- ensureCapacityInternal(size + 1)
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));// 确定内部容量方法
}
- calculateCapacity(Object[] elementData, int minCapacity)
// 计算容量大小
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
这里有两种情况分别需要分析：
第一种情况：elementData初始化时是空的数组，那么第一次add的时候，minCapacity=size+1；也就是说minCapacity=1，这是就会将初始化容量设置为DEFAULT_CAPACITY，也就是minCapacity=10。
第二种情况：elementData不是一个空数组，那么在add的时候，minCapacity=size+1；也就是minCapacity代表着elementData中增加之后的实际数据的个数情况，后面会拿着它去和elementData的length比较，如果length不够用，那么肯定要扩大容量，不然增加这个元素就会溢出。
- ensureExplicitCapacity(int minCapacity)
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 后面解释
// overflow-conscious code
if (minCapacity - elementData.length > 0) // 判断minCapacity的长度是不是大于elementData的数组长度length，如果大于0，则说明数组长度这时候已经不够用了。则需要对数组进行扩容。
grow(minCapacity); // 确定数组容量大小，并改变容量大小
}
- grow(int minCapacity)
// 核心方法，扩展数组容量
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // elementData的长度赋给oldCapacity
int newCapacity = oldCapacity + (oldCapacity >> 1); // 计算新的elementData的大小，就是1.5倍的oldCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; // 这里是为了适应elementData就是空数组的时候，length=0，那么这个时候newCapacity和oldCapacity都为0，所以这里的判断成立了，这里将newCapacity设置为10
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity); // 如果newCapacity超过了最大的容量限制，就调用hugeCapacity，也就是能够给的最大值的newCapacity。
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); // 最后将数组的容量已经确定好，直接拷贝就可以了。
}
补充：
之前有一个modCount属性没有说明，现在来解释一下。我们发现在父类AbstractList中定义了一个int型的属性：modCount，记录了ArrayList结构性变化的次数。
protected transient int modCount = 0;
在ArrayList的所有涉及结构变化的方法中都增加modCount的值，包括：add()、remove()、addAll()、removeRange()及clear()方法。这些方法每调用一次，modCount的值就加1。
AbstractList中的iterator()方法（ArrayList直接继承了这个方法）使用了一个私有内部成员类Itr，生成一个Itr对象（Iterator接口）返回：
public Iterator iterator() { return new Itr(); }
Itr实现了Iterator()接口，其中也定义了一个int型的属性：expectedModCount，这个属性在Itr类初始化时被赋予ArrayList对象的modCount属性的值。
int expectedModCount = modCount;
注：内部成员类Itr也是ArrayList类的一个成员，它可以访问所有的AbstractList的属性和方法。理解了这一点，Itr类的实现就容易理解了。
在Itr.hasNext()方法中：
public boolean hasNext() { return cursor != size(); }
调用了AbstractList的size()方法，比较当前光标位置是否越界。
在Itr.next()方法中，Itr也调用了定义在AbstractList中的get(int)方法，返回当前光标处的元素：
public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
注意，在next()方法中调用了checkForComodification()方法，进行对修改的同步检查：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
现在对modCount和expectedModCount的作用应该非常清楚了。在对一个集合对象进行跌代操作的同时，并不限制对集合对象的元素进行操作，这些操作包括一些可能引起跌代错误的add()或remove()等危险操作。在AbstractList中，使用了一个简单的机制来规避这些风险。 这就是modCount和expectedModCount的作用所在。
- void add(int index, E element)
/**
* 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在插入位置后的所有元素往后面移动一位。
elementData[index] = element;
size++;
}
描述：在集合特定位置添加元素。
分析：
- rangeCheckForAdd(index)：检查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));
}
插入的位置肯定不能大于size和小于0；如果是，则抛出IndexOutOfBoundsException异常。
- boolean addAll(Collection<? extends E> c)
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
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;
}
描述：将集合c中的所包含的元素都插入到集合中。
- boolean addAll(int index, Collection<? extends E> c)
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
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;
}
描述：将集合c中所包含的元素都插入到集合的index处。
remove方法
- 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); // 检查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; // clear to let GC do its work
return oldValue; // 返回删除的元素
}
描述：删除集合指定位置上的元素，并返回删除的元素。
- 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 ? get(i)==null : 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;
}
描述：删除集合中第一个特定的对象。这里我们发现ArrayList是可以存在null值的。
- 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
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
描述：将elementData中的每个元素都赋值为null，并且等待垃圾回收，且将size设置为0。
- boolean removeAll(Collection<?> c)
/**
* Removes from this list all of its elements that are contained in the
* specified collection.
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
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++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r]; // false情况取不在c集合中的元素
} 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 work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
set方法
- 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; // 返回旧的值
}
描述：将index索引处的元素替换成element对象，返回被替换的旧元素。
indexOf方法
- int indexOf(Object o)
/**
* 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 ? get(i)==null : 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;
}
描述：返回对象o在集合中第一次出现的位置索引，如果没有则返回-1。
get方法
- 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);
}
描述：返回集合index索引处的元素。
总结
- ArrayList可以存放null值。
- ArrayList本质上是一个elementData数组。
- ArrayList与数组的本质区别就在于能够自动扩展，其中自动扩展容量为1.5倍原来容量大小。
- ArrayList由于本质是数组，所以它在数据查询方面会很快，但是对于数据的插入和删除，性能会下降很多，因为需要移动数据才能达到插入的效果。
- ArrayList实现了RandomAccess，所以遍历推荐使用for循环。
