ArrayList概述
1.ArrayList是基于数组实现的，是一个动态数组，与Java的数组相比，它的容量可以自动增长扩容。
2.ArrayList实现了RandomAccess（支持随机快速访问，通过序列号访问元素内容），实现了Cloneable（可以被克隆），实现了Serializable（可以被序列化）。
3.ArrayList不是线程安全的，最好在单线程情况下使用，多线程的情况下考虑用concurrent并发包下面的CopyOnWriteArrayList类或者Vector类，或者通过Collections.synchronizedList(list)函数返回一个线程安全的ArraList类
构造函数
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0) // 如果initialCapacity>0就给定一个 initialCapacity大小的数组
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA; // 给定一个空数组
}
// 构造一个包含指定元素的list，这些元素是按照C的迭代器返回的顺序排列的
public ArrayList(Collection<? extends E> paramCollection)
{
this.elementData = paramCollection.toArray(); //转换
if ((this.size = this.elementData.length) != 0)
{
if (this.elementData.getClass() != [Ljava.lang.Object.class) { // 不是Object类型就强制转换为Object类型
this.elementData = Arrays.copyOf(this.elementData, this.size, [Ljava.lang.Object.class);
}
}
else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
添加
public boolean add(E e) {
// 增加一个元素首先得保证底层数组不越界
ensureCapacityInternal(size + 1); // 增加modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 之前使用的是ArrayList()作为构造函数的话，第一次扩展把空数组扩展成size=10的数组
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
// 数组容量检查，不够时则进行扩容
private void ensureExplicitCapacity(int minCapacity) {
//这个变量记录了对ArrayList修改的次数(Fail-Fast 就是检测的这个变量)
modCount++;
// overflow-conscious code
// 当前数组没有更多容量了，则需要动态扩展
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 即newCapacity =1.5倍oldCapacity，所以ArrayList每次动态扩展是1.5倍的扩展
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// ArrayList不适合Add很多的场景，每当底层数组扩容后需要把所有的元素从老数组copy到新数组
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
添加(指定下标)
public void add(int index, E element) {
rangeCheckForAdd(index); // 判断输入的下标是否越界
ensureCapacityInternal(size + 1); // 增加 modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 需要把指定位置后面的所有元素都往后移动一个位置，所以也是比较低效的。
elementData[index] = element; // 指定位置存放元素
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
读取
public E get(int index) {
rangeCheck(index); // 判断索引是否越界
return elementData(index); // 返回指定索引的值
}
/**
*检查给定的索引是否在范围内。如果没有，就抛出一个适当的
*运行时异常。该方法不检查索引是否为
*否定:在数组访问之前，它总是被立即使用，
*抛出ArrayIndexOutOfBoundsException如果指数是负的。
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
修改
public E set(int index, E element) {
rangeCheck(index); // 判断索引是否越界
E oldValue = elementData(index); // 取得旧的值
elementData[index] = element; // 设为新的值
return oldValue; // 返回旧的值
}
删除
public E remove(int index) {
rangeCheck(index); // 判断索引是否越界
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0) // 把index后面的元素整体向前移动，可以看出这步是非常耗资源的
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 放弃对最后一个元素的引用，让GC能回收掉它
elementData[--size] = null; // clear to let GC do its work
return oldValue; // 返回被删除的那个元素
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) { // 删除数组中所有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) // 把index后面的元素整体向前移动，可以看出这步是非常耗资源的
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 放弃对最后一个元素的引用，让GC能回收掉它
elementData[--size] = null; // clear to let GC do its work
}
