jdk-source-analysis/docs/java.util.ArrayList.adoc at master

对于每种抽象数据类型并不存在什么法则来告诉我们必须要有哪些操作，这是一个设计决策。--《数据结构与算法分析》

类图

先来看一下 ArrayList 的类图：

@startuml
skinparam nodesep 100
'skinparam ranksep 60

interface Iterable<E>

interface Collection<E> extends Iterable

abstract class AbstractCollection<E> implements Collection

interface List<E>

interface List<E> extends Collection

abstract class AbstractList<E> extends AbstractCollection implements List

class ArrayList<E> extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable

@enduml

支持泛型，继承了 AbstractList，实现了 List 接口。
RandomAccess 用来表明其支持快速（通常是固定时间）随机访问。在 Collections.binarySearch() 方法中，它要判断传入的list 是否 RamdomAccess 的实例，如果是，调用 Collections.indexedBinarySearch(list, key) 方法，如果不是，那么调用 Collections.iteratorBinarySearch(list, key) 方法。
Cloneable 可以调用 Object.clone() 方法返回该对象的浅拷贝。
Serializable 此类可被序列化

为什么还要再次实现 List 接口？（其父类已经实现此接口部分方法： AbstractList 实现 List 接口中除 size() , get(int index) 之外的所有函数）。

抽象类实现接口，可以不真正实现所有方法（可以抽象实现）。

初始化

首先，我们看一下 ArrayList 的初始化：

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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);
    }
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // defend against c.toArray (incorrectly) not returning Object[]
        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

从上述代码中可以猜测，ArrayList 内部使用数组来保存元素的，并且使用一个整型 int 变量来保存长度。

ArrayList 初始化工作分三种情况：

无参构造函数初始化时，直接将内部数组初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。在第一次添加元素时，再初始化为默认容量是 10 的数组。
指定容量大小进行初始化时，容量大于 0 则初始化为指定容量的数组；如果等于 0 则初始化为默认空数组 EMPTY_ELEMENTDATA。否则抛出异常。
如果使用 Collection 实例来初始化，不为空则将调用 toArray() 方法来初始化 elementData；如果为空则初始化为默认空数组 EMPTY_ELEMENTDATA。

添加元素

在进行正常测试前，先展示一下"透视" ArrayList 的工具类：

link:{sourcedir}/ArrayListBaseTest.java[role=include]

正式测试：将初始化长度设置为 8，同时将添加元素的个数设置为 8 * 2 来方便观察数组增长情况。通过上述的工具方法，可以将 ArrayList 内部的数据进一步展示出来：

link:{sourcedir}/ArrayListAddTest.java[role=include]

JDK 相关源代码：

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 * @throws OutOfMemoryError if minCapacity is less than zero
 */
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

private Object[] grow() {
    return grow(size + 1);
}

/**
 * Returns a capacity at least as large as the given minimum capacity.
 * Returns the current capacity increased by 50% if that suffices.
 * Will not return a capacity greater than MAX_ARRAY_SIZE unless
 * the given minimum capacity is greater than MAX_ARRAY_SIZE.
 *
 * @param minCapacity the desired minimum capacity
 * @throws OutOfMemoryError if minCapacity is less than zero
 */
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

/**
 * This helper method split out from add(E) to keep method
 * bytecode size under 35 (the -XX:MaxInlineSize default value),
 * which helps when add(E) is called in a C1-compiled loop.
 */
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

经过测试发现，ArrayList 是在容量达到数组长度之后，再次添加才会扩容，扩容长度为 int newCapacity = oldCapacity + (oldCapacity >> 1)，最小为原始长度，最大不能超过 int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8。

之所以最大长度为 Integer.MAX_VALUE 减去 8，文档解释是因为某些 VM 保留数组头部用于存储一些 header words。但是在 hugeCapacity(int minCapacity) 方法中，在最小容量大于 MAX_ARRAY_SIZE，又可以返回 Integer.MAX_VALUE。

link:{sourcedir}/ArrayListAddTest.java[role=include]

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}

/**
 * A version of rangeCheck used by add and addAll.
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

从这里看出，在头部插入添加元素，实际就是将指定坐标位置以及右侧所有元素向后移动一位，腾出空间存放新元素。

/**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order that they are returned by the
 * specified collection's Iterator.  The behavior of this operation is
 * undefined if the specified collection is modified while the operation
 * is in progress.  (This implies that the behavior of this call is
 * undefined if the specified collection is this list, and this
 * list is nonempty.)
 *
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    System.arraycopy(a, 0, elementData, s, numNew);
    size = s + numNew;
    return true;
}

/**
 * Inserts all of the elements in the specified collection into this
 * list, starting at the specified position.  Shifts the element
 * currently at that position (if any) and any subsequent elements to
 * the right (increases their indices).  The new elements will appear
 * in the list in the order that they are returned by the
 * specified collection's iterator.
 *
 * @param index index at which to insert the first element from the
 *              specified collection
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);

    int numMoved = s - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    size = s + numNew;
    return true;
}

向 ArrayList 中添加集合实例，则是集合示例转化成数组，然后利用数组拷贝的方式来高效完成添加工作。

删除元素

测试遍历速度

ArrayList 的遍历方式有如下几种：

标准迭代器方式
外部 for 循环 + get(index)
forEach(lambda) 方法
for(E e: arrayList)

基准测试当然非 Java Microbenchmark Harness 莫属了。直接上代码：

link:{sourcedir}/ArrayListIteratorSpeedTest.java[role=include]

运行结果如下：

在代码中，常常看到 modCount 属性，这个属性是从 AbstractList 继承到的一个重要属性。这个属性用于在使用迭代器（ListIterator，Iterator）遍历的时候，用来检查列表中的元素是否发生结构性变化（列表元素数量发生改变）了，主要在多线程环境下需要使用，防止一个线程正在迭代遍历，另一个线程修改了这个列表的结构。ArrayList 是非线程安全的，多线程同时修改会抛出异常。writeObject（序列化时），也可能会抛出此异常。

检查到修改不一致就抛出异常是 fail-fast 机制，是 Java 集合(Collection)中的一种错误机制。它只能被用来检测错误，因为JDK并不保证 fail-fast 机制一定会发生。如果发生 fail-fast，则推荐使用 JUC 中对应的类。

简单来说，Java 的序列化机制是通过在运行时判断类的 serialVersionUID 来验证版本一致性的。在进行反序列化时，JVM会把传来的字节流中的 serialVersionUID 与本地相应实体（类）的 serialVersionUID 进行比较，如果相同就认为是一致的，可以进行反序列化，否则就会出现序列化版本不一致的异常。(InvalidCastException)

serialVersionUID 有两种显示的生成方式：

一个是默认的L类型数字，比如：private static final long serialVersionUID = 1L;
一个是根据类名、接口名、成员方法及属性等来生成一个64位的哈希字段。

当实现 java.io.Serializable 接口的实体（类）没有显式地定义一个名为 serialVersionUID，类型为 long 的变量时，Java序列化机制会根据编译的class(它通过类名，方法名等诸多因素经过计算而得，理论上是一一映射的关系，也就是唯一的)自动生成一个 serialVersionUID 作序列化版本比较用，这种情况下，如果class文件(类名,方法明等)没有发生变化(增加空格,换行,增加注释,等等)，就算再编译多次，serialVersionUID 也不会变化的.

如果我们不希望通过编译来强制划分软件版本，即实现序列化接口的实体能够兼容先前版本，未作更改的类，就需要显式地定义一个名为 serialVersionUID，类型为 long 的变量，不修改这个变量值的序列化实体都可以相互进行串行化和反串行化。

3.观察3两个重要属性关键字 transient（瞬态）被标记为transient的属性在对象被序列化的时候不会被保存。 why? 假如elementData的长度为10，而其中只有5个元素，那么在序列化的时候只需要存储5个元素，而数组中后面5个元素是不需要存储的。于是将elementData定义为transient，避免了Java自带的序列化机制，并定义了两个方法，实现了自己可控制的序列化操作。

//更新
public E set(int index, E element) {
	rangeCheck(index);

	E oldValue = elementData(index);
	elementData[index] = element;
	return oldValue;
}
//查找

public E get(int index) {
	rangeCheck(index);

	return elementData(index);
}

//是否包含
public boolean contains(Object o) {
	return indexOf(o) >= 0;
}

public int indexOf(Object o) {
	if (o == null) {
		for (int i = 0; i < size; i++)
			if (elementData[i]==null)
				return i;
	} else {
		for (int i = 0; i < size; i++)
			if (o.equals(elementData[i]))
				return i;
	}
	return -1;
}
//反向查找
public int lastIndexOf(Object o) {
	if (o == null) {
		for (int i = size-1; i >= 0; i--)
			if (elementData[i]==null)
				return i;
	} else {
		for (int i = size-1; i >= 0; i--)
			if (o.equals(elementData[i]))
				return i;
	}
	return -1;
}
//容量判断

public int size() {
	return size;
}

public boolean isEmpty() {
	return size == 0;
}

1.浅克隆（shallow clone）

被复制对象的所有基础类型变量（byte,short,int,long,char,boolean,float,double）与原有对象中变量具有相同的值，修改其值不会影响原对象；而复制对象中引用类型（数组，类对象等）还是指向原来对象，修改其值会影响原对象。

2.深克隆（deep clone）

被复制对象的所有基础类型变量（byte,short,int,long,char,boolean,float,double）与原有对象中变量具有相同的值，修改其值不会影响原对象；并且复制对象中引用类型（数组，类对象等）指向被复制过的新对象，修改其值不会影响原对象。

public Object clone() {
	try {
		ArrayList<?> v = (ArrayList<?>) super.clone();
		v.elementData = Arrays.copyOf(elementData, size);
		v.modCount = 0;
		return v;
	} catch (CloneNotSupportedException e) {
		// this shouldn't happen, since we are Cloneable
		throw new InternalError(e);
	}
}

public Object[] toArray() {
	return Arrays.copyOf(elementData, size);
}

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
	if (a.length < size)
		// Make a new array of a's runtime type, but my contents:
		return (T[]) Arrays.copyOf(elementData, size, a.getClass());
	System.arraycopy(elementData, 0, a, 0, size);
	if (a.length > size)
		a[size] = null;
	return a;
}

// Positional Access Operations
//得到指定索引处的元素
@SuppressWarnings("unchecked")
E elementData(int index) {
	return (E) elementData[index];
}
//清空
public void clear() {
	modCount++;

	// clear to let GC do its work
	for (int i = 0; i < size; i++)
		elementData[i] = null;

	size = 0;
}


protected void removeRange(int fromIndex, int toIndex) {
	modCount++;
	int numMoved = size - toIndex;
	System.arraycopy(elementData, toIndex, elementData, fromIndex,
					 numMoved);

	// clear to let GC do its work
	int newSize = size - (toIndex-fromIndex);
	for (int i = newSize; i < size; i++) {
		elementData[i] = null;
	}
	size = newSize;
}

 //检查数否超出数组长度 用于添加元素时
private void rangeCheck(int index) {
	if (index >= size)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//检查是否溢出
private void rangeCheckForAdd(int index) {
	if (index > size || index < 0)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private String outOfBoundsMsg(int index) {
	return "Index: "+index+", Size: "+size;
}
//删除指定集合的元素
public boolean removeAll(Collection<?> c) {
	Objects.requireNonNull(c);
	return batchRemove(c, false);
}
//仅保留指定集合的元素
public boolean retainAll(Collection<?> c) {
	Objects.requireNonNull(c);
	return batchRemove(c, true);
}
* @param complement true时从数组保留指定集合中元素的值，为false时从数组删除指定集合中元素的值。
* @return 数组中重复的元素都会被删除(而不是仅删除一次或几次)，有任何删除操作都会返回true
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)
				elementData[w++] = elementData[r];
	} finally {
		// Preserve behavioral compatibility with AbstractCollection,
		// even if c.contains() throws.
		if (r != size) {
			System.arraycopy(elementData, r,
							 elementData, w,
							 size - r);
			w += size - r;
		}
		if (w != size) {
			// clear to let GC do its work
			for (int i = w; i < size; i++)
				elementData[i] = null;
			modCount += size - w;
			size = w;
			modified = true;
		}
	}
	return modified;
}
 //保存数组实例的状态到一个流（即它序列化）。写入过程数组被更改会抛出异常
private void writeObject(java.io.ObjectOutputStream s)
	throws java.io.IOException{
	// Write out element count, and any hidden stuff
	int expectedModCount = modCount;
	s.defaultWriteObject();

	// Write out size as capacity for behavioural compatibility with clone()
	s.writeInt(size);

	// Write out all elements in the proper order.
	for (int i=0; i<size; i++) {
		s.writeObject(elementData[i]);
	}

	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}
}
//上面是写，这个就是读了。
private void readObject(java.io.ObjectInputStream s)
	throws java.io.IOException, ClassNotFoundException {
	elementData = EMPTY_ELEMENTDATA;

	// Read in size, and any hidden stuff
	s.defaultReadObject();

	// Read in capacity
	s.readInt(); // ignored

	if (size > 0) {
		// be like clone(), allocate array based upon size not capacity
		ensureCapacityInternal(size);

		Object[] a = elementData;
		// Read in all elements in the proper order.
		for (int i=0; i<size; i++) {
			a[i] = s.readObject();
		}
	}
}

public ListIterator<E> listIterator(int index) {
	if (index < 0 || index > size)
		throw new IndexOutOfBoundsException("Index: "+index);
	return new ListItr(index);
}
实现Iterable
public ListIterator<E> listIterator() {
	return new ListItr(0);
}
实现Iterable
public Iterator<E> iterator() {
	return new Itr();
}

//通用的迭代器实现 迭代器（Iterator）模式

private class Itr implements Iterator<E> {
	int cursor;       // index of next element to return
	int lastRet = -1; // index of last element returned; -1 if no such
	int expectedModCount = modCount;

	public boolean hasNext() {
		return cursor != size;
	}

	@SuppressWarnings("unchecked")
	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];
	}

	public void remove() {
		if (lastRet < 0)
			throw new IllegalStateException();
		checkForComodification();

		try {
			ArrayList.this.remove(lastRet);
			cursor = lastRet;
			lastRet = -1;
			expectedModCount = modCount;
		} catch (IndexOutOfBoundsException ex) {
			throw new ConcurrentModificationException();
		}
	}

	@Override
	@SuppressWarnings("unchecked")
	public void forEachRemaining(Consumer<? super E> consumer) {
		Objects.requireNonNull(consumer);
		final int size = ArrayList.this.size;
		int i = cursor;
		if (i >= size) {
			return;
		}
		final Object[] elementData = ArrayList.this.elementData;
		if (i >= elementData.length) {
			throw new ConcurrentModificationException();
		}
		while (i != size && modCount == expectedModCount) {
			consumer.accept((E) elementData[i++]);
		}
		// update once at end of iteration to reduce heap write traffic
		cursor = i;
		lastRet = i - 1;
		checkForComodification();
	}

	final void checkForComodification() {
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();
	}
}

其中的ListItr继承Itr，实现了ListIterator接口，同时重写了hasPrevious()，nextIndex()， previousIndex()，previous()，set(E e)，add(E e)等方法，所以这也可以看出了Iterator和ListIterator的区别，就是ListIterator在Iterator的基础上增加了添加对象，修改对象，逆向遍历等方法，这些是Iterator不能实现的。

private class ListItr extends Itr implements ListIterator<E> {
	ListItr(int index) {
		super();
		cursor = index;
	}

	public boolean hasPrevious() {
		return cursor != 0;
	}

	public int nextIndex() {
		return cursor;
	}

	public int previousIndex() {
		return cursor - 1;
	}

	@SuppressWarnings("unchecked")
	public E previous() {
		checkForComodification();
		int i = cursor - 1;
		if (i < 0)
			throw new NoSuchElementException();
		Object[] elementData = ArrayList.this.elementData;
		if (i >= elementData.length)
			throw new ConcurrentModificationException();
		cursor = i;
		return (E) elementData[lastRet = i];
	}

	public void set(E e) {
		if (lastRet < 0)
			throw new IllegalStateException();
		checkForComodification();

		try {
			ArrayList.this.set(lastRet, e);
		} catch (IndexOutOfBoundsException ex) {
			throw new ConcurrentModificationException();
		}
	}

	public void add(E e) {
		checkForComodification();

		try {
			int i = cursor;
			ArrayList.this.add(i, e);
			cursor = i + 1;
			lastRet = -1;
			expectedModCount = modCount;
		} catch (IndexOutOfBoundsException ex) {
			throw new ConcurrentModificationException();
		}
	}
}
//返回指定范围的子数组
public List<E> subList(int fromIndex, int toIndex) {
	subListRangeCheck(fromIndex, toIndex, size);
	return new SubList(this, 0, fromIndex, toIndex);
}

static void subListRangeCheck(int fromIndex, int toIndex, int size) {
	if (fromIndex < 0)
		throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
	if (toIndex > size)
		throw new IndexOutOfBoundsException("toIndex = " + toIndex);
	if (fromIndex > toIndex)
		throw new IllegalArgumentException("fromIndex(" + fromIndex +
										   ") > toIndex(" + toIndex + ")");
}

其中的SubList继承AbstractList，实现了RandmAccess接口，类内部实现了对子序列的增删改查等方法，但它同时也充分利用了内部类的优点，就是共享ArrayList的全局变量，例如检查器变量modCount，数组elementData等，所以SubList进行的增删改查操作都是对ArrayList的数组进行的，并没有创建新的数组(不浪费内存资源)。

private class SubList extends AbstractList<E> implements RandomAccess {
	private final AbstractList<E> parent;
	private final int parentOffset;
	private final int offset;
	int size;

	SubList(AbstractList<E> parent,
			int offset, int fromIndex, int toIndex) {
		this.parent = parent;
		this.parentOffset = fromIndex;
		this.offset = offset + fromIndex;
		this.size = toIndex - fromIndex;
		this.modCount = ArrayList.this.modCount;
	}

	public E set(int index, E e) {
		rangeCheck(index);
		checkForComodification();
		E oldValue = ArrayList.this.elementData(offset + index);
		ArrayList.this.elementData[offset + index] = e;
		return oldValue;
	}

	public E get(int index) {
		rangeCheck(index);
		checkForComodification();
		return ArrayList.this.elementData(offset + index);
	}

	public int size() {
		checkForComodification();
		return this.size;
	}

	public void add(int index, E e) {
		rangeCheckForAdd(index);
		checkForComodification();
		parent.add(parentOffset + index, e);
		this.modCount = parent.modCount;
		this.size++;
	}

	public E remove(int index) {
		rangeCheck(index);
		checkForComodification();
		E result = parent.remove(parentOffset + index);
		this.modCount = parent.modCount;
		this.size--;
		return result;
	}

	protected void removeRange(int fromIndex, int toIndex) {
		checkForComodification();
		parent.removeRange(parentOffset + fromIndex,
						   parentOffset + toIndex);
		this.modCount = parent.modCount;
		this.size -= toIndex - fromIndex;
	}

	public boolean addAll(Collection<? extends E> c) {
		return addAll(this.size, c);
	}

	public boolean addAll(int index, Collection<? extends E> c) {
		rangeCheckForAdd(index);
		int cSize = c.size();
		if (cSize==0)
			return false;

		checkForComodification();
		parent.addAll(parentOffset + index, c);
		this.modCount = parent.modCount;
		this.size += cSize;
		return true;
	}

	public Iterator<E> iterator() {
		return listIterator();
	}

	public ListIterator<E> listIterator(final int index) {
		checkForComodification();
		rangeCheckForAdd(index);
		final int offset = this.offset;

		return new ListIterator<E>() {
			int cursor = index;
			int lastRet = -1;
			int expectedModCount = ArrayList.this.modCount;

			public boolean hasNext() {
				return cursor != SubList.this.size;
			}

			@SuppressWarnings("unchecked")
			public E next() {
				checkForComodification();
				int i = cursor;
				if (i >= SubList.this.size)
					throw new NoSuchElementException();
				Object[] elementData = ArrayList.this.elementData;
				if (offset + i >= elementData.length)
					throw new ConcurrentModificationException();
				cursor = i + 1;
				return (E) elementData[offset + (lastRet = i)];
			}

			public boolean hasPrevious() {
				return cursor != 0;
			}

			@SuppressWarnings("unchecked")
			public E previous() {
				checkForComodification();
				int i = cursor - 1;
				if (i < 0)
					throw new NoSuchElementException();
				Object[] elementData = ArrayList.this.elementData;
				if (offset + i >= elementData.length)
					throw new ConcurrentModificationException();
				cursor = i;
				return (E) elementData[offset + (lastRet = i)];
			}

			@SuppressWarnings("unchecked")
			public void forEachRemaining(Consumer<? super E> consumer) {
				Objects.requireNonNull(consumer);
				final int size = SubList.this.size;
				int i = cursor;
				if (i >= size) {
					return;
				}
				final Object[] elementData = ArrayList.this.elementData;
				if (offset + i >= elementData.length) {
					throw new ConcurrentModificationException();
				}
				while (i != size && modCount == expectedModCount) {
					consumer.accept((E) elementData[offset + (i++)]);
				}
				// update once at end of iteration to reduce heap write traffic
				lastRet = cursor = i;
				checkForComodification();
			}

			public int nextIndex() {
				return cursor;
			}

			public int previousIndex() {
				return cursor - 1;
			}

			public void remove() {
				if (lastRet < 0)
					throw new IllegalStateException();
				checkForComodification();

				try {
					SubList.this.remove(lastRet);
					cursor = lastRet;
					lastRet = -1;
					expectedModCount = ArrayList.this.modCount;
				} catch (IndexOutOfBoundsException ex) {
					throw new ConcurrentModificationException();
				}
			}

			public void set(E e) {
				if (lastRet < 0)
					throw new IllegalStateException();
				checkForComodification();

				try {
					ArrayList.this.set(offset + lastRet, e);
				} catch (IndexOutOfBoundsException ex) {
					throw new ConcurrentModificationException();
				}
			}

			public void add(E e) {
				checkForComodification();

				try {
					int i = cursor;
					SubList.this.add(i, e);
					cursor = i + 1;
					lastRet = -1;
					expectedModCount = ArrayList.this.modCount;
				} catch (IndexOutOfBoundsException ex) {
					throw new ConcurrentModificationException();
				}
			}

			final void checkForComodification() {
				if (expectedModCount != ArrayList.this.modCount)
					throw new ConcurrentModificationException();
			}
		};
	}

	public List<E> subList(int fromIndex, int toIndex) {
		subListRangeCheck(fromIndex, toIndex, size);
		return new SubList(this, offset, fromIndex, toIndex);
	}

	private void rangeCheck(int index) {
		if (index < 0 || index >= this.size)
			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	}

	private void rangeCheckForAdd(int index) {
		if (index < 0 || index > this.size)
			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	}

	private String outOfBoundsMsg(int index) {
		return "Index: "+index+", Size: "+this.size;
	}

	private void checkForComodification() {
		if (ArrayList.this.modCount != this.modCount)
			throw new ConcurrentModificationException();
	}

	public Spliterator<E> spliterator() {
		checkForComodification();
		return new ArrayListSpliterator<E>(ArrayList.this, offset,
										   offset + this.size, this.modCount);
	}
}

//按照比较器的判断逻辑进行排序
@Override
@SuppressWarnings("unchecked")
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++;
}
 以下基于 1.8，和函数式编程相关的方法
@Override
public void forEach(Consumer<? super E> action) {
	Objects.requireNonNull(action);
	final int expectedModCount = modCount;
	@SuppressWarnings("unchecked")
	final E[] elementData = (E[]) this.elementData;
	final int size = this.size;
	for (int i=0; modCount == expectedModCount && i < size; i++) {
		action.accept(elementData[i]);
	}
	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}
}

@Override
public Spliterator<E> spliterator() {
	return new ArrayListSpliterator<>(this, 0, -1, 0);
}

static final class ArrayListSpliterator<E> implements Spliterator<E> {


	private final ArrayList<E> list;
	private int index; // current index, modified on advance/split
	private int fence; // -1 until used; then one past last index
	private int expectedModCount; // initialized when fence set

	/** Create new spliterator covering the given  range */
	ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
						 int expectedModCount) {
		this.list = list; // OK if null unless traversed
		this.index = origin;
		this.fence = fence;
		this.expectedModCount = expectedModCount;
	}

	private int getFence() { // initialize fence to size on first use
		int hi; // (a specialized variant appears in method forEach)
		ArrayList<E> lst;
		if ((hi = fence) < 0) {
			if ((lst = list) == null)
				hi = fence = 0;
			else {
				expectedModCount = lst.modCount;
				hi = fence = lst.size;
			}
		}
		return hi;
	}

	public ArrayListSpliterator<E> trySplit() {
		int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
		return (lo >= mid) ? null : // divide range in half unless too small
			new ArrayListSpliterator<E>(list, lo, index = mid,
										expectedModCount);
	}

	public boolean tryAdvance(Consumer<? super E> action) {
		if (action == null)
			throw new NullPointerException();
		int hi = getFence(), i = index;
		if (i < hi) {
			index = i + 1;
			@SuppressWarnings("unchecked") E e = (E)list.elementData[i];
			action.accept(e);
			if (list.modCount != expectedModCount)
				throw new ConcurrentModificationException();
			return true;
		}
		return false;
	}

	public void forEachRemaining(Consumer<? super E> action) {
		int i, hi, mc; // hoist accesses and checks from loop
		ArrayList<E> lst; Object[] a;
		if (action == null)
			throw new NullPointerException();
		if ((lst = list) != null && (a = lst.elementData) != null) {
			if ((hi = fence) < 0) {
				mc = lst.modCount;
				hi = lst.size;
			}
			else
				mc = expectedModCount;
			if ((i = index) >= 0 && (index = hi) <= a.length) {
				for (; i < hi; ++i) {
					@SuppressWarnings("unchecked") E e = (E) a[i];
					action.accept(e);
				}
				if (lst.modCount == mc)
					return;
			}
		}
		throw new ConcurrentModificationException();
	}

	public long estimateSize() {
		return (long) (getFence() - index);
	}

	public int characteristics() {
		return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
	}
}

@Override
public boolean removeIf(Predicate<? super E> filter) {
	Objects.requireNonNull(filter);
	// figure out which elements are to be removed
	// any exception thrown from the filter predicate at this stage
	// will leave the collection unmodified
	int removeCount = 0;
	final BitSet removeSet = new BitSet(size);
	final int expectedModCount = modCount;
	final int size = this.size;
	for (int i=0; modCount == expectedModCount && i < size; i++) {
		@SuppressWarnings("unchecked")
		final E element = (E) elementData[i];
		if (filter.test(element)) {
			removeSet.set(i);
			removeCount++;
		}
	}
	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}

	// shift surviving elements left over the spaces left by removed elements
	final boolean anyToRemove = removeCount > 0;
	if (anyToRemove) {
		final int newSize = size - removeCount;
		for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
			i = removeSet.nextClearBit(i);
			elementData[j] = elementData[i];
		}
		for (int k=newSize; k < size; k++) {
			elementData[k] = null;  // Let gc do its work
		}
		this.size = newSize;
		if (modCount != expectedModCount) {
			throw new ConcurrentModificationException();
		}
		modCount++;
	}

	return anyToRemove;
}

@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
	Objects.requireNonNull(operator);
	final int expectedModCount = modCount;
	final int size = this.size;
	for (int i=0; modCount == expectedModCount && i < size; i++) {
		elementData[i] = operator.apply((E) elementData[i]);
	}
	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}
	modCount++;
}

}

总结， List接口可调整大小的数组实现。实现所有可选的List操作，并允许所有元素，包括null，元素可重复。除了列表接口外，该类提供了一种方法来操作该数组的大小来存储该列表中的数组的大小。

时间复杂度：
方法size、isEmpty、get、set、iterator和listIterator的调用是常数时间的。
	添加删除的时间复杂度为O(N)。其他所有操作也都是线性时间复杂度。

容量：
	每个ArrayList都有容量，容量大小至少为List元素的长度，默认初始化为10。
 容量可以自动增长。
 如果提前知道数组元素较多，可以在添加元素前通过调用ensureCapacity()方法提前增加容量以减小后期容量自动增长的开销。
 也可以通过带初始容量的构造器初始化这个容量。

 线程不安全：
 	ArrayList不是线程安全的。
 	如果需要应用到多线程中，需要在外部做同步。
**指导意义**
那种遍历性能更优？应该使用哪种遍历方式？
《编写高质量代码：改善Java程序的151个建议》一书认为使用传统的下标遍历是优于增强型for循环的，而《Effective Java中文版 第2版》推荐的是增强型for循环，说for-each循环没有性能损失。何解？
在ArrayList大小为十万之前，五种遍历方式时间消耗几乎一样
即便在千万大小的ArrayList中，几种遍历方式相差也不过50ms左右（for-each循环较大），且在常用的十万左右时间几乎相等，考虑foreach简洁的优点，我们大可选用foreach这种简便方式进行遍历。

这是对ArrayList效率影响比较大的一个因素。每当执行Add等添加元素的方法，都会检查内部数组的容量是否不够了，如果是，它就会以当前容量的 1.5 倍来重新构建一个数组，将旧元素Copy到新数组中，然后丢弃旧数组，在这个临界点的扩容操作，应该来说是比较影响效率的。正确的预估可能的元素，是提高ArrayList使用效率的重要途径。

问题

Java 中有很多标识类的接口。这些表示类有什么意义？是否在 Java 虚拟机中对其进行了特殊处理？
在实现 java.io.Serializable 时，如果不声明 serialVersionUID 变量时，是否会生成这个值？默认的值是什么？在序列化时，是如何保存这个值？在反序列化时，如何从对象的字节码中获取这个值？比较后，如果不同又怎么处理的？
在 ArrayList 中有 writeObject(java.io.ObjectOutputStream s) 和 readObject(java.io.ObjectInputStream s) 方法。在单例模式中，为了解决反序列化的问题，会添加 readResolve() 方法。这三个方法有什么用？什么时候被什么调用？被什么调用？设置断点调试一下，看 调用栈。
ArrayList 在扩容时，使用的是 oldCapacity + (oldCapacity >> 1)，这里 oldCapacity >> 1 就是直接移位将 oldCapacity 的值减半，取到的值就是 oldCapacity/2 后的最大正整数。
ArrayList 中有 rangeCheck(int index) 和 rangeCheckForAdd(int index)，区别就是前者没有做负数检查。为什么会有这种区别？为什么不检查负数？再为什么不检查负数为什么还能抛出 ArrayIndexOutOfBoundsException 异常？（文档中）
《数据结构与算法分析》中提到 Iterator 和 ListIterator 的区别以及 ListIterator 中一个特殊的使用。再次看书来确认一下。
通过指令来对比 Iterat or 和 foreach 之间的性能差异。

类图

初始化

添加元素

删除元素

测试遍历速度

问题

参考资料