ArrayList类源码全解读

1. ArryaList的实现方式是数组
2. 数组的默认大小为10
3. ArrayList线程不安全
4. ArrayList的最大容量是最大整形.
5. 可以传入一个比较器来修改list的顺序

ArrayList的重要方法

grow(int minCapacity)
方法来增加list容量

/**
* 增加list的容量,确保它至少可以存放指定的最小数量的元素.
* @param minCapacity the desired minimum capacity
*/
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);
   elementData = Arrays.copyOf(elementData, newCapacity);
}
复制代码

add(E e)添加元素

/**
     * list末尾添加指定元素
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
		//增加一个元素前,确保list空间足够
        ensureCapacityInternal(size + 1);  //  Increments modCount!!
        elementData[size++] = e;
        return true;
    }
复制代码

get(int index)获取元素

/**
 * 返回指定下标元素
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    rangeCheck(index);//下标检查
    return elementData(index);
}
复制代码

删除元素remove(int index)

/**
 * 删除指定位置的元素.将该位置及后边的元素左移.返回旧的该位置的元素
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    rangeCheck(index);//检查index合法性

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
		//该位置及后面的元素全部往前移
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
	//list元素个数-1,全部元素左移后,将最后一个元素置为null
    elementData[--size] = null; //  clear to let GC do its work
    return oldValue;
}
复制代码

过滤器过滤元素removeIf(Predicate<? super E> filter)

@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;
	//BitSet是一个用来表示各个数值是否存在的类.
	//它将多个数值放在一个long[]中,long[]中的每一个值只能是0或者1.
	//0表示该index的数不存在,1表示该index的数存在.
	//例如三个数1,6,7存在long[]中,因为一个long值长度为64bit,因此,只需一个long值即可存
	//存起来的结果是: [000...76000010],第1位,6位,7位的值置为1
    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)) {
            //BitSet中标记
			removeSet.set(i);
			删除元素数量+1
            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为下一个未删除的元素
			i = removeSet.nextClearBit(i);
			//将未删除的元素集中挪到数组的前面
            elementData[j] = elementData[i];
        }
		//遍历未被删除的元素后面的所有元素,将所有元素置为null,等待回收
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  //  Let gc do its work
        }
		//设置list中元素数量
        this.size = newSize;
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }
	//返回是否有元素被删除
    return anyToRemove;
}
复制代码

源码全解读

package java.util;

import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;

/**
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Collection
 * @see     List
 * @see     LinkedList
 * @see     Vector
 * @since   1.2
 */

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * DEFAULT_CAPACITY: 默认初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 空的共享示例
     */
    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 = {};

    /**
     * 存储ArrayList的元素的数组缓冲区。ArrayList的容量是此数组缓冲区的长度。
     */
    transient Object[] elementData; *  非私有化为了简化类的嵌套访问

    /**
     * ArrayList拥有的元素个数
     *
     * @serial
     */
    private int size;

    /**
     * 指定初始容量,构造一个空的list
     * @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);
        }
    }

    /**
	 * 构造一个空的list,默认初始容量为10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 使用集合来构造一个list
     *
     * @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) {
			// 如果返回的不是Object类型,那么新建一个数组,复制原来的元素并转换为Object类型
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            //  空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    /**
	 * 将list数组的大小设置到和size一样大,来节省存储空间
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

    /**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     *
     * @param   minCapacity   the desired minimum capacity
     */
    public void ensureCapacity(int minCapacity) {
		// list不等于空,最小扩容就是0,否则最小容量是10
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            //  any size if not default element table
            ? 0
            //  larger than default for default empty table. It's already
            //  supposed to be at default size.
            : DEFAULT_CAPACITY;
		// 如果最小容量大于最小扩容,那么确保最小容量可用,将list扩容到最小容量
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    private void ensureCapacityInternal(int minCapacity) {
		// 如果list为空,最小容量是10或者最小容量中较大的值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
		// 确保最小容量可用,将list扩容到最小容量
        ensureExplicitCapacity(minCapacity);
    }
	// 保证最小容量: 防止内存溢出
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        //  overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /**
	 * list的最大可分配大小.一些虚拟机需要在数组里保留一些头信息,获取更大的空间可
	 * 能会导致内存溢出.
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 增加list的容量,确保它至少可以存放指定的最小数量的元素.
     * @param minCapacity the desired minimum capacity
     */
    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);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) *  如果最小容量数字已经溢出了,抛异常
            throw new OutOfMemoryError();
		// 如果最小容量>Integer.MAX_VALUE - 8,那么最小容量
		// 设为Integer.MAX_VALUE,否则最小容量设为Integer.MAX_VALUE-8
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

    /**
     * 查询list中元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 查询list是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 查询是否包含指定元素
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    /**
     * 遍历list查询指定元素的位置.如果没有返回-1
     */
    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;
    }

    /**
     * 查询某个元素最后出现的位置,没有的话返回-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;
    }

    /**
     * 复制一个list,元素本身并不会被复制,相当于浅复制
     */
    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);
    }

    /**
     * 将list中的全部元素放到数组a中,并覆盖. 
	 * 如果a的空间足够,那么直接覆盖a,多余的空间用null填充,
	 * 如果a中没有足够的空间,那么新生成一个数组,
	 * 并将list中的元素全部放进去,而a不变.
     * @throws NullPointerException if the specified array is null
     */
    @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;
    }

    //下标查找
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

    /**
     * 返回指定下标元素
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        rangeCheck(index);//下标检查
        return elementData(index);
    }

    /**
     * 根据下标来设置元素,返回旧的该位置的元素
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    /**
     * list末尾添加指定元素
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
		//增加一个元素前,确保list空间足够
        ensureCapacityInternal(size + 1);  //  Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    /**
     * 在制定位置增加新的元素,原来该位置的元素以及后边的元素全部往后挪一个位置.
     * @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);//检查index是否越界.
		//确保空间足够
        ensureCapacityInternal(size + 1);  //  Increments modCount!!
        //将该位置及后边的元素右移
		System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //添加该元素
		elementData[index] = element;
        //元素个数+1
		size++;
    }

    /**
     * 删除指定位置的元素.将该位置及后边的元素左移.返回旧的该位置的元素
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        rangeCheck(index);//检查index合法性

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
			//该位置及后面的元素全部往前移
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
		//list元素个数-1,全部元素左移后,将最后一个元素置为null
        elementData[--size] = null; //  clear to let GC do its work
        return oldValue;
    }

    /**
     * 如果存在某元素,遍历删除第一个.
     * @param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
					//该位置及后面的元素全部往前移,并把最后一个元素置
					//为null,list元素个数-1
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    /*
	 * 删除指定位置的元素,不检查index合法性,不返回被删除的元素的值
     */
    private void fastRemove(int index) {
        modCount++;
        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
    }

    /**
	 * 删除所有元素
     */
    public void clear() {
        modCount++;

        //  clear to let GC do its work
        for (int i = 0; i < size; i++)
			//设置元素为空
            elementData[i] = null;
		//list的元素个数置为0
        size = 0;
    }

    /**
     * 将集合c中的全部元素添加到list的尾部.
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> 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();
        int numNew = a.length;
		//如果容量足够,那么扩容
        ensureCapacityInternal(size + numNew);  //  Increments modCount
        //复制集合中的元素到list中
		System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
		//如果集合长度不为0,则添加成功
        return numNew != 0;
    }

    /**
     * 将集合c中的全部元素添加到list的指定位置,原来位置以及后面的元素往后移.
     * @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 <tt>true</tt> 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);//检查index合法性

        Object[] a = c.toArray();
        int numNew = a.length;
		//如果新的容量合法,那么扩容
        ensureCapacityInternal(size + numNew);  //  Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
			//将原来位置的元素以及后面的元素后移
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
		//将集合中的全部元素放进去
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

    /**
     * 将list中下标从fromIndex到toIndex的元素删除
     * @throws IndexOutOfBoundsException if {@code fromIndex} or
     *         {@code toIndex} is out of range
     *         ({@code fromIndex < 0 ||
     *          fromIndex >= size() ||
     *          toIndex > size() ||
     *          toIndex < fromIndex})
     */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
		//将下标从toIndex开始的全部元素往前移至fromIndex的位置.
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        //  clear to let GC do its work
		//新的list元素个数
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            //将超出下标范围的元素的值设为null
			elementData[i] = null;
        }
        size = newSize;
    }

    /**
	 * 检查index合法性,越界抛出异常.这个方法并不检查index是否为负数.
	 * 当index为负数时,数组本身也会抛出越界的错误,所以这个方法没必要
	 * 检查index是否为负数.
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * add和addAll方法检查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;
    }

    /**
     * 从list中删除与集合c重复的元素
     *
     * @param c collection containing elements to be removed from this list
     * @return {@code true} if this list changed as a result of the call
     * @throws ClassCastException if the class of an element of this list
     *         is incompatible with the specified collection
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if this list contains a null element and the
     *         specified collection does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>),
     *         or if the specified collection is null
     * @see Collection#contains(Object)
     */
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
		//批量删除
        return batchRemove(c, false);
    }

    /**
     * list中只保留与集合c相同的元素
     *
     * @param c collection containing elements to be retained in this list
     * @return {@code true} if this list changed as a result of the call
     * @throws ClassCastException if the class of an element of this list
     *         is incompatible with the specified collection
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if this list contains a null element and the
     *         specified collection does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>),
     *         or if the specified collection is null
     * @see Collection#contains(Object)
     */
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
	/**
	* list批量删除/保留与集合c相同的元素.complement: 删除为false,保留为true
	*/
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        //r: 遍历元素最后一个元素的下标,w: 剩下元素最后一个元素的下标
		int r = 0, w = 0;
		//是否删除元素
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
					//把要保留的元素按照顺序还放到list里,将原来的元素覆盖.
                    elementData[w++] = elementData[r];
        } finally {
            //原方法有可能会报错,这样r就没走到r.size
            if (r != size) {
				//将r到size-1的元素移到保留的元素的后面
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                //w的下标增加r到size-1个元素
				w += size - r;
            }
            if (w != size) {
                //  clear to let GC do its work
				//将保留的元素的后面的元素的值置为null
                for (int i = w; i < size; i++)
                    elementData[i] = null;
				//修改的次数就是删除的元素个数
                modCount += size - w;
                size = w;
				//w和size不相等,说明有元素被删除
                modified = true;
            }
        }
        return modified;
    }

    /**
     * Save the state of the <tt>ArrayList</tt> instance to a stream (that
     * is, serialize it).
     *
     * @serialData The length of the array backing the <tt>ArrayList</tt>
     *             instance is emitted (int), followed by all of its elements
     *             (each an <tt>Object</tt>) in the proper order.
     */
    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();
        }
    }

    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     */
    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();
            }
        }
    }

    /**
     * Returns a list iterator over the elements in this list (in proper
     * sequence), starting at the specified position in the list.
     * The specified index indicates the first element that would be
     * returned by an initial call to {@link ListIterator#next next}.
     * An initial call to {@link ListIterator#previous previous} would
     * return the element with the specified index minus one.
     *
     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

    /**
     * Returns a list iterator over the elements in this list (in proper
     * sequence).
     *
     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @see #listIterator(int)
     */
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

    /**
     * Returns an iterator over the elements in this list in proper sequence.
     *
     * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @return an iterator over the elements in this list in proper sequence
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * 内部类,优化版本的AbstractList.Itr,迭代器
	 * 迭代器的方法类似于链表,但实际实现还是以数组的方式来实现的
     */
    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
        //期待的版本号: 如果跟list中的保持一致,说明中间没有被修改.
		int expectedModCount = modCount;
		//如果游标不等于index,那么有下一个元素
        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
			//检查有没有其他线程修改list内容
            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;
				//将期望版本号改为同list的版本号保持一致
                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();
            }
			//遍历消费从i开始的元素
            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();
        }
    }

    /**
	 * 优化版本的AbstractList.ListItr
     */
    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();
            }
        }
    }

    /**
     * 返回一个list,从原list的fromIndex(包含),到原list的toIndex(不包含).
	 * 对新的list的修改会反映在原list上.
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @throws IllegalArgumentException {@inheritDoc}
     */
    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 + ")");
    }

    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) {
            //原list
			this.parent = parent;
            //子list与原list的偏移量就是fromIndex
			this.parentOffset = fromIndex;
            //子list的偏移量(即子list的游标)是原list的偏移量+fromIndex
			this.offset = offset + fromIndex;
            //子list的长度是toIndex - fromIndex
			this.size = toIndex - fromIndex;
            //子list版本号与原list版本号一直
			this.modCount = ArrayList.this.modCount;
        }

        public E set(int index, E e) {
            //检查index合法性
			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;
        }
		//调用原list方法添加元素
        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
    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();
        }
    }

    /**
     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
     * list.
     *
     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
     * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
     * Overriding implementations should document the reporting of additional
     * characteristic values.
     *
     * @return a {@code Spliterator} over the elements in this list
     * @since 1.8
     */
    @Override
    public Spliterator<E> spliterator() {
        return new ArrayListSpliterator<>(this, 0, -1, 0);
    }

    /** Index-based split-by-two, lazily initialized Spliterator */
    static final class ArrayListSpliterator<E> implements Spliterator<E> {

        /*
         * If ArrayLists were immutable, or structurally immutable (no
         * adds, removes, etc), we could implement their spliterators
         * with Arrays.spliterator. Instead we detect as much
         * interference during traversal as practical without
         * sacrificing much performance. We rely primarily on
         * modCounts. These are not guaranteed to detect concurrency
         * violations, and are sometimes overly conservative about
         * within-thread interference, but detect enough problems to
         * be worthwhile in practice. To carry this out, we (1) lazily
         * initialize fence and expectedModCount until the latest
         * point that we need to commit to the state we are checking
         * against; thus improving precision.  (This doesn't apply to
         * SubLists, that create spliterators with current non-lazy
         * values).  (2) We perform only a single
         * ConcurrentModificationException check at the end of forEach
         * (the most performance-sensitive method). When using forEach
         * (as opposed to iterators), we can normally only detect
         * interference after actions, not before. Further
         * CME-triggering checks apply to all other possible
         * violations of assumptions for example null or too-small
         * elementData array given its size(), that could only have
         * occurred due to interference.  This allows the inner loop
         * of forEach to run without any further checks, and
         * simplifies lambda-resolution. While this does entail a
         * number of checks, note that in the common case of
         * list.stream().forEach(a), no checks or other computation
         * occur anywhere other than inside forEach itself.  The other
         * less-often-used methods cannot take advantage of most of
         * these streamlinings.
         */

        private final ArrayList<E> list;
        //下标: 默认为0
		private int index; //  current index, modified on advance/split
        //分割次数,默认-1
		private int fence; //  -1 until used; then one past last index
        //期望版本号: 默认0
		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;
        }
		//当fence为获取分割次数
        private int getFence() { //  initialize fence to size on first use
            //每一个分割里的终止位置的下标
			int hi; //  (a specialized variant appears in method forEach)
            ArrayList<E> lst;
			//此处会给hi赋值为fence.
            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() {
            //获取分割次数,lo为起始下标,mid为起始下标+终止下标/2
			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;
		//BitSet是一个用来表示各个数值是否存在的类.
		//它将多个数值放在一个long[]中,long[]中的每一个值只能是0或者1.
		//0表示该index的数不存在,1表示该index的数存在.
		//例如三个数1,6,7存在long[]中,因为一个long值长度为64bit,因此,只需一个long值即可存
		//存起来的结果是: [000...76000010],第1位,6位,7位的值置为1
        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)) {
                //BitSet中标记
				removeSet.set(i);
				删除元素数量+1
                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为下一个未删除的元素
				i = removeSet.nextClearBit(i);
				//将未删除的元素集中挪到数组的前面
                elementData[j] = elementData[i];
            }
			//遍历未被删除的元素后面的所有元素,将所有元素置为null,等待回收
            for (int k=newSize; k < size; k++) {
                elementData[k] = null;  //  Let gc do its work
            }
			//设置list中元素数量
            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++;
    }

    @Override
    @SuppressWarnings("unchecked")
    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
		//调用Arrays.sort方法来对list进行排序
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }
}

复制代码