简介
ArrayList是一个动态数组。ArrayList几乎拥有数组所有优点，例如元素有序，索引访问等；并且一般情况下它还不会越界，添加元素时它能动态扩容。平时工作中ArrayList被我们广泛应用，本章详细介绍ArrayList原代码。
类
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable,
java.io.Serializable
ArrayList实现List接口，继承AbstractList抽象类，另外实现RandomAccess (支持随机访问)、Cloneable(支持拷贝) 两个特殊接口
属性
// 默认容量大小
private static final int DEFAULT_CAPACITY = 10;
// 空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 空数组。（用两个的目的是为了知道添加第一个元素时需要创建多大的空间）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};
// 真正存储ArrayList中的元素的数组
transient Object[] elementData;
// 存储ArrayList的大小，注意不是elementData的长度
private int size;
// 数组的最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 修改次数, 每次add、remove它的值都会加1（这个属性是AbstractList中的）
protected transient int modCount = 0;
构造函数
// 无参构造函数
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
使用无参构造函数初始化时并不会设置元素数组长度
// 带初始长度参数的构造函数
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 初始长度参数大于0，用此长度初始化创建元素数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 初始长度参数为0，使用空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 小于0抛异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
初始化时指定长度，长度小于0抛异常，等于0时一样用空数组，大于0时才会创建
// 参数为集合
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 {
// 参数中也没有元素时，用空数组替换
this.elementData = EMPTY_ELEMENTDATA;
}
}
使用集合初始化时，是把参数转数组，然后赋值给元素数组。至于转Object数组操作，只是为了解决前面版本的bug
基础方法
// 获取元素个数
public int size() {
return size;
}
// 判空
public boolean isEmpty() {
return size == 0;
}
// 根据索引设值
public E set(int index, E element) {
// 判断索引是大于元素个数
rangeCheck(index);
// 替换数组中的元素
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
索引取值
// 根据索引获取元素
E elementData(int index) {
return (E) elementData[index];
}
// 根据索引获取元素
public E get(int index) {
// 判断索引是否大于元素个数
rangeCheck(index);
// 数组取值
return elementData(index);
}
找索引
public int indexOf(Object o) {
if (o == null) {// 参数为空
// 遍历查找为空的元素，并返回索引（从0开始）
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {// 参数不为空
// 遍历查找equals一样的元素，并返回索引（从0开始）
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
// 未找到返回-1
return -1;
}
public int lastIndexOf(Object o) {
if (o == null) {// 参数为空
// 遍历查找为空的元素，并返回索引（从size-1开始）
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {// 参数不为空
// 遍历查找equals一样的元素，并返回索引（从size-1开始）
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
添加方法
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
// 验证index是否越界
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
// 从index位置开始，后面的元素全部向后移动1
System.arraycopy(elementData, index, elementData,
index + 1, size - index);
elementData[index] = element;
size++;
}
public boolean addAll(Collection<? extends E> c) {
// 参数集合转数组
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
// 数组拼接
System.arraycopy(a, 0, elementData, size, numNew);
// 修改元素个数
size += numNew;
// 参数中元素个数不为0时添加成功
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
// 验证index是否越界
rangeCheckForAdd(index);
// 参数集合转数组
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
// 判断插入的位置是否有元素
int numMoved = size - index;
if (numMoved > 0)
// 有元素就把后元素向后移动numNew，给参数留位置
System.arraycopy(elementData, index, elementData,
index + numNew, numMoved);
// 数组拼接
System.arraycopy(a, 0, elementData, index, numNew);
// 修改元素个数
size += numNew;
// 参数中元素个数不为0时添加成功
return numNew != 0;
}
向元素数组中插入新元素。这里一直提到ensureCapacityInternal方法，下面看看这个方法
private void ensureCapacityInternal(int minCapacity) {
// 这里调用calculateCapacity方法
ensureExplicitCapacity(calculateCapacity(elementData,
minCapacity));
}
private static int calculateCapacity(Object[] elementData,
int minCapacity) {
// 这里判断是否为第一次添加元素
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);
}
上面ensureCapacityInternal方法源码可以看出，第一次调用时初始化数组，后面调用时它的作用就是接受一个长度，判断这个长度是否超过数组长度，超过就要扩容
扩容
private void grow(int minCapacity) {
// 原数组长度
int oldCapacity = elementData.length;
// 新长度 新长度为原长度的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 新长度小元素个数，则新长度为元素个数
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 新长度超限，hugeCapacity判断长度超限
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) {
// 长度小于0抛异常
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 长度超过Integer.MAX_VALUE-8时，取Integer.MAX_VALUE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
通过上面方法可以看到，扩容在添加之前，扩容后长度为原来的1.5倍（>>1 右移一位相当于除以2，左移一位相当于乘以2），扩容后长度超过int最大值减8时取int最大值
删除
单个元素删除比较简单
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);
// 修改长度，并把最后一个置空
elementData[--size] = null;
// 返回原来元素
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;
}
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;
}
多个元素删除
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)
// 整理当前数组，w为已整理元素个数
elementData[w++] = elementData[r];
} finally {
// 只有在前面循环完，数组扩容才会r!=size
if (r != size) {
// 把w至r的元素干掉，r至新size的元素前移
System.arraycopy(elementData, r,
elementData, w, size - r);
// 设置w长度
w += size - r;
}
// 参数跟当前数组不一样
if (w != size) {
// 从w开始清空
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
// 修改元素个数
size = w;
modified = true;
}
}
return modified;
}
可以看出JDK 考虑的非常细
取交集
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
清空
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
// 数组中元素置空
elementData[i] = null;
// 长度设为0
size = 0;
}
转数组
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
// 判断长度是否够用
if (a.length < size)
// 长度不够，创建长度为size的数组，并拷贝
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// 长度不够用，直接拷贝
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}