开篇
ArrayList主要由如下特性：
ArrayList实际上是通过一个数组去保存数据的，当我们构造ArrayList时，如果使用默认构造函数，ArrayList的默认容量大小是10。
当ArrayList容量不足以容纳全部元素时，ArrayList会自动扩张容量，新的容量 = 1.5*原始容量。
ArrayList的克隆函数，将全部元素克隆到一个数组中，采用Arrays.copyOf方法实现。
ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写出“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
在做ArrayList的遍历的时候有3中遍历的方法，分别是随机访问遍历，用迭代器遍历和强制for循环遍历，按照效率来说最快的是随机访问遍历，最差的是迭代器遍历。
ArrayList的遍历是不安全的，在遍历的时候如果改变了集合的结构会抛出ConcurrentModificationException异常。
ArrayList类图
ArrayList类图
ArrayList类定义
ArrayList的类定义比较简单，基本上可以看出来默认值数组大小为10，数据存储通过elementData变量。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
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 = {};
//默认是package-private access，保存数据
transient Object[] elementData;
//实际保存的数据量大小
private int size;
}
ArrayList构造函数
ArrayList的构造数非常简单，根据传入的参数initialCapacity初始化数组大小。如果不传参数就默认构建空数组。
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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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;
}
}
ArrayList常用操作
ArrayList的add操作
ArrayList的add操作其实就是分两步走：
- 以size+1的大小去看下是否容纳的下新元素，否则就以1.5的原有空间扩容。
- 在扩容后的新数组的index位置插入新元素。
- grow()方法内部实现扩容和旧元素的拷贝，采用Arrays.copyOf(elementData, newCapacity)实现。
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++;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}
ArrayList的remove操作
ArrayList的remove操作分两步走：
- 将待移除的index往后的元素拷贝至index开始的位置。
- 将最后一位元素置null并且size-1即可。
ArrayList的clear操作负责将数组全部置null即可。
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;
}
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
ArrayList迭代器
ArrayList的迭代器实现很简单，通过创建Itr对象。在Itr类当中将cursor初始化为0，next过程中就是返回变量同时将cursor+1，hasNext()方法只是判断cursor是否等于size的值。
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // 默认初始化值为0
int lastRet = -1; // 上一个返回值的下标
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
}
