程序员的自我修养

/**
 * This class implements the <tt>Set</tt> interface, backed by a hash table
 * (actually a <tt>HashMap</tt> instance).  It makes no guarantees as to the
 * iteration order of the set; in particular, it does not guarantee that the
 * order will remain constant over time.  This class permits the <tt>null</tt>
 * element.
 * 该类是由 hash table(实际上是 HashMap 实例) 支持的 Set 接口的实现类。它不能保证 set 的迭代顺序；特别是，它不保证 set 内元素的顺序随着时间的变化不会改变。该类允许(添加) null 元素。
 * <p>This class offers constant time performance for the basic operations
 * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
 * assuming the hash function disperses the elements properly among the
 * buckets.  Iterating over this set requires time proportional to the sum of
 * the <tt>HashSet</tt> instance's size (the number of elements) plus the
 * "capacity" of the backing <tt>HashMap</tt> instance (the number of
 * buckets).  Thus, it's very important not to set the initial capacity too
 * high (or the load factor too low) if iteration performance is important.
 * 该类的基本操作(add，remove，contains 和 size)提供O(1)的级别的性能表现，假设 hash 方法将元素均匀的分布在桶中。遍历整个 set 所需的时间与 HashSet 实例的 size(元素数量) * (底层 HashMap 实例的 capacity(桶的数量)) 成正比。
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a hash set concurrently, and at least one of
 * the threads modifies the set, it <i>must</i> be synchronized externally.
 * This is typically accomplished by synchronizing on some object that
 * naturally encapsulates the set.
 * 参见 HashMap
 * If no such object exists, the set should be "wrapped" using the
 * {@link Collections#synchronizedSet Collections.synchronizedSet}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the set:<pre>
 *   Set s = Collections.synchronizedSet(new HashSet(...));</pre>
 * 参见 HashMap
 * <p>The iterators returned by this class's <tt>iterator</tt> method are
 * <i>fail-fast</i>: if the set is modified at any time after the iterator is
 * created, in any way except through the iterator's own <tt>remove</tt>
 * method, the Iterator throws a {@link ConcurrentModificationException}.
 * Thus, in the face of concurrent modification, the iterator fails quickly
 * and cleanly, rather than risking arbitrary, non-deterministic behavior at
 * an undetermined time in the future.
 * 参见 HashMap
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness: <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 * 参见 HashMap
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @param <E> the type of elements maintained by this set
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Collection
 * @see     Set
 * @see     TreeSet
 * @see     HashMap
 * @since   1.2
 */
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
// 由 Map 接口支持的虚拟对象
private static final Object PRESENT = new Object();

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 * 构造一个新的空的 set；提供底层支持的 HashMap 实例的 默认初始 capacity 为 16，负载因子为 0.75。
 */
public HashSet() {
    map = new HashMap<>();
}

/**
 * Constructs a new set containing the elements in the specified
 * collection.  The <tt>HashMap</tt> is created with default load factor
 * (0.75) and an initial capacity sufficient to contain the elements in
 * the specified collection.
 * 构造一个包含指定 collection 中的元素的新 set 实例。
 * @param c the collection whose elements are to be placed into this set
 * @throws NullPointerException if the specified collection is null
 */
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}
/**
 * {@inheritDoc}
 * 该方法继承自 AbstractCollection(即，HashSet 没有重写 addAll()，直接指向的是 AbstractCollection.addAll()方法) 
 * <p>This implementation iterates over the specified collection, and adds
 * each object returned by the iterator to this collection, in turn.
 * 该方法实现遍历整个指定的 collection，并且将 collection 的 iterator 返回的每个 对象按顺序添加到 set 中。
 * <p>Note that this implementation will throw an
 * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
 * overridden (assuming the specified collection is non-empty).
 * 需要注意的是，这个方法实现会抛出一个 UnsupportedOperationException 异常，除非 add() 被重写(假设指定的 collection 是非空的)。
 * @throws UnsupportedOperationException {@inheritDoc}
 * @throws ClassCastException            {@inheritDoc}
 * @throws NullPointerException          {@inheritDoc}
 * @throws IllegalArgumentException      {@inheritDoc}
 * @throws IllegalStateException         {@inheritDoc}
 *
 * @see #add(Object)
 */
public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}
/**
 * Adds the specified element to this set if it is not already present.
 * More formally, adds the specified element <tt>e</tt> to this set if
 * this set contains no element <tt>e2</tt> such that
 * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
 * If this set already contains the element, the call leaves the set
 * unchanged and returns <tt>false</tt>.
 * 添加指定元素到 set 中，如果 set 中还没有该元素。严谨来说，添加一个元素 e 到该 set 中，如果 set 中不存在一个满足这样条件的 (e2: e==null ? e2==null : e.equals(e2)).如果 set 中已经存在一个这样的元素，当次调用不会改变 set，并且放回 false。
 * @param e element to be added to this set
 * @return <tt>true</tt> if this set did not already contain the specified
 * element
 */
public boolean add(E e) {
    // map.put() 返回 null，说明添加新值成功；否则说明添加的元素发生哈希碰撞，或者是重复添加相同元素。
    // 另外，需要注意到的是 PRESENT，即影子对象，没有实际意义，纯粹为了填充 value。
    return map.put(e, PRESENT)==null;
}
    
/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * the specified initial capacity and the specified load factor.
 * 构建一个新的空的 set；指定构建由底层提供支持的 HashMap 实例时的初始容量，和负载因子。
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * the specified initial capacity and default load factor (0.75).
 * 构建一个新的空 set；指定构建由底层提供支持的 HashMap 实例时的初始容量，负载因子默认为 0.75.
 * @param      initialCapacity   the initial capacity of the hash table
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero
 */
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
/**
 * Constructs a new, empty linked hash set.  (This package private
 * constructor is only used by LinkedHashSet.) The backing
 * HashMap instance is a LinkedHashMap with the specified initial
 * capacity and the specified load factor.
 * 构建一个新的空 Linked Hash set。(这个包级作用域私有的构造器只能被 LinkedHashSet 使用)。底层提供支持的 HashMap 实例是一个 由指定初始容量和指定负载因子的 LinkedHashMap。
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @param      dummy             ignored (distinguishes this
 *             constructor from other int, float constructor.)
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

/**
 * Resizable-array implementation of the <tt>List</tt> interface.  Implements
 * all optional list operations, and permits all elements, including
 * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
 * this class provides methods to manipulate the size of the array that is
 * used internally to store the list.  (This class is roughly equivalent to
 * <tt>Vector</tt>, except that it is unsynchronized.)
 * (ArrayList) 通过 List 接口实现的容量可变数组。实现了 list 的所有可选操作(方法)，并且允许添加所有元素，包括 null。除了实现了 List 的接口，ArrayList 还提供了修改用来容纳 list 的数组的 size 的方法(ArrayList 是非线程安全的，除此以外大致上与 Vector 相同)。
 * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
 * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
 * that is, adding n elements requires O(n) time.  All of the other operations
 * run in linear time (roughly speaking).  The constant factor is low compared
 * to that for the <tt>LinkedList</tt> implementation.
 * size，isEmpty，get，set，iterator 方法和 listIterator 操作的时间复杂度是O(1)的(常数级)。add() 方法的时间复杂度是O(1)+的(amortized constant time)(因为涉及到list 扩容，扩容也需要时间，需要把这部分时间平均分摊到每次 add 操作中。)，也就是说，添加元素的时间复杂度为O(n)。其他操作的时间复杂度大致为O(n)，常量值 n 通常要比 LinkedList 的时间复杂度中常量值要小(即，其他操作要比 LinkedList 的其他操作要快一点)。
 * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
 * the size of the array used to store the elements in the list.  It is always
 * at least as large as the list size.  As elements are added to an ArrayList,
 * its capacity grows automatically.  The details of the growth policy are not
 * specified beyond the fact that adding an element has constant amortized
 * time cost.
 * 每一个 ArrayList 实例都有一个 capacity(容量)属性，该属性不小于 list 的 size。当向 ArrayList 中添加元素时，它的 capacity 会自动增长。除了添加一个元素具有固定的摊余时间成本之外，增长规则的细节没有被指定。
 * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
 * before adding a large number of elements using the <tt>ensureCapacity</tt>
 * operation.  This may reduce the amount of incremental reallocation.
 * 在程序中添加大量元素之前，可以调用 ensureCapacity() 方法来对 ArrayList 进行扩容。这样可以减少多次扩容所花费的时间(可以减少扩容的次数)
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
 * and at least one of the threads modifies the list structurally, it
 * <i>must</i> be synchronized externally.  (A structural modification is
 * any operation that adds or deletes one or more elements, or explicitly
 * resizes the backing array; merely setting the value of an element is not
 * a structural modification.)  This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the list.
 * 需要注意的是，ArrayList 对 List 的实现是非同步的。如果多线程同时请求对 ArrayList 的访问，并且至少会有一个线程对 ArrayList 进行结构性修改(结构性修改是指添加或删除一个以上的元素，或者显式的修改了其数组的大小。仅仅修改元素值并非结构性修改)，那么务必在 ArrayList 外部进行 synchronized 修饰。这通常是通过 synchronized 修饰 封装了 list 的某个对象来实现的。
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
 * 如果(手头儿)没有这样的对象，那么应该用 Collections.synchronizedList 包裹 list。该操作最好在创建 list 时进行，以防意外的非同步访问 list。
 * <p><a name="fail-fast"/>
 * The iterators returned by this class's {@link #iterator() iterator} and
 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
 * if the list is structurally modified at any time after the iterator is
 * created, in any way except through the iterator's own
 * {@link ListIterator#remove() remove} or
 * {@link ListIterator#add(Object) add} methods, the iterator will throw a
 * {@link ConcurrentModificationException}.  Thus, in the face of
 * concurrent modification, the iterator fails quickly and cleanly, rather
 * than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 * 通过 ArrayList 的 iterator() 方法，或者 listIterator(int) 方法返回的 iterator 都是 fail-fast(快速失效)的：如果在创建 iterator 之后，任何对 list 的结构性修改，都会抛出 ConcurrentModificationException，除了 iterator 本身的 remove() 和 add() 方法。因此，在面临并发对 list 的修改时，iterator 会快速而干净的失效，而不是在未来不确定的时间冒着任意的、不确定的风险。
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:  <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 * 另外，需要注意的是，，iterator 的 fail-fast 行为是不能被保证的，，通常来说，在并发非同步对 list 的修改时，任何硬性的保证都是不可能的。fail-fast 会让 iterator 尽可能抛出 ConcurrentModificationException。因此，在程序中通过依赖抛出 ConcurrentModificationException 异常来保证自身的正常运行是错误的：fail-fast 行为只应该用来 debug。
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @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

/**
 * Default initial capacity.
 * 默认初始 capacity, 10
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 * 对所有由无参构造函数创建的空实例共享的空数组对象
 */
private static final Object[] 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 == EMPTY_ELEMENTDATA will be expanded to
 * DEFAULT_CAPACITY when the first element is added.
 * 临时用来存储 ArrayList 中元素的数组。 ArrayList 对象的长度就是这个缓存数组的长度。任何空 ArrayList ，且 elementData == EMPTY_ELEMENTDATA，在添加第一个元素时，数组将被扩展到默认大小(DEFAULT_CAPACITY, 10)。
 * (因为是临时的，所以用 transient 修饰，不会被序列化)
 */
private transient Object[] elementData;

/**
 * The size of the ArrayList (the number of elements it contains).
 * ArrayList 的 size(包含的元素的数量)。
 * @serial
 */
private int size;

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 * 允许分配给数组的最大的容量。
 * 一些虚拟机实现会在数组预留一些 header words。
 * 视图分配更大的数组可能会造成 OOM：所需数组大小超出虚拟机限制。
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Constructs an empty list with the specified initial capacity.
 * 通过指定初始 capacity 大小来构造一个空 list
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    super();
    // 初始容量小于零时，会抛出 IllegalArgumentException
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    //  初始化指定大小的临时对象数组                                       
    this.elementData = new Object[initialCapacity];
}

/**
 * Constructs an empty list with an initial capacity of ten.
 * 构造一个空 list，当向该 list 添加元素时，需先扩展数组到默认初始容量大小，即 10.
 */
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * 按照 collection 迭代器返回元素的顺序构造包含指定 collection 的元素的 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) {
    // 如果 c 为 null，此处会抛 NPE
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    // 如果 elementData 不是对象数组，还需要将其复制到新的对象数组中。
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

/**
 * Doubly-linked list implementation of the {@code List} and {@code Deque}
 * interfaces.  Implements all optional list operations, and permits all
 * elements (including {@code null}).
 * 该双向链表实现了 List 接口和 Deque 接口。实现了 list 的所有可选操作，并且允许(添加)所有元素(包括 null)。
 * <p>All of the operations perform as could be expected for a doubly-linked
 * list.  Operations that index into the list will traverse the list from
 * the beginning or the end, whichever is closer to the specified index.
 * 对于该双向链表，所有操作都是可预期的。如果对 list 的操作涉及到指定索引位置的元素，那么将判断指定的索引离 begin 更近，还是离 end 更近。这样能进行更少次数的迭代，性能更好。
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a linked list concurrently, and at least
 * one of the threads modifies the list structurally, it <i>must</i> be
 * synchronized externally.  (A structural modification is any operation
 * that adds or deletes one or more elements; merely setting the value of
 * an element is not a structural modification.)  This is typically
 * accomplished by synchronizing on some object that naturally
 * encapsulates the list.
 * 需要注意的是 LinkedList 类并不是线程安全的。如果多线程同时访问 linked list，而且至少一个线程会修改 list 的结构，那么它的外部必须使用 synchronized 关键字。(结构性修改指的是 插入(add)或者删除(remove)操作，修改一个元素的值并不是结构性修改)。这通常通过同步(synchronized 修饰)一个 封装了 list 的对象来实现。
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new LinkedList(...));</pre>
 * 如果手头儿没有这样的对象，list 应该被 Collections.synchronizedList() 包裹起来。最好在初始化 LinkedList 对象时候就这样去做，以免不可预知的对 list 的非同步访问。
 * <p>The iterators returned by this class's {@code iterator} and
 * {@code listIterator} methods are <i>fail-fast</i>: if the list is
 * structurally modified at any time after the iterator is created, in
 * any way except through the Iterator's own {@code remove} or
 * {@code add} methods, the iterator will throw a {@link
 * ConcurrentModificationException}.  Thus, in the face of concurrent
 * modification, the iterator fails quickly and cleanly, rather than
 * risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 * 通过LinkedList 的 iterator() 方法，或者 listIterator(int) 方法返回的 iterator 都是 fail-fast(快速失效)的：如果在创建 iterator 之后，任何对 list 的结构性修改，都会抛出 ConcurrentModificationException，除了 iterator 本身的 remove() 和 add() 方法。因此，在面临并发对 list 的修改时，iterator 会快速而干净的失效，而不是在未来不确定的时间冒着任意的、不确定的风险。
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:   <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 * 另外，需要注意的是，，iterator 的 fail-fast 行为是不能被保证的，，通常来说，在并发非同步对 list 的修改时，任何硬性的保证都是不可能的。fail-fast 会让 iterator 尽可能抛出 ConcurrentModificationException。因此，在程序中通过依赖抛出 ConcurrentModificationException 异常来保证自身的正常运行是错误的：fail-fast 行为只应该用来 debug。
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author  Josh Bloch
 * @see     List
 * @see     ArrayList
 * @since 1.2
 * @param <E> the type of elements held in this collection
 */
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

transient int size = 0;

/**
 * Pointer to first node. // 指向 LinkedList 的第一个节点
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node. // 指向 LinkedList 的最后一个节点
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

/**
 * Constructs an empty list.
 * 构造一个空 list
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * 通过指定的 collection 构造一个包含元素的 list，其顺序由 collection 的迭代器决定。
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

/**
 * 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.  (Note that this will occur if the specified collection is
 * this list, and it's nonempty.)
 * 将指定的 collection 的所有元素拼接到 list 的末尾元素之后，顺序由指定的 collection 的迭代器决定。在执行该操作(addAll())的时候，如果 collection 被修改了，该操作的行为将不可预知(请注意，如果指定的 collection 正好是该 list 对象自己，那么这种情况将会发生)。
 * @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) {
    return addAll(size, c);
}

/**
 * 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.
 * 从指定的位置开始将指定 collection 中的所有元素插入到该 list 中。指定位置的元素(如果有的话)及其右边的元素将会右移(原索引值增大)。新的元素将会以指定 collection 的迭代器 返回的顺序出现在 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 {@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) {
    // 判断索引是否非法
    checkPositionIndex(index);

    // 将 collection 转为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 如果为空数组，返回 false
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    // 如果索引值与容器的大小相同，即当前 LinkedList 实例中无任何元素
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        // 构建 Node 节点对象 newNode
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果指定位置的元素位于列表头部，则 newNode 为 first 节点
        if (pred == null)
            first = newNode;
        else
            // 否则，前一个节点的 next 属性指向 newNode
            pred.next = newNode;
        // pred 指向 newNode，开始下一轮遍历(相当于常规 for 循环的 i++)
        pred = newNode;
    }

    // 如果原 list 为空列表，则经过遍历之后，last 指向 pred
    if (succ == null) {
        last = pred;
    } else {
        // 如果指定索引位置有值，遍历添加 collection 中的元素之后，指定索引位置的元素及其右侧的所有元素统一右移，，将新增的所有元素中的最后一个元素的 next 指向 右移的元素中的第一个元素；右移的元素中的第一个元素的 prev 属性指向新增元素中的最后一个。
        pred.next = succ;
        succ.prev = pred;
    }

    // 原 size 加上 新增元素的数量
    size += numNew;
    // list 的结构性更改次数 +1
    modCount++;
    return true;
}

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 * Tells if the argument is the index of a valid position for an
 * iterator or an add operation.
 * 判断参数代表的索引位置在 iterator 或者 add() 中是否可用
 */
private boolean isPositionIndex(int index) {
    // 不小于零，且不大于 size
    return index >= 0 && index <= size;
}

/**
 * Returns the (non-null) Node at the specified element index.
 * 返回指定位置的非空节点
 * 此处遍历 list 查找指定位置的元素时，先判断 index 距离 begin 节点近还是 end 节点。如此可以减少遍历次数，有助于性能表现。大概这就是维护成双向列表而非单向列表的原因吧。
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    // 指定的索引值是否小于中位数(翻译成人话就是，判断索引是否在列表的前半段)
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 就是硬遍历，直到指定索引位置
        //  因为 i < index，所以会遍历到指定索引位置的前一个节点，这时取其 next 指向的节点即可。
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

// 私有静态内部类
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        // item 为当前节点的值
        this.item = element;
        // next 指向当前节点的下一个节点
        this.next = next;
        // prev 指向当前节点的前一个节点
        this.prev = prev;
    }
}