1. 简介
List是一种支持插入、删除、查找，元素可重复，可为null的数据结构，在JDK中有不同的实现类，其中ArrayList基于数组实现，支持随机访问，非线程安全，插入与删除时间复杂度为O(n)。
2. 实现
ArrayList内部是使用数组来实现的，所以可以做到随机访问时间为O(1)，如果不一开始设置好最终的大小，可能在不断添加元素的过程中多次扩容而导致效率问题。
属性
//默认容量
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
//数组最大大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//元素存放的数组，设置为transient的目的是序列化对象时忽略该数组，因为数组可能不是存满的，我们只序列化必要的对象以节省空间时间。
transient Object[] elementData; // non-private to simplify nested class access
//已经添加的元素数量
private int size;
构造函数
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);
}
}
// 如果未给出大小，默认大小是数组大小10，只不过这个大小为10的数组是延迟到添加元素创建的，所以这里
// 一开始数组大小是0。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
扩容函数
private void ensureCapacityInternal(int minCapacity) {
// 这里就是默认大小数组延迟创建的开始部分了
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 判断是否需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 新数组的大小为旧数组的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);
}
增删改查方法
// 获取指定位置上的元素
public E get(int index) {
//范围检查，index超出范围抛出异常
rangeCheck(index);
return elementData(index);
}
// 修改指定位置上的元素并返回旧元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
// 添加元素到列表尾部
public boolean add(E e) {
// 判断是否需要扩容，如需要则扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 添加元素到指定索引位置
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++;
}
// 移除指定位置上的元素并返回其值
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; // clear to let GC do its work
return oldValue;
}
// 若存在对象o则移除
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;
}
// 清空所有对象
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
toArray方法
// 复制出一个具有原数组所有元素的新数组
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
subList方法
创建出一个子List，对该List的操作将作用于到原List上
public List<E> subList(int fromIndex, int toIndex) {
// 检查索引范围是否合法
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
sort方法
List接口中存在默认的sort方法，只不过该方法是为LinkedList非基于数组实现的List准备的，所以ArrayList重写了sort方法，通过调用Arrays.sort()方法直接对数组进行排序效率比默认的高。
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
3. 适用场景
- ArrayList内部基于数组实现，查找效率非常高，但是当出现大量的插入或删除操作，每次都要移动大量元素，明显效率很低。所以ArrayList应该适合于那种查找操作多于插入删除操作的场景。
- ArrayList比LinkedList节省空间，因为ArrayList核心就是一个存储该类元素的数组。在64位虚拟机下，不开启指针压缩情况下：
- ArrayList存储元素消耗的空间为 24字节（数组对象头）+ 数组长度 * 8字节
- LinkedList存储元素消耗的空间为 元素数量 * 40字节（结点对象头 + 前后结点指针 + 元素指针）
- 总的来说，每存储一个元素，ArrayList平均消耗8个字节的引用空间，而LinkedList除了消耗8个字节的引用空间还要32字节的空间（结点对象头 + 前后结点指针）
