/**

      * Constructs an empty list.

      */

     public LinkedList() {

     }

     /**

      * Constructs a list containing the elements of the specified

      * collection, in the order they are returned by the collection's

      * iterator.

      *

      * @param  c the collection whose elements are to be placed into this list

      * @throws NullPointerException if the specified collection is null

      */

     public LinkedList(Collection c) {

         // 调用无参构造，其实就是个空方法

         this();

         // 添加全部元素至 LinkedList

         addAll(c);

     }

     //addAll 方法，此时对于新建的 LinkedList 实例， size=0

     public boolean addAll(Collection 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.

      *

      * @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 c) {

         // 越界检查

         checkPositionIndex(index);

         // 将 Collection 入参转换为数组

         Object[] a = c.toArray();

         // 检查入参中是否包含元素，如果返回 false ，说明有参构造的 Collection 参数不包含元素

         int numNew = a.length;

         if (numNew == 0)

             return false;

         // 链表节点 Node

         Node pred, succ;

         // 验证 index 是否 ==size ，如果等于，则在链表 last 元素后追加新元素

         if (index == size) {

             succ = null;

             pred = last;

         } else {

             // 如不等于，则获取下标为 index 元素，

             succ = node(index);

             pred = succ.prev;

         }

         // 循环入参中的元素

         for (Object o : a) {

             @SuppressWarnings("unchecked") E e = (E) o;

             // 新建一个节点，外汇跟单gendan5.com不包含 next 下一节点

             Node newNode = new Node<>(pred, e, null);

             如果新建节点 next==null ，说明是头节点

             if (pred == null)

                 first = newNode;

             else

                 // 否则，将前节点的 next 引用指向新建节点

                 pred.next = newNode;

             pred = newNode;

         }

         // 循环结束，如果传入 index 为链表长度，最后一次循环得到 pred 就是尾节点

         if (succ == null) {

             last = pred;

         } else {

             // 如果 index 不等于 size ，说明是从中间插入的，最后一个元素也有下一节点

             // 该下一节点就是之前下标为 index 的元素

             pred.next = succ;

             succ.prev = pred;

         }

         // 链表元素数量增加

         size += numNew;

         // 迭代器需要用到的修改次数，若不为 0 ，使用迭代器遍历会报错

         modCount++;

         return true;

     }

     // 越界检查

     private void checkPositionIndex(int index) {

         if (!isPositionIndex(index))

             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

     }

     // 越界检查

     private boolean isPositionIndex(int index) {

         return index >= 0 && index <= size;

     }

     // 链表中节点，包含自身引用及前后节点引用

     // 这样，链表中的节点便是包含前一节点和后一节点引用 ( 除去首尾节点 )

     private static class Node {

         E item;

         Node next;

         Node prev;

         Node(Node prev, E element, Node next) {

             this.item = element;

             this.next = next;

             this.prev = prev;

         }

     }

     /**

      * Returns the (non-null) Node at the specified element index.

      * 返回指定位置的非空节点

      * 节点如果为空

      */

     Node node(int index) {

         // assert isElementIndex(index);

         //index 大于 size 的一半，则从链表头部开始向下遍历处理

         if (index < (size >> 1)) {

             Node x = first;

             // 从头遍历，找到下标为 index 的元素（同数组的下标）

             // 也就是说秒如果 index=4 ，得到的，是第五个元素

             for (int i = 0; i < index; i++)

                 x = x.next;

             return x;

         } else {

             // 否则，则从链表尾部开始向上遍历处理

             Node x = last;

             // 从尾巴节点的前节点开始找，假如 size=8.index = 6. 实际得到的，相当于数组中下标为 7 的元素

             for (int i = size - 1; i > index; i--)

                 x = x.prev;

             return x;

         }

     }