ArrayList源码分析

334

一、简介

      ArrayList是个可调整大小的数组实现<tt>List</tt>接口。实现了所有可选操作,并允许所有元素,包括<tt>null</tt>元素。除了实现<tt>List</tt>接口,这个类提供了操作数组的大小,list内部使用数组进行存储。ArrayList相当于<tt>Vector</tt>,除了它不是同步的。<tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,  <tt>iterator</tt>, 和 <tt>listIterator</tt>这些操作在常数时间运行。<tt>add</tt>操作大致常数时间运行。也就是说,添加n个元素需要O(n)时间复杂度。所有其他的操作运行在线性时间内(大致上)。每一个<tt>ArrayList</tt>实例含有容量。容量是数组的大小用于存储列表中的元素。数组的大小总是至少和列表大小一样大。数组元素被添加到ArrayList中,容量自动增长。增长策略细节未指定的情况下,添加一个元素有恒定的时间成本开销。应用程序可以在添加大量的元素之前使用<tt>ensureCapacity</tt>方法操作增加<tt>ArrayList</tt>实例容量,这可能减少增量重新分配。注意此实现不是同步的。如果多个线程并发访问一个<tt>ArrayList</tt>实例,和至少一个线程修改列表结构,必须外部同步。(结构修改任何操作,add或者delete一个或者多个元素,或者显式地调整数组的大小;只设置一个元素的值不会修改结构)。这通常是通过一些对象同步列表。如果没有同步对象存在,list应该使用包装{@link Collections#synchronizedList Collections.synchronizedList}方法。最好在创建时完成,以防止意外的不同步访问列表<pre> List list = Collections.synchronizedList(new ArrayList(...));</pre>。{@link #iterator() iterator} 和{@link #listIterator(int) listIterator}方法返回的迭代器都是快速失败(fail-fast)。如果迭代器创建完后,列表结构修改,任何时候以任何方式修改列表结构除非通过迭代器的{@link ListIterator#remove() remove} 或者 {@link ListIterator#add(Object) add} 方法, 否则迭代器将会抛出 {@link ConcurrentModificationException}异常。因此,面对并发修改,迭代器快速、清晰的失败,而不是冒着任意,不确定的行为在未来一个不确定的时间。

二、类关系


List

/**
 * 一个有序集合(也称为一个序列)。该接口的用户精确控制列表中的每个元素被插入的地方。用户可以通过整数索引
 *(列表中的位置)访问元素,并搜索列表中的元素。不像Set集合,<tt>List</tt>通常允许重复的元素。更正式,
 * 列表通常允许元素<tt>e1</tt>和<tt>e2</tt>,<tt>e1.equals(e2)</tt>,并且List通常允许多个null元素,如果
 * 他们允许null元素。也并非不可想象有人会希望实现一个列表,禁止重复元素,通过抛出运行时异常当用户试图
 * 插入他们,但我们希望这种用法是罕见的。<tt>List</tt>接口除了那些指定的,实现<tt>Collection</tt>接口, 
 * <tt>iterator</tt>, <tt>add</tt>, <tt>remove</tt>, <tt>equals</tt>, 和
 * <tt>hashCode</tt>方法。为了方便,声明还包括其他继承方法。<tt>List</tt>接口提供了四种方法通过位置
 * 访问列表元素。List(像java数组)下标从0开始。<tt>List</tt>列表接口提供了一个特殊的迭代器。叫做
 * <tt>ListIterator</tt>允许元素插入和替换,和双向访问除了正常的操作是由<tt>Iterator</tt>提供。
 * <tt>List</tt>接口提供了两种方法来搜索指定的对象。从性能的角度来看,这些方法应该小心使用。在很多实现
 * 中他们将执行昂贵的线性搜索。<tt>List</tt>接口提供了两种方法有效地插入和删除多个元素列表中的任意位置的元素
 * 注意:虽然列表允许包含自己做为元素,极其谨慎的建议<tt>equals</tt> 和 <tt>hashCode</tt>方法在
 * 这个列表不再是良好的定义。一些列表实现限制它们可能包含的元素。例如,一些列表实现禁止null元素,有些 
 * 限制元素的类型。试图添加一个不合格的元素抛出一个运行时异常,通常<tt>NullPointerException</tt> or <tt>ClassCastException</tt>
 * Collection的介绍可以看https://juejin.cn/post/6844904084378484743
 */
public interface List<E> extends Collection<E> {
    // 查询操作

    /**
     * 返回此集合的元素数量.  如果这个集合
     * 包含超过 <tt>Integer.MAX_VALUE</tt> 元素, returns
     * <tt>Integer.MAX_VALUE</tt>数量.
     *
     * @return 在这个集合的元素数量
     */
    int size();

    /**
     * 返回 <tt>true</tt> 如果这个集合不包含任何元素.
     *
     * @return <tt>true</tt> 如果这个集合不包含任何元素
     */
    boolean isEmpty();

    /**
     * 返回 <tt>true</tt> 如果集合包含指定的元素.
     * 更正式, 返回 <tt>true</tt> 当且仅当这个集合包含至少一个元素 <tt>e</tt> 正如
     * <tt>(o==null?e==null:o.equals(e))</tt>.
     *
     * @param o 指定元素
     * @return <tt>true</tt> 如果集合包含指定的元素
     * @throws ClassCastException 如果指定元素的类型与这个集合不相容,可选操作
     * @throws NullPointerException 如果指定的元素为null,并且这个集合不允许null元素
     */
    boolean contains(Object o);

    /**
     * 返回一个这个列表的元素序列的迭代器.
     *
     * @return 返回一个这个列表的元素序列的迭代器
     */
    Iterator<E> iterator();

    /**
     * 返回一个数组,包含这个集合的所有元素,保持元素在这个列表中的顺序(从第一个元素到最后一个元素)。
     *
     * <p>如果集合没有包含引用对象,返回的数组将安全,深copy和浅copy。(换句话说,这个方法必须分配一个新数组,
     *  即使这个集合是由一个数组),调用者可以自由修改返回的数组
     *
     * <p>这种方法给数组和集合充当桥梁.
     *
     * @return 返回包含集合所有元素的一个数组
     */
    Object[] toArray();

    /**
     * 返回一个数组,包含这个集合的所有元素,保持元素在这个列表中的顺序(从第一个元素到最后一个元素)。
     * 返回的数组元素类型是指定的数组的元素类型.如果指定的数组容量大于集合容量,指定的数组会被返回。
     * 否则,一个新的数组将被分配,数组的元素类型为指定数组的元素类型,数组的大小为这个集合的大小。
     *
     * <p>如果数组容量比集合大小更大,集合元素会填充到指定数组的空闲空间,超过集合大小的那些数组位置元素都置为null
     *
     * <p>就像{@link #toArray()} 方法, 这种方法给数组和集合充当桥梁.  
     * 此外,这个方法允许精确控制输出数组的运行时类型,在某些情况下,被用来节省分配成本,
     *
     * <p>假设 <tt>x</tt> 集合只含有字符串元素.
     * 下面的代码可以用转储收集到一个新分配的数组字符串
     *
     * <pre>
     *     String[] y = x.toArray(new String[0]);</pre>
     *
     * 请注意 <tt>toArray(new Object[0])</tt> 和
     * <tt>toArray()</tt>在功能上是一样的.
     *
     * @param <T> 数组包含的元素类型
     * @param a 如果指定的这个数组容量足够大,集合元素将会存储在这个数组;否则一个新的数组将被分配,元素类型为指定数组的元素类型.
     * @return 一个数组,其中包含集合的所有元素
     * @throws ArrayStoreException 如果指定数组的元素类型不是集合元素类型的父类
     * @throws NullPointerException 如果指定的数组是null
     */
    <T> T[] toArray(T[] a);


    // 修改操作
     
    /**
     * 将指定元素加到列表末尾中(可选操作).  
     *
     * 集合支持限制某些元素不能被添加到这个集合操作。特别是一些集合拒绝添加null元素。
     * 和其他人将限制可能添加的元素的类型。集合类应该清楚的指定添加任何限制元素的注释文
     *
     * @param e 指定元素加到集合中
     * @return <tt>true</tt> 如果集合在被调用这个方法后改变
     * @throws UnsupportedOperationException 如果 <tt>add</tt> 操作
     *         在这个集合不支持
     * @throws ClassCastException 如果指定元素的类型不是集合元素类型的超类
     * @throws NullPointerException 如果指定元素是null,并且这个集合不允许添加null元素
     * @throws IllegalArgumentException 如果指定元素的某些属性可以防止它被添加到这个集合中
     */
    boolean add(E e);

    /**
     * 从这个集合删除指定元素,如果它存在(可选操作)。如果列表不包含指定元素,列表不会改变。
     * 更正式,移除e这个元素,列表包含一个或者多个这样的元素,移除最低下标的元素,正如(o==null?e==null:o.equals(e))
     * 如果这个列表包含一个或者多个这样的元素。返回true,如果集合包含指定的元素,调用这个方法集合改变
     *
     * @param o 从列表把这个元素移除,如果这个元素存在
     * @return <tt>true</tt> 返回true,如果集合包含指定的元素,调用这个方法集合改变
     * @throws ClassCastException 如果指定元素的类型与这个列表不相容
     * @throws NullPointerException 如果指定元素是null,并且这个列表不允许添加null元素
     * @throws UnsupportedOperationException 如果这个列表不支持删除操作
     */
    boolean remove(Object o);


    // 批量操作

    /**
     * 返回 <tt>true</tt> 如果列表包含指定集合的所有元素.
     *
     * @param  c 指定集合将被检查,指定集合所有元素是否在这个集合内
     * @return 返回<tt>true</tt> 如果集合包含指定集合的所有元素
     * @throws ClassCastException 在指定集合中有一个或多个元素的类型和这个列表不相容
     * @throws NullPointerException 如果指定集合包含一个或者多个null元素并且当前列表不允许null元素,
     * @see    #contains(Object)
     */
    boolean containsAll(Collection<?> c);

    /**
     * 添加指定集合中的所有元素加到这个列表的末尾,添加到列表中元素的顺序和指定集合迭代器返回的
     * 元素顺序一致(可选操作)
     * 这个操作的行为是未定义的,如果指定的集合被修改当这个方法还在进行中
     *
     * @param c 指定集合,指定集合中的所有元素加到这个列表
     * @return 返回<tt>true</tt> 如果调用后列表改变
     * @throws UnsupportedOperationException 如果 <tt>addAll</tt> 操作
     *         在这个列表不支持
     * @throws ClassCastException 如果指定元素的类型与这个列表元素类型不相容
     * @throws NullPointerException 如果指定的集合含有null元素,但当前列表不支持null元素
     *         或者指定的集合是null
     * @throws IllegalArgumentException 如果指定中至少有一个元素的某些属性可以防止它被添加到这个列表中
     * @see #add(Object)
     */
    boolean addAll(Collection<? extends E> c);

    /**
     * 将指定集合中的所有元素插入此列表的指定位置(可选操作)。
     * 指定位置原本如果存在元素的话,当前位置的元素和后续的元素向右(增加他们的下标)。
     * 新元素出现在这个列表的顺序,即指定集合的迭代器返回元素的顺序。
     * 这个操作的行为是未定义的,在这个方法正在进行中,如果指定的集合被修改。
     * (注意,这将发生如果这个列表指定的集合非空的)
     *
     * @param index 插入指定集合的第一个元素的下标位置
     * @param c 集合包含元素被添加到该列表
     * @return <tt>true</tt> 如果调用该方法后列表改变
     * @throws UnsupportedOperationException 如果 <tt>addAll</tt> 操作
     *         这个列表不支持
     * @throws ClassCastException 如果指定元素的类型与这个列表元素类型不相容
     * @throws NullPointerException 如果指定的集合含有null元素,但当前列表不支持null元素
     *         或者指定的集合是null
     * @throws IllegalArgumentException 如果指定中至少有一个元素的某些属性可以防止它被添加到这个列表中
     * @throws IndexOutOfBoundsException 如果传入进来的下标index
     *         (<tt>index < 0 || index > size()</tt>)
     */
    boolean addAll(int index, Collection<? extends E> c);

    /**
     * 在这个列表删除指定集合的所有元素(可选操作)。这个调用返回后,这个列表不包含指定集合的元素.
     *
     * @param c 集合包含的所有元素从这个列表移除
     * @return <tt>true</tt> 如果调用该方法后列表改变
     * @throws UnsupportedOperationException 如果 <tt>removeAll</tt> 操作
     *         这个列表不支持
     * @throws ClassCastException 如果指定元素的类型与这个列表元素类型不相容
     * @throws NullPointerException 如果该列表含有null元素,并且指定的集合不允许null元素
     *         或者指定的集合是null
     * @see #remove(Object)
     * @see #contains(Object)
     */
    boolean removeAll(Collection<?> c);

    /**
     * 列表只保留指定集合的所有元素(可选操作)。换句话说,
     * 从这个列表删除所有不包含在指定的集合的元素
     *
     * @param c 列表只保留指定集合的所有元素
     * @return <tt>true</tt> 如果调用该方法后列表改变
     * @throws UnsupportedOperationException 如果 <tt>retainAll</tt> 操作
     *         这个列表不支持
     * @throws ClassCastException 如果指定元素的类型与这个列表元素类型不相容
     * @throws NullPointerException 如果该列表含有null元素,并且指定的集合不允许null元素
     *         或者指定的集合是null
     * @see #remove(Object)
     * @see #contains(Object)
     */
    boolean retainAll(Collection<?> c);

    /**
     * 替换这个列表的所有元素为UnaryOperator操作元素后的结果.  
     * 操作错误或抛出运行时异常传递给调用者.
     *
     * @implSpec
     * 默认实现相当于,对于这个 {@code list}:
     * <pre>{@code
     *     final ListIterator<E> li = list.listIterator();
     *     while (li.hasNext()) {
     *         li.set(operator.apply(li.next()));
     *     }
     * }</pre>
     *
     * 如果这个列表的 list-iterator 迭代器不支持 {@code set} 操作
     * {@code UnsupportedOperationException} 将替换第一个元素时抛出
     *
     * @param operator 这个操作运用到每个元素
     * @throws UnsupportedOperationException 如果这个列表是不可变的。
     *         实现元素被替换时可能会抛出这个异常,一般来说,不可变对象不支持修改
     * @throws NullPointerException 如果指定的操作是null或者如果操作后的结果是null并且这个
     *         列表不允许null元素
     * @since 1.8
     */
    default void replaceAll(UnaryOperator<E> operator) {
        //判断传入进来的操作是否为null
        Objects.requireNonNull(operator);
        //获取可以前后遍历的ListIterator迭代器
        final ListIterator<E> li = this.listIterator();
        //判断是否有下一个元素
        while (li.hasNext()) {
            //将指定元素替换成operator操作后的结果
            li.set(operator.apply(li.next()));
        }
    }

    /**
     * 排序列表根据指定的{@link Comparator}排序
     * 
     * <p>在这个列表的所有元素可以 <i>相互 comparable</i> 使用指定
     * 的comparator (正如, {@code c.compare(e1, e2)} 不能抛出
     * {@code ClassCastException} 对于这个列表的任何两个元素 {@code e1} and {@code e2}
     * ).
     *
     * <p>如果指定的comparator是 {@code null} 这个列表的所有元素
     * 必须实现 {@link Comparable} 接口,并且
     * {@linkplain Comparable 自然排序} 将被使用.
     *
     * <p>这个列表必须修改的,但是不需要可调整大小的.
     *
     * @implSpec实现规范
     * 默认实现获得这个列表的所有元素的数组,遍历这个列表的每个元素重置数组相应的位置。
     * (这样就避免了n^2的时间复杂度,只需要nlog(n)性能,试图排序链表.)
     *
     * @implNote实现注意事项
     * 这个实现是一种稳定的、自适应迭代归并排序,需要远远少于n(lg(n))比较当输入数组部分排序,
     * 同时提供传统的归并排序的性能当输入是随机有序数组
     *
     * @param c {@code Comparator} 用于比较列表元素.
     *          如果 {@code null} 值表明列表的所有元素'使用
     *          {@linkplain Comparable 自然排序} 
     * @throws ClassCastException 如果列表包含的元素不能使用指定的比较器相互可比
     * @throws UnsupportedOperationException 如果列表的list-iterator迭代器
     *         不支持{@code set} 操作
     * @throws IllegalArgumentException 可选。如果发生比较器违反{@link comparator}
     *         
     * @since 1.8
     */
    @SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        //获取列表的数组
        Object[] a = this.toArray();
        //排序数组
        Arrays.sort(a, (Comparator) c);
        //获取列表迭代器
        ListIterator<E> i = this.listIterator();
        //将排序好的数组重新设置到列表中 
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

    /**
     * 从这个列表删除所有元素(可选操作).这个调用返回后的列表是空的
     *
     * @throws UnsupportedOperationException 如果 <tt>clear</tt> 操作
     *         列表不支持
     */
    void clear();


    // 比较和哈希

    /**
     * 比较指定的对象与此列表是否相等.  返回
     * <tt>true</tt> 当且仅当指定的对象也是一个列表,列表有相同的大小,两个列表,
     * 所有相应的元素相等.  (两个元素 <tt>e1</tt> 和
     * <tt>e2</tt> <i>equal</i> 如果 <tt>(e1==null ? e2==null :
     * e1.equals(e2))</tt>.)  换句话说,两个列表定义相等如果他们包含相同的元素和元素相同的顺序
     * 
     * @param o 指定对象和这个列表进行比较
     * @return <tt>true</tt> 如果指定的对象和这个列表相等
     */
    boolean equals(Object o);

    /**
     * 返回此列表的哈希码值。定义列表的散列码的计算后的结果:
     * <pre>{@code
     *     int hashCode = 1;
     *     for (E e : list)
     *         hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
     * }</pre>
     * 这将确保 <tt>list1.equals(list2)</tt> 意味着
     * <tt>list1.hashCode()==list2.hashCode()</tt> 任何的两个列表
     *
     * @return 这个列表的哈希码值
     * @see Object#equals(Object)
     * @see #equals(Object)
     */
    int hashCode();


    // 下标操作

    /**
     * 返回此列表的在指定位置的元素.
     *
     * @param index 下标的元素将返回
     * @return 在这个列表指定位置的元素
     * @throws IndexOutOfBoundsException 如果下标
     *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    E get(int index);

    /**
     * 取代这个列表指定位置上的元素(可选操作).
     *
     * @param index 此下标的元素将被替换
     * @param element 元素存储在指定的位置
     * @return 以前在指定位置的元素将被返回
     * @throws UnsupportedOperationException 如果 <tt>set</tt> 操作
     *         在这个列表不支持
     * @throws ClassCastException 如果指定元素的类型和列表元素类型不相容
     * @throws NullPointerException 如果指定元素是null并且这个列表不允许null元素
     * @throws IllegalArgumentException 如果指定元素的某些属性可以防止它被添加到这个集合中
     * @throws IndexOutOfBoundsException 如果下标
     *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    E set(int index, E element);

    /**
     * 在这个列表指定位置插入指定元素(可选操作)。如果指定的位置有元素,和后续的元素都向右一个下标
     *
     * @param index 指定元素被插入的下标
     * @param element 指定元素被插入
     * @throws UnsupportedOperationException 如果 <tt>add</tt> 操作
     *         在这个列表不被支持
     * @throws ClassCastException 如果指定元素的类型和列表元素类型不相容
     * @throws NullPointerException 如果指定元素是null并且这个列表不允许null元素
     * @throws IllegalArgumentException 如果指定元素的某些属性可以防止它被添加到这个集合中
     * @throws IndexOutOfBoundsException 如果下标
     *         (<tt>index &lt; 0 || index &gt; size()</tt>)
     */
    void add(int index, E element);

    /**
     * 移除这个列表指定下标的元素 (可选操作)
     * 任何后续元素转移到左,即删除元素的各个右侧元素向左移动一个下标.返回从列表中删除的元素
     *
     * @param index 指定下标的元素将被移除
     * @return 返回从列表中删除的元素
     * @throws UnsupportedOperationException 如果 <tt>remove</tt> 操作
     *         在这个列表不被支持
     * @throws IndexOutOfBoundsException 如果下标
     *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    E remove(int index);


    // 搜索操作

    /**
     * 返回第一次出现指定元素的下标,或者-1如果该列表不包含指定元素.
     * 更正式, 返回最低下标 <tt>i</tt> 正如
     * <tt>(o==null?get(i)==null:o.equals(get(i)))</tt>,
     * 或者 -1 如果该列表不包含指定元素x.
     *
     * @param o 指定元素将被搜索
     * @return 第一次出现指定元素的下标,或-1如果该列表不包含该元素
     * @throws ClassCastException 如果指定元素的类型和列表元素类型不相容
     * @throws NullPointerException 如果指定元素为null,并且该列表不允许null元素
     */
    int indexOf(Object o);

    /**
     * 返回最后一次出现指定元素的下标,或者-1如果该列表不包含指定元素.
     * 更正式, 返回最低下标 <tt>i</tt> 正如
     * <tt>(o==null?get(i)==null:o.equals(get(i)))</tt>,
     * 或者 -1 如果该列表不包含指定元素x..
     *
     * @param o 指定元素将被搜索
     * @return 最后一次出现指定元素的下标,或-1如果该列表不包含该元素
     * @throws ClassCastException 如果指定元素的类型和列表元素类型不相容
     * @throws NullPointerException 如果指定元素为null,并且该列表不允许null元素
     */
    int lastIndexOf(Object o);


    // 列表迭代器

    /**
     * 返回一个列表迭代器 (适当的序列).
     *
     * @return 返回一个列表迭代器 (适当的序列).
     */
    ListIterator<E> listIterator();

    /**
     * 返回一个列表迭代器(适当的序列),起始为指定的位置.
     * 指定的下标意味着调用{@link ListIterator#next next}返回的第一个元素。
     * 调用{@link ListIterator#previous previous}将返回指定下标减一位置的元素
     *
     * @param index 指定的下标意味着调用(调用{@link ListIterator#next next})返回第一个元素
     * @return 返回一个列表迭代器(适当的序列),起始为指定的位置
     * @throws IndexOutOfBoundsException 如果下标
     *         ({@code index < 0 || index > size()})
     */
    ListIterator<E> listIterator(int index);

    // 视图

    /**
     * 返回一个指定的部分之间的这个列表视图
     * <tt>fromIndex</tt>, 包括, 和 <tt>toIndex</tt>, 不包括.  (如果
     * <tt>fromIndex</tt> 和 <tt>toIndex</tt> 相等, 返回的集合是空的
     * 返回的列表是基于该列表,所以返回列表的变化反映到在该列表。
     * 返回的列表支持的所有可选的操作得到这个列表的支持
     *
     * 这种方法不需要显示的操作范围(数组)的普遍存在。任何操作,预计可以用作范围列表操作通过子列表视图,而不是整个列表
     * 例如从列表中删除范围的元素:
     * <pre>{@code
     *      list.subList(from, to).clear();
     * }</pre>
     * 
     * @param fromIndex 低端点 (包括) 的子列表
     * @param toIndex 高端点 (不包括) 的子列表
     * @return 这个列表指定范围的视图
     * @throws IndexOutOfBoundsException 对于一个非法端点的下标值
     *         (<tt>fromIndex &lt; 0 || toIndex &gt; size ||
     *         fromIndex &gt; toIndex</tt>)
     */
    List<E> subList(int fromIndex, int toIndex);

    /**
     * 创建一个{@link Spliterator}.
     *
     * <p>{@code Spliterator} 报道 {@link Spliterator#SIZED} 并且
     * {@link Spliterator#ORDERED}.  实现文档报告附加的特征值.
     *
     * @implSpec
     * 默认实现创建一个
     * <em><a href="Spliterator.html#binding">迟绑定</a></em> spliterator
     * from the list's {@code Iterator}. spliterator继承
     * <em>fail-fast</em> 快速失败属性列表迭代器.
     *
     * @implNote实现注意事项
     * 创建{@code Spliterator}额外报道
     * {@link Spliterator#SUBSIZED}.
     *
     * @return a {@code Spliterator}
     * @since 1.8
     */
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.ORDERED);
    }
}

AbstractList

/**
 * 这个类提供了一个实现List接口骨架,以减少其他类实现List这个接口所需的努力,随机存取。顺序
 * 存取数据(比如一个链表),应该优先使用这个类{@link AbstractSequentialList}。
 * 实现一个不可修改的List,程序员只需要扩展这个类,并提供实现{@link #get(int)} 和
 * {@link List#size() size()}方法。
 * 实现一个可修改的列表,程序员必须另外覆盖{@link #set() set()}方法(否则这个方法会抛出{@code UnsupportOperationException})。 * 如果列表大小是可扩展的,程序员必须另外覆盖{@link #add(int,Object) add(int, E)}和{@link #remove(int)}方法。
 * 程序员通常提供一个无参数和一个集合参数的构造函数,按照推荐的{@link Collection}接口规范。
 * 与其他抽象实现集合不同,程序员不需要提供一个迭代器实现;这个类提供了iterator和list iterator实现,和
 * 随机存取的方法。
 * 在这个类的每个非抽象的方法文档详细描述它的实现,这些方法可能会覆盖如果集合实现一个更高效的实现
 */
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    /**
     * 唯一的构造函数(由子类的构造函数隐式的调用)
     */
    protected AbstractList() {
    }

    /**
     * 将指定元素加到列表末尾中(可选操作).  
     *
     * 集合支持限制某些元素不能被添加到这个集合操作。特别是一些集合拒绝添加null元素。
     * 和其他人将限制可能添加的元素的类型。集合类应该清楚的指定添加任何限制元素的注释文档
     * 这个实现是调用{@code add(size(),e)}
     * 注意此实现抛出一个{@code UnsupportedOperationException}除非{@link #add(int, Object)}被覆盖
     *
     * @param e 指定元素加到集合中
     * @return <tt>true</tt> 如果集合在被调用这个方法后改变
     * @throws UnsupportedOperationException 如果 <tt>add</tt> 操作
     *         在这个集合不支持
     * @throws ClassCastException 如果指定元素的类型不是集合元素类型的超类
     * @throws NullPointerException 如果指定元素是null,并且这个集合不允许添加null元素
     * @throws IllegalArgumentException 如果指定元素的某些属性可以防止它被添加到这个集合中
     */
    public boolean add(E e) {
        add(size(), e);
        return true;
    }

    /**
     * /**
     * 返回此列表的在指定位置的元素.
     *
     * @param index 下标的元素将返回
     * @return 在这个列表指定位置的元素
     * @throws IndexOutOfBoundsException 如果下标
     *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    abstract public E get(int index);

    /**
     * 取代这个列表指定位置上的元素(可选操作).
     *
     * @param index 此下标的元素将被替换
     * @param element 元素存储在指定的位置
     * @return 以前在指定位置的元素将被返回
     * @throws UnsupportedOperationException 如果 <tt>set</tt> 操作
     *         在这个列表不支持
     * @throws ClassCastException 如果指定元素的类型和列表元素类型不相容
     * @throws NullPointerException 如果指定元素是null并且这个列表不允许null元素
     * @throws IllegalArgumentException 如果指定元素的某些属性可以防止它被添加到这个集合中
     * @throws IndexOutOfBoundsException 如果下标
     *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    public E set(int index, E element) {
        throw new UnsupportedOperationException();
    }

    /**
     * 在这个列表指定位置插入指定元素(可选操作)。如果指定的位置有元素,和后续的元素都向右一个下标
     *
     * @param index 指定元素被插入的下标
     * @param element 指定元素被插入
     * @throws UnsupportedOperationException 如果 <tt>add</tt> 操作
     *         在这个列表不被支持
     * @throws ClassCastException 如果指定元素的类型和列表元素类型不相容
     * @throws NullPointerException 如果指定元素是null并且这个列表不允许null元素
     * @throws IllegalArgumentException 如果指定元素的某些属性可以防止它被添加到这个集合中
     * @throws IndexOutOfBoundsException 如果下标
     *         (<tt>index &lt; 0 || index &gt; size()</tt>)
     */
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }

    /**
     * 移除这个列表指定下标的元素 (可选操作)
     * 任何后续元素转移到左,即删除元素的各个右侧元素向左移动一个下标.返回从列表中删除的元素
     *
     * @param index 指定下标的元素将被移除
     * @return 返回从列表中删除的元素
     * @throws UnsupportedOperationException 如果 <tt>remove</tt> 操作
     *         在这个列表不被支持
     * @throws IndexOutOfBoundsException 如果下标
     *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    public E remove(int index) {
        throw new UnsupportedOperationException();
    }


    // 搜索操作

    /**
     * 返回第一次出现指定元素的下标,或者-1如果该列表不包含指定元素.
     * 更正式, 返回最低下标 <tt>i</tt> 正如
     * <tt>(o==null?get(i)==null:o.equals(get(i)))</tt>,
     * 或者 -1 如果该列表不包含指定元素x.
     *
     * <p>这个实现首先获取list iterator ({@code listIterator()}).  
     * 因此, 遍历列表,直到指定的元素被发现或遍历完列表.
     *
     * @param o 指定元素将被搜索
     * @return 第一次出现指定元素的下标,或-1如果该列表不包含该元素
     * @throws ClassCastException 如果指定元素的类型和列表元素类型不相容
     * @throws NullPointerException 如果指定元素为null,并且该列表不允许null元素
     */
    public int indexOf(Object o) {
        //获取ListIterator迭代器
        ListIterator<E> it = listIterator();
        //如果指定元素为空
        if (o==null) {
            //判断是否有下一个元素
            while (it.hasNext())
                //如果下一个元素为空
                if (it.next()==null)
                    //获取当前元素下标  
                    return it.previousIndex();
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return it.previousIndex();
        }
        return -1;
    }

    /**
     * 返回最后一次出现指定元素的下标,或者-1如果该列表不包含指定元素.
     * 更正式, 返回最低下标 <tt>i</tt> 正如
     * <tt>(o==null?get(i)==null:o.equals(get(i)))</tt>,
     * 或者 -1 如果该列表不包含指定元素x.
     * 这个实现首先获取ListIterator迭代器,指向列表的最后{@code listIterator(size())}
     * 然后向前遍历列表,直到找到指定的元素,或列表的开始
     *
     * @param o 指定元素将被搜索
     * @return 最后一次出现指定元素的下标,或-1如果该列表不包含该元素
     * @throws ClassCastException 如果指定元素的类型和列表元素类型不相容
     * @throws NullPointerException 如果指定元素为null,并且该列表不允许null元素
     */
    public int lastIndexOf(Object o) {
        ListIterator<E> it = listIterator(size());
        if (o==null) {
            while (it.hasPrevious())
                if (it.previous()==null)
                    return it.nextIndex();
        } else {
            while (it.hasPrevious())
                if (o.equals(it.previous()))
                    return it.nextIndex();
        }
        return -1;
    }


    // 批量操作

    /**
     * 从这个列表删除所有元素(可选操作).
     * 这个调用返回后列表是空的.
     *
     * <p>这个实现调用{@code removeRange(0, size())}方法.
     *
     * <p>注意这个实现抛出{@code UnsupportedOperationException}异常
     *  除非 {@code remove(int
     * index)} 或者 {@code removeRange(int fromIndex, int toIndex)} 被重写.
     *
     * @throws UnsupportedOperationException 如果{@code clear}操作
     *         在这个列表不被支持
     */
    public void clear() {
        removeRange(0, size());
    }

    /**
     * 将指定集合中的所有元素插入此列表的指定位置(可选操作)。
     * 指定位置原本如果存在元素的话,当前位置的元素和后续的元素向右(增加他们的下标)。
     * 新元素出现在这个列表的顺序,即指定集合的迭代器返回元素的顺序。
     * 这个操作的行为是未定义的,在这个方法正在进行中,如果指定的集合被修改。
     * (注意,这将发生如果这个列表指定的集合非空的)。
     * 这个实现迭代器对传入进来的集合进行遍历,从迭代器获取的元素插入在此列表的适当位置,
     * 一次一个,使用{@code add(int, E)}方法。
     * 许多实现将覆盖此方法,提供效率更高的方法
     * 
     * <p>注意这个实现抛出{@code UnsupportedOperationException}异常
     * 除非{@link #add(int, Object) add(int, E)}被重写
     *
     * @param index 插入指定集合的第一个元素的下标位置
     * @param c 集合包含元素被添加到该列表
     * @return <tt>true</tt> 如果调用该方法后列表改变
     * @throws UnsupportedOperationException 如果 <tt>addAll</tt> 操作
     *         这个列表不支持
     * @throws ClassCastException 如果指定元素的类型与这个列表元素类型不相容
     * @throws NullPointerException 如果指定的集合含有null元素,但当前列表不支持null元素
     *         或者指定的集合是null
     * @throws IllegalArgumentException 如果指定中至少有一个元素的某些属性可以防止它被添加到这个列表中
     * @throws IndexOutOfBoundsException 如果传入进来的下标index
     *         (<tt>index < 0 || index > size()</tt>)
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        //检查传入进来的下标是否在 size() >= index >= 0的范围内
        rangeCheckForAdd(index);
        //传入进来的集合是否有元素被添加到这个列表中
        boolean modified = false;
        for (E e : c) {
            add(index++, e);
            modified = true;
        }
        return modified;
    }


    // Iterators

    /**
     * 
     * 返回一个这个列表的元素序列的迭代器.
     * 
     *
     * <p>这个实现返回一个迭代器接口的简单实现,依靠列表的{@code size()},
     * {@code get(int)},  和{@code remove(int)} 方法.
     *
     * <p>注意,这个方法返回的迭代器将抛出一个{@link UnsupportedOperationException}异常以响应
     * {@code remove} 方法除非集合的{@code remove(int)} 方法被重写
     *
     * <p>这个实现可以抛出运行时异常在并发修改,按照规范,使用(protected) {@link #modCount}
     * 字段进行维护.
     *
     * @return 返回一个这个列表的元素序列的迭代器
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * 返回一个列表迭代器 (适当的序列),可以向前和向后进行遍历
     * <p>这个实现返回 {@code listIterator(0)}.
     *
     * @see #listIterator(int)
     */
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }

    /**
     * 返回一个列表迭代器 (适当的序列),可以向前和向后进行遍历
     *
     * <p>这个方法返回一个简单的实现{@code ListIterator}接口
     *  扩展实现{@code Iterator}接口,{@code iterator()}方法返回
     * 这个{@code ListIterator} 实现依靠列表的
     * {@code get(int)}, {@code set(int, E)}, {@code add(int, E)}
     * 和 {@code remove(int)} 方法.
     *
     * <p>注意,这个方法返回的迭代器将抛出一个{@link UnsupportedOperationException}异常以响应
     * {@code remove}, {@code set} 和 {@code add} 方法除非
     * 列表 {@code remove(int)}, {@code set(int, E)}, 和
     * {@code add(int, E)} 方法被重写.
     *
     * <p>这个实现可以抛出运行时异常在并发修改,按照规范,使用(protected) {@link #modCount}
     * 字段进行维护.
     *
     * @throws IndexOutOfBoundsException 如果传入进来的下标index
     *         (<tt>index < 0 || index > size()</tt>)
     */
    public ListIterator<E> listIterator(final int index) {
        //检查传入进来的下标是否在 size() >= index >= 0的范围内
        rangeCheckForAdd(index);

        return new ListItr(index);
    }

    private class Itr implements Iterator<E> {
        /**
         * 下标的元素,调用next方法将被返回.
         */
        int cursor = 0;

        /**
         * 最近调用next或者previous返回元素的下标
         * 重置为-1 如果这个元素调用remove方法被删除
         */
        int lastRet = -1;

        /**
         * modCount值在iterator迭代器,依靠列表修改值。如果违反了这种期望,迭代器检测到并发修改
         */
        int expectedModCount = modCount;
        
        /**
         * 返回 {@code true} 如果迭代器有更多的元素.
         * (换句话说, 返回 {@code true} 如果 {@link #next} 返回一个元素而不是抛出异常.)
         *
         * @return {@code true} 如果迭代有更多的元素
         */
        public boolean hasNext() {
            //当前元素下标不等于列表大小
            return cursor != size();
        }
        
        /**
         * 返回迭代的下一个元素.
         *
         * @return 返回迭代的下一个元素
         * @throws NoSuchElementException 如果迭代中没有更多的元素
         */
        public E next() {
            //检测迭代过程列表是否有并发修改
            checkForComodification();
            try {
                //调用next方法元素将被返回的下标
                int i = cursor;
                //获取到当前下标的元素
                E next = get(i);
                //记录当前被返回元素的下标,lastRet用于移除
                lastRet = i;
                //当前下标加1,返回下一个元素
                cursor = i + 1;
                //返回当前下标元素
                return next;
            } catch (IndexOutOfBoundsException e) {//如果在next方法之前没有调用hasNext方法,可能会出现下标越界
                ////检测迭代过程列表是否有并发修改
                checkForComodification();
                //抛出没有此元素NoSuchElementException异常
                throw new NoSuchElementException();
            }
        }
        
       /**
        * 删除迭代器从底层集合返回的最后一个元素 (可选操作). 这个方法可以被称为每调用一次{@link #next}.  
        * 迭代器的行为是不确定的,如果底层集合被修改在迭代过程中以任何方式除了通过调用这个方法。
        *
        * @implSpec实现规范
        * 默认实现抛出一个
        * {@link UnsupportedOperationException} 并且没有执行任何操作.
        *
        * @throws UnsupportedOperationException 如果 {@code remove}
        *         操作在这个迭代器不支持
        *
        * @throws IllegalStateException 如果 {@code next} 方法从来没有
        *         被调用, 或者 {@code remove} 方法总是在最后调用 {@code next}
        *         方法后调用,即next已经没有元素,remove会报IllegalStateException
        */
        public void remove() {
            // 如果{@code next}方法从来没有被调用
            if (lastRet < 0)
                throw new IllegalStateException();
            //检测迭代过程列表是否有并发修改  
            checkForComodification();

            try {
                //调用底层列表的remove方法
                AbstractList.this.remove(lastRet);
                //如果cursor大于lastRet,即迭代器是Iterator,调用next方法,cursor会指向下一个元素下标,lastRet指向当前元素下标
                //如果迭代器是LastIterator,调用previous方法, lastRet和cursor会相等,remove时,下标cursor无需移动
                if (lastRet < cursor)                   
                    cursor--;
                //将最近返回的下标置为-1
                lastRet = -1;
                //重新将列表的modCount赋值给迭代器的expectedModCount
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {//如果在移除的过程中,列表存在并发修改
                throw new ConcurrentModificationException();
            }
        }
        
        //检查迭代器在遍历的过程中,列表是否存在并发修改
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    private class ListItr extends Itr implements ListIterator<E> {
        //传入下标index,即迭代器从哪个位置开始往前开始遍历,或者next方法调用返回的元素
        ListItr(int index) {
            cursor = index;
        }
        
        //判断迭代器是否还有前一个元素
        public boolean hasPrevious() {
            return cursor != 0;
        }
        
        //返回前一个元素
        public E previous() {
            //判断迭代器在遍历的过程中是否有并发修改
            checkForComodification();
            try {
                //当前下标-1。如果
                int i = cursor - 1;
                //获取前一个元素
                E previous = get(i);
                //记录最近访问的下标
                lastRet = cursor = i;
                //返回前一个元素
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }
        
        //下一个元素下标,即调用next方法返回的元素
        public int nextIndex() {
            return cursor;
        }
        
        //上一个元素下标,即调用previous方法返回的元素
        public int previousIndex() {
            return cursor-1;
        }
        
        //替换最近访问过的下标的元素
        public void set(E e) {
            //如果next方法没有被调用过,抛出IllegalStateException异常
            if (lastRet < 0)
                throw new IllegalStateException();
            //判断列表是否存在并发修改
            checkForComodification();
            
            try {
                //调用底层列表的set方法
                AbstractList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            //判断列表是否存在并发修改
            checkForComodification();

            try {
                //获取调用next方法返回元素的下标
                int i = cursor;
                //将指定的元素添加到这个下标,这个位置的元素及后续的元素都往后移一位
                AbstractList.this.add(i, e);
                //记录最近访问的lastRet置为-1
                lastRet = -1;
                //获取调用next方法返回元素的下标+1,这样才能获取到原本要访问的元素
                cursor = i + 1;
                //将迭代器的expectedModCount重新赋值为列表的modCount
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

    /**
     * {@inheritDoc}
     *
     * <p>这个实现返回一个列表,{@code AbstractList}的子类
     * 这个返回的子类, 有一个私有的属性, offset属性
     * 子列表的大小(可以改变在它的生命周期),以及预期的{@code modCount}值
     * 有两个不同的子类,其中一个实现了{@code RandomAccess}。如果该列表实现了{@code RandomAccess}
     * 返回的子列表也将实现{@code RandomAccess}。
     * 
     * <p>这个子类 {@code set(int, E)}, {@code get(int)},
     * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
     * Collection)} 和 {@code removeRange(int, int)} 的所有方法委托给基于的列表方法
     * 
     * 
     * {@code addAll(Collection c)} 方法相当于 {@code addAll(size,
     * c)}.
     * 
     * <p>这个 {@code listIterator(int)} 方法返回一个封装的迭代器对象
     * 基于这个列表.{@code iterator}方法
     * 相当于调用 {@code listIterator()}, 并且 {@code size} 方法
     * 相当于返回子类的 {@code size} 属性.
     *
     * <p>所有的方法首先检查真实的{@code modCount}基于这个列表是否等于期望的值, 如果不是的话抛出
     * {@code ConcurrentModificationException}异常.
     *
     * @throws IndexOutOfBoundsException 如果指定的下标值超出范围
     *         {@code (fromIndex < 0 || toIndex > size)}
     * @throws IllegalArgumentException 如果指定的fromIndex和toIndex
     *         {@code (fromIndex > toIndex)}
     */
    public List<E> subList(int fromIndex, int toIndex) {
        return (this instanceof RandomAccess ?
                new RandomAccessSubList<>(this, fromIndex, toIndex) :
                new SubList<>(this, fromIndex, toIndex));
    }

    // 比较 和 哈希

    /**
     * 比较指定的对象是否和这个列表相等.  返回
     * {@code true} 当且仅当指定的对象是个列表, 并且
     * 和这个列表有相同的元素大小, 并且两个列表的元素
     * <i>equal</i>相等.  (两个 元素 {@code e1} 和
     * {@code e2} <i>equal</i> 如果 {@code (e1==null ? e2==null :
     * e1.equals(e2))}.)  换句话说, 两个列表被定义成相等
     * 如果他们包含相同的元素并且相同的元素有一样的顺序.<p>
     *
     * 这个实现首先检查指定的对象是此列表. 如果是返回{@code true}; 否则的话, 检查
     * 指定的对象是否是个列表. 如果不是, 返回{@code false}; 如果,
     * 遍历两个列表, 比较列表中的元素.
     * 如果有任何一个元素比较不相等返回 {@code false}, 这个方法返回
     * {@code false}. 如果两个列表的元素长度不相等返回{@code false} ;
     * 否则返回 {@code true}.
     *
     * @param o 指定的对象将和这个列表比较
     * @return {@code true} 如果指定的元素和这个列表相等
     */
    public boolean equals(Object o) {
        //指定的对象是否是这个列表 
        if (o == this)
            //如果是返回true
            return true;
        //判断指定的对象是否是个列表 
        if (!(o instanceof List))
            //如果不是直接返回false
            return false;
        //获取这个列表的迭代器
        ListIterator<E> e1 = listIterator();
        //获取指定对象的迭代器 
        ListIterator<?> e2 = ((List<?>) o).listIterator();
        //遍历两个列表的元素。判断每个元素是否相等
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        //如果两个列表有不同的长度,返回false
        return !(e1.hasNext() || e2.hasNext());
    }

    /**
     * 返回此列表的哈希码.
     *
     * @return 这个列表的哈希码值
     */
    public int hashCode() {
        //默认hashCode为1
        int hashCode = 1;
        //遍历列表元素 
        for (E e : this)
            //基数31是为了哈希减少冲突
            hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
        return hashCode;
    }

    /**
     * 从这个列表中删除指定下标范围内的所有元素
     * {@code fromIndex}, 包含, 和 {@code toIndex}, 不包含.
     * toIndex右侧的所有元素左移一个下标 (减少他们的下标),包括toIndex元素.
     * 这叫缩短这个列表这个范围内{@code (toIndex - fromIndex)} 元素.
     * (如果 {@code toIndex==fromIndex}, 这个操作不受影响.)
     *
     * <p>在list和subLists的{@code clear}调用此方法
     * 在这个列表和子列表重写这个方法利用内部实现,可以大幅提高性能
     *
     * <p>这个实现获得列表迭代器,位置从{@code fromIndex}
     * 并且重复的调用{@code ListIterator.next},随后调用{@code ListIterator.remove}
     * 直到整个范围被移除。
     * <b>注意: 如果 {@code ListIterator.remove} 要求线性的时间,
     * 这个实现需要平方的时间.</b>
     *
     * @param fromIndex 第一个被移除元素的下标
     * @param toIndex 最后一个被移除元素的下标(不包括)
     */
    protected void removeRange(int fromIndex, int toIndex) {
        //获取可以前后遍历的ListIterator迭代器,遍历的位置从fromIndex开始
        ListIterator<E> it = listIterator(fromIndex);
        //删除fromIndex到toIndex的所有元素,toIndex不包括
        for (int i=0, n=toIndex-fromIndex; i<n; i++) {
            //调用next方法,将lastRet设置为cursor
            it.next();
            //将lastRet位置的元素删除
            it.remove();
        }
    }
    
    /**
     * 这个值是列表结构被修改的次数。结构修改是改变列表的大小,或者扰乱迭代过程中可能产生不正确的结果
     * 这个属性被用在iterator和list iterator实现,由{@code iterator} 和 {@code listIterator}方法返回
     * 如果这个字段的值变化出乎意料,iterator或者list iterator将会抛出{@code ConcurrentModificationException}异常做为响应
     * 在 {@code next}, {@code remove}, {@code previous},
     * {@code set} 或者 {@code add}操作。这提供了快速失败的行为,而不是不确定的行为在迭代期间并发修改
     * 子类使用这个字段是可选的。如果子类希望提供快速失败的iterator和list iterator,
     * 那么仅仅增加这个字段在{@code add(int, E)}和{@code remove(int)}方法(和任何其他方法,它覆盖,导致列表结构修改) 
     */
    protected transient int modCount = 0;
    
    //在增加元素的时候检查传入进来的index是否超出范围,add的位置只能在0<=index<=size()
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size())
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    //传入下标,记录下标越界信息
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size();
    }
}

class SubList<E> extends AbstractList<E> {
    //创建SubList的列表
    private final AbstractList<E> l;
    //偏移量,AbstractList偏移量 
    private final int offset;
    //SubList元素个数
    private int size;
    
    /**
     * 创建SubList,只在subList(int fromIndex, int toIndex)方法调用
     * 
     * @param list 创建SubList的列表
     * @param fromIndex 起始位置,包括
     * @param toIndex 结束位置,不包括
     * @throws IndexOutOfBoundsException 如果指定的下标值超出范围
     *         {@code (fromIndex < 0 || toIndex > size)}
     * @throws IllegalArgumentException 如果指定的fromIndex和toIndex
     *         {@code (fromIndex > toIndex)}
     */
    SubList(AbstractList<E> list, int fromIndex, int toIndex) {
        //如果起始下标小于0
        if (fromIndex < 0)
            //抛出IndexOutOfBoundsException异常
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        //如果结束位置大于元素大小
        if (toIndex > list.size())
            //抛出IndexOutOfBoundsException异常 
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        //如果起始位置大于结束位置
        if (fromIndex > toIndex)
            //抛出IllegalArgumentException
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
        l = list;
        offset = fromIndex;
        size = toIndex - fromIndex;
        this.modCount = l.modCount;
    }
    
    /**
     * 设置index下标元素
     * @param index 要设置元素下标
     * @param element 要设置的元素
     * @return 返回index下标原有的元素
     */
    public E set(int index, E element) {
        //检查下标是否在 size > index > 0 
        rangeCheck(index);
        //检查列表是否并发修改
        checkForComodification();
        //调用创建SubList的列表set方法,index和偏移量
        return l.set(index+offset, element);
    }
    
    /**
     * 获取index下标元素
     * @param index 要获取的元素下标
     * @return 返回index下标的元素
     */
    public E get(int index) {
        //检查下标是否在 size > index > 0 
        rangeCheck(index);
        //检查列表是否并发修改
        checkForComodification();
        //调用创建SubList的列表get方法,index和偏移量
        return l.get(index+offset);
    }
    
    /**
     * 获取当前列表存在元素
     */
    public int size() {
        //检查列表是否并发修改
        checkForComodification();
        //返回当前列表存在元素
        return size;
    }
    
    /**
     * 在这个列表指定位置添加指定元素(可选操作)。如果指定的位置有元素,和后续的元素都向右一个下标
     */ 
    public void add(int index, E element) {
        //检查下标是否在 size > index > 0 
        rangeCheckForAdd(index);
        checkForComodification();
        l.add(index+offset, element);
        this.modCount = l.modCount;
        size++;
    }

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

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

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

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

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

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

    public ListIterator<E> listIterator(final int index) {
        checkForComodification();
        rangeCheckForAdd(index);

        return new ListIterator<E>() {
            private final ListIterator<E> i = l.listIterator(index+offset);

            public boolean hasNext() {
                return nextIndex() < size;
            }

            public E next() {
                if (hasNext())
                    return i.next();
                else
                    throw new NoSuchElementException();
            }

            public boolean hasPrevious() {
                return previousIndex() >= 0;
            }

            public E previous() {
                if (hasPrevious())
                    return i.previous();
                else
                    throw new NoSuchElementException();
            }

            public int nextIndex() {
                return i.nextIndex() - offset;
            }

            public int previousIndex() {
                return i.previousIndex() - offset;
            }

            public void remove() {
                i.remove();
                SubList.this.modCount = l.modCount;
                size--;
            }

            public void set(E e) {
                i.set(e);
            }

            public void add(E e) {
                i.add(e);
                SubList.this.modCount = l.modCount;
                size++;
            }
        };
    }

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

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

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

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

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

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
        super(list, fromIndex, toIndex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<>(this, fromIndex, toIndex);
    }
}

三、属性

四、构造函数

五、内部类