ArrayList是我们最常用的集合类，我们看下它的实现(基于JDK1.8)。
支持原创，转载请注明出处。
继承关系
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
public interface List<E> extends Collection<E>
ArrayList实现了List接口，List又实现了Collection接口。
核心成员变量
private static final int DEFAULT_CAPACITY = 10 ; //默认容量
transient Object [] elementData; //保存元素
private int size ; //当前元素个数
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //空数组
我们注意，数组默认的大小为10。
构造函数
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 boolean add(E e) { //在最后添加元素
ensureCapacityInternal(size + 1); //确保不会越界
elementData[size++] = e; //加入数组
return true;
}
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);
//拷贝原始数组到一个新的数组，新的数组大小为newCapacity，可能截断，或在尾部添加null
elementData = Arrays.copyOf(elementData, newCapacity);
}
加入元素e后，首先确保添加该元素后不会溢出，必要时会进行扩容，扩容机制为int newCapacity = oldCapacity + (oldCapacity >> 1)大约为原大小的1.5倍，然后将原数组复制到新的长度为newCapacity的数组中。最后将该元素e加入到数组末尾。这里我们看到根据需要指定ArrayList的大小可以防止扩容，提高效率。
查找元素
public E get(int index) {
rangeCheck(index); //检查是否越界
return elementData(
}
E elementData(int index) {
return (E) elementData[index]; //返回对应下标的元素
}
查找很简单，先检查是否越界，不越界就返回对象下标的元素。
删除元素
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; //返回被删除元素
}
在数组中间删除元素同样会进行拷贝，如果是常用操作可以使用LinkedList代替。
支持原创，转载请注明出处。
github：https://github.com/gatsbydhn
