一、简述
我们知道，数据结构中主要有两种存储结构，分别是：顺序存储结构（线性表）、链式存储结构（链表），在Java中，对这两种结构分别进行实现的类有：
- 顺序存储结构：ArrayList、Vector、Stack
- 链式存储结构：LinkedList、Queue
二、归纳
- 继承了AbstractList抽象类，实现了List接口，底层基于数组实现容量大小动态变化，允许null的存在。
- 实现了RandomAccess, Cloneable, java.io.Serializable接口，所以支持快速访问、复制(拷贝)、序列化。
- 当使用无参数构造函数创建ArrayList对象时，ArrayList对象中的数组初始长度为0（是一个空数组），然后当进行#add()操作添加一个元素的时候，如果当前是一个空数组，则初始化一个长度为10的数组。
- ArrayList的扩容策略是每次都增加当前数组长度的一半，如果还不满足则增加要当前所需的数组长度。
- ArrayList的扩容方式是直接创建一个新的数组，并将数据拷贝到新数组中。
- 查和改操作速度非常快【时间复杂度：O(1)】,增和删操作相对较慢【时间复杂度：最快O(1)最慢O(n)】。
- ArrayList的操作单线安全，多线程不安全，多线程中可以采用Collections.synchronizedList或者CopyOnWriteArrayList等操作。
三、分析
1、接口
在分析ArrayList源码之前，我们先来看看集合的接口--List。
public interface List<E> extends Collection<E> {
...
// 增
boolean add(E e);
void add(int index, E element);
// 删
boolean remove(Object o);
E remove(int index);
// 改
E set(int index, E element);
// 查
E get(int index);
...
}
在上述接口中，我只抽取了比较重要的几个方法，然后以此为后续重点分析目标，其List接口对应的源码中远不止上述几个方法，有兴趣的同学可以自行翻阅。
2、成员变量
在ArrayList的源码中,其成员变量并不多,所以在此把它们都一一列出。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
// 序列化唯一表示UID
private static final long serialVersionUID = 8683452581122892189L;
// 默认初始化数组容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组实例，在不同的构造函数中使用到
private static final Object[] EMPTY_ELEMENTDATA = {};
// 空数组实例，在无参构造方法中使用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存储ArrayList元素的数组缓冲区，其中transient的作用是防止被序列化的
transient Object[] elementData;
// ArrayList的大小，其实就是其内部维护的数组存储元素的数量
private int size;
...
}
3、构造函数
构造函数是一个类最常见的，同样也是最常被使用到的，接着我们分析Arraylist的三个不同的构造函数。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
/**
* 无参构造函数
*/
public ArrayList() {
// 给elementData数组赋值为一个空数组实例
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 有参构造函数
*
* @param initialCapacity 数组的容量
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {// 当initialCapacity为负数的时候为非法，抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}
/**
* 有参构造函数
* 构造包含指定元素的列表集合
*
* @param c 集合元素
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// 判断其是不是Object对象，如果不是将其转换为Object对象数组
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 给elementData数组赋值为一个空数组实例
this.elementData = EMPTY_ELEMENTDATA;
}
}
...
}
4、增
ArrayList的增操作有两种实现，分别为add(E e)和add(int index, E element)，下面我们来分析其两种实现。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
/**
* 将元素e添加到列表中
*
* @param e 元素e
* @return 返回true标识添加成功
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 将元素element添加到指定的索引位置
*
* @param index 要插入指定元素的索引
* @param element 要插入的元素
* @throws IndexOutOfBoundsException 如果索引角标不合法，则抛出索引越界异常
*/
public void add(int index, E element) {
// 如果索引角标不合法，则抛出索引越界异常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 确保数组有足够的容量，
ensureCapacityInternal(size + 1);
// 从指定的源数组指定的位置开始，将数组复制到目标数组的指定位置，且规定要复制的长度
System.arraycopy(elementData, index, elementData, index + 1,size - index);
// 更新数组索引为index的元素值
elementData[index] = element;
// 维护size
size++;
}
/**
* 复制数组，注意src【源数组】和dest【目标数组】可为同一数组
*
* @param src 源数组
* @param srcPos 源数组中的起始索引位置
* @param dest 目标数组
* @param dest 目标数组中的起始索引位置
* @param length 要copy的数组的长度
*/
public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int length)
/**
* 计算并扩大最小的容器体积
*
* @param minCapacity 容积，其实就是数组的容量大小
*/
private void ensureCapacityInternal(int minCapacity) {
// 判断当前数组elementData是否为空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 获取当前最大的容积
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 看是否需要进行扩容操作
ensureExplicitCapacity(minCapacity);
}
/**
* 看是否需要进行扩容操作
*
* @param minCapacity 容积，其实就是数组的容量大小
*/
private void ensureExplicitCapacity(int minCapacity) {
// 这是ArrayList的父类AbstractList中定义了一个int型的属性
// 在此用来记录了ArrayList结构性变化的次数
modCount++;
// 当该if成立时，说明当前数组(容器)的空间不够了，需要扩容，所以调用grow()方法
if (minCapacity - elementData.length > 0)
grow(minCapacity);// 扩容操作
}
/**
* 增加容量以确保它至少可以容纳由最小容量参数指定的元素数目
*
* @param minCapacity 容积，其实就是数组的容量大小
*/
private void grow(int minCapacity) {
// 获取原始容积
int oldCapacity = elementData.length;
// (oldCapacity >> 1)等价于(oldCapacity / 2)
// 这里就是扩容到原始容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容1.5倍后还不满足，则直接赋值到其所需的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果扩容的容量大于整型的最大值，则进行异常处理或者赋值为整型最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用Arrays.copyOf()创建一个新的数组并将数据拷贝到新数组中，最后让elementData进行引用
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 判断minCapacity是否溢出
*
* @param minCapacity 容积，其实就是数组的容量大小
*/
private static int hugeCapacity(int minCapacity) {
// 判断minCapacity是否小于零，小于则抛出异常
if (minCapacity < 0) throw new OutOfMemoryError();
// 判断minCapacity是否超过整型的边界值从而进行赋值
return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}
...
}
5、删
ArrayList的删操作有两种实现，分别是remove(int index)和remove(Object o)，下面我们来分析其两种实现。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
/**
* 删除索引为index的元素并返回
*
* @param index 要删除的索引
* @return 返回删除的元素
* @throws IndexOutOfBoundsException 抛出索引角标越界异常
*/
public E remove(int index) {
// 判断索引是否合法性
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 这是ArrayList的父类AbstractList中定义了一个int型的属性
// 在此用来记录了ArrayList结构性变化的次数
modCount++;
// 获取要删除的元素
E oldValue = (E) elementData[index];
// 在执行删除操作时数组需要移动的元素个数
int numMoved = size - index - 1;
// (numMoved > 0)成立则将数组进行前移copy
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// 因为数组有可能进行了整个前移1位，所以将最后一个索引对应的值置空，从而降低GC
elementData[--size] = null;
// 返回要删除的元素
return oldValue;
}
/**
* 删除元素o，并且返回是否有效删除
*
* @param o 元素将从此列表中删除(如果存在)
* @return 如果存在该元素将其删除并返回true，否则返回false
*/
public boolean remove(Object o) {
// 这里把空和非空进行区分，空的话用“==”判断，非空用“equals”判断
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 void fastRemove(int index) {
// 这是ArrayList的父类AbstractList中定义了一个int型的属性
// 在此用来记录了ArrayList结构性变化的次数
modCount++;
// 在执行删除操作时数组需要移动的元素个数
int numMoved = size - index - 1;
// (numMoved > 0)成立则将数组进行前移copy
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// 因为数组有可能进行了整个前移1位，所以将最后一个索引对应的值置空，从而降低GC
elementData[--size] = null;
}
...
}
6、改
ArrayList的改操作有一种实现，对应的是set(int index, E element)，下面我们来分析这种实现。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
/**
* 修改索引角标为index的元素值
*
* @param index 要修改的索引坐标
* @param element 修改后存储的元素值
* @return 返回修改前的元素值
* @throws IndexOutOfBoundsException 抛出索引角标越界异常
*/
public E set(int index, E element) {
// 判断索引是否合法性
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 获取原本index的元素值
E oldValue = (E) elementData[index];
// 将其替换成新的元素值
elementData[index] = element;
// 返回修改前的元素值
return oldValue;
}
...
}
7、查
ArrayList的查操作有一种实现，对应的是get(int index)，下面我们来分析这种实现。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
/**
* 查找索引角标为index的元素值
*
* @param index 要修改的索引坐标
* @return 返回查找到的索引为index的元素值
* @throws IndexOutOfBoundsException 抛出索引角标越界异常
*/
public E get(int index) {
// 判断索引是否合法性
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 返回查找到的索引为index的元素值
return (E) elementData[index];
}
...
}
四、ArrayList线程安全处理
1、Collections.synchronizedList
最常用的方法是通过 Collections 的 synchronizedList 方法将 ArrayList 转换成线程安全的容器后再使用。
List<Object> list =Collections.synchronizedList(new ArrayList<Object>);
2、CopyOnWriteArrayList
使用线程安全的 CopyOnWriteArrayList 代替线程不安全的 ArrayList。
List<Object> list1 = new CopyOnWriteArrayList<Object>();
