LinkedList源码解析（基于JDK1.8）

LinkedList将做为双链表来实现，它本身实现了List接口和Deque接口，并且实现了所有可选的列表操作，并且允许包含所有元素（包括null）。

下图是LinkedList的UML图：

从图中我们可以看出：

1. 继承了AbstractSequentialList抽象类：在遍历LinkedList的时候，官方更推荐使用顺序访问，也就是使用我们的迭代器。（因为LinkedList底层是通过一个链表来实现的）（虽然LinkedList也提供了get（int index）方法，但是底层的实现是：每次调用get（int index）方法的时候，都需要从链表的头部或者尾部进行遍历，每一的遍历时间复杂度是O(index)，而相对比ArrayList的底层实现，每次遍历的时间复杂度都是O(1)。所以不推荐通过get（int index）遍历LinkedList。至于上面的说从链表的头部后尾部进行遍历：官方源码对遍历进行了优化：通过判断索引index更靠近链表的头部还是尾部来选择遍历的方向）（所以这里遍历LinkedList推荐使用迭代器）。
2. 实现了List接口。（提供List接口中所有方法的实现）
3. 实现了Cloneable接口，它支持克隆（浅克隆），底层实现：LinkedList节点并没有被克隆，只是通过Object的clone（）方法得到的Object对象强制转化为了LinkedList,然后把它内部的实例域都置空，然后把被拷贝的LinkedList节点中的每一个值都拷贝到clone中。（后面有源码解析）
4. 实现了Deque接口。实现了Deque所有的可选的操作。

5. 实现了Serializable接口。表明它支持序列化。（和ArrayList一样，底层都提供了两个方法：readObject（ObjectInputStream o）、writeObject（ObjectOutputStream o），用于实现序列化，底层只序列化节点的个数和节点的值）。

   后面的源代码分析太多，这里直接把总结部分放到最前面了。

   总结：

   ①LinkedList底层是一个双链表。是一个直线型的链表结构。
   ②LinkedList内部实现了6种主要的辅助方法：void linkFirst(E e)、void linkLast(E e)、linkBefore(E e, Node<E> succ)、E unlinkFirst(Node<E> f)、E unlinkLast(Node<E> l)、E unlink(Node<E> x)。它们都是private修饰的方法或者没有修饰符，表明这里都只是为LinkedList的其他方法提供服务，或者同一个包中的类提供服务。在LinkedList内部，绝大部分方法的实现都是依靠上面的6种辅助方法实现的，所以，只要把这6个辅助方法自己实现了（或者理解了（最好还是自己实现一次）），LinkedList的基本操作也就掌握了。
   ③如果自己能够实现LinkedList 的功能，对学习算法也很有帮助。毕竟算法是程序的灵魂么！
   最后说一句，如果你自己动手实现一次LinkedList，你一会收获很多！

下面给出源码解析部分

1：首先我们先看看LinkedList的核心，也就是LinkedList中真正用来存储元素的数据结构。

Node 类是LinkedList中的私有内部类，LinkedList中就是通过Node来存储集合中的元素。
E ：节点的值。
Node next：当前节点的后一个节点的引用（可以理解为指向当前节点的后一个节点的指针）
Node prev:当前节点的前一个节点的引用（可以理解为指向当前节点的前一个节点的指针）

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

2：LinkedList集合中有哪些元素：
size：用来记录LinkedList的大小
Node first：用来表示LinkedList的头节点。
Node last：用来表示LinkedList的尾节点。

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    transient int size = 0;

    /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */
    transient Node<E> first;

    /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */
    transient Node<E> last;
 }

3：接下来看看构造器，LinkedList提供了两个构造器，ArrayList比它多提供了一个通过设置初始化容量来初始化类。LinkedList不提供该方法的原因：因为LinkedList底层是通过链表实现的，每当有新元素添加进来的时候，都是通过链接新的节点实现的，也就是说它的容量是随着元素的个数的变化而动态变化的。而ArrayList底层是通过数组来存储新添加的元素的，所以我们可以为ArrayList设置初始容量（实际设置的数组的大小）。
①空构造器：

    public LinkedList() {
    }

传入一个集合（Collection）作为参数初始化LinkedList。

这里有一个非常重要的方法addAll(int index, Collection

// 首先调用一下空的构造器。
//然后调用addAll(c)方法。
  public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
//通过调用addAll(int index, Collection<? extends E> c) 完成集合的添加。
  public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
//重点来了。（还是建议大家自己手动写一次源码实现。） 
//几乎所有的涉及到在指定位置添加或者删除或修改操作都需要判断传进来的参数是否合法。
// checkPositionIndex(index)方法就起这个作用。该方法后面会介绍。 
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);
//先把集合转化为数组，然后为该数组添加一个新的引用（Objext[] a）。
        Object[] a = c.toArray();
//新建一个变量存储数组的长度。
        int numNew = a.length;
//如果待添加的集合为空，直接返回，无需进行后面的步骤。后面都是用来把集合中的元素添加到
//LinkedList中。
        if (numNew == 0)
            return false;
//这里定义了两个节点：（读这里的程序的时候，强烈建议自己画一个图，辅助你理解这个过程）。
//Node<E> succ：指代待添加节点的位置。
//Node<E> pred：指代待添加节点的前一个节点。
//下面的代码是依据新添加的元素的位置分为两个分支：
//①新添加的元素的位置位于LinkedList最后一个元素的后面。
//新添加的元素的位置位于LinkedList中。
//如果index==size;说明此时需要添加LinkedList中的集合中的每一个元素都是在LinkedList
//最后面。所以把succ设置为空，pred指向尾节点。
//否则的话succ指向插入待插入位置的节点。这里用到了node（int index）方法，这个方法
//后面会详细分析，这里只需要知道该方法返回对应索引位置上的Node（节点）。pred指向succ节点的前一个节点。
//上面分析的这几步如果看不懂的话，可以自己画个图，清晰明了^_^。
        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
//接着遍历数组中的每个元素。在每次遍历的时候，都新建一个节点，该节点的值存储数组a中遍历
//的值，该节点的prev用来存储pred节点，next设置为空。接着判断一下该节点的前一个节点是否为
//空，如果为空的话，则把当前节点设置为头节点。否则的话就把当前节点的前一个节点的next值
//设置为当前节点。最后把pred指向当前节点，以便后续新节点的添加。
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
//这里仍然和上面一样，分两种情况对待：
//①当succ==null（也就是新添加的节点位于LinkedList集合的最后一个元素的后面），
//通过遍历上面的a的所有元素，此时pred指向的是LinkedList中的最后一个元素，所以把
//last指向pred指向的节点。
//当不为空的时候，表明在LinkedList集合中添加的元素，需要把pred的next指向succ上，
//succ的prev指向pred。
//最后把集合的大小设置为新的大小。
//modCount（修改的次数）自增。
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    } 

4：接下是一些辅助方法（这些方法大多数是private或者是protected修饰的），LinkedList中大多数通过他们来完成List、Deque中类似的操作。

①：把参数中的元素作为链表的第一个元素。

//因为我们需要把该元素设置为头节点，所以需要新建一个变量把头节点存储起来。
//然后新建一个节点，把next指向f，然后自身设置为头结点。
//再判断一下f是否为空，如果为空的话，说明原来的LinkedList为空，所以同时也需要把新节点设
//置为尾节点。否则就把f的prev设置为newNode。
//size和modCount自增。
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

②：把参数中的元素作为链表的最后一个元素。

//因为我们需要把该元素设置为尾节点，所以需要新建一个变量把尾节点存储起来。
//然后新建一个节点，把last指向l，然后自身设置为尾结点。
//再判断一下l是否为空，如果为空的话，说明原来的LinkedList为空，所以同时也需要把新节点设
//置为头节点。否则就把l的next设置为newNode。
//size和modCount自增。
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

③在非空节点succ之前插入元素e。

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
//首先我们需要新建一个变量指向succ节点的前一个节点，因为我们要在succ前面插入一个节点。
//接着新建一个节点，它的prev设置为我们刚才新建的变量，后置节点设置为succ。
//然后修改succ的prev为新节点。
//接着判断一个succ的前一个节点是否为空，如果为空的话，需要把新节点设置为为头结点。
//如果不为空，则把succ的前一个节点的next设置为新节点。
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

④删除LinkedList中第一个节点。（该节点不为空）（并且返回删除的节点的值）
官方文档的代码中也给出了注释：使用该方法的前提是参数f是头节点，而且f不能为空。
不过，它是私有方法，我们也没有权限使用￣□￣｜｜…

  private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
  //定义一个变量element指向待删除节点的值，接着定义一个变量next指向待删除节点的
  //下一个节点。（因为我们需要设置f节点的下一个节点为头结点，而且需要把f节点的值设置为空）
  //接着把f的值和它的next设置为空，把它的下一个节点设置为头节点。
  //接着判断一个它的下一个节点是否为空，如果为空的话，则需要把last设置为空。否则
  //的话，需要把next的prev设置为空，因为next现在指代头节点。
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

⑤删除LinkedList的最后一个节点。（该节点不为空）（并且返回删除节点对应的值）
和unlinkFirst（）方法思路差不多。

  private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

⑥删除一个节点（该节点不为空）
试想一下，我们删除LinkedList中的一个节点，都需要把该节点的前、后节点重新链接起来，总不能让链表断开吧(⊙o⊙)…。
所以呢，这就需要我们新建几个变量来保存他们的状态。
所以，下面新建了三个变量，第一个变量用来存储当前被删除节点的值，因为我们最后需要把这个返回回去。第二个变量用来存储待删除节点的前一个节点，第三个变量用来存储待删除节点的后一个节点。
接下来判断一下，待删除节点的前一个节点是否为空，如果为空的话，表明待删除的节点是我们的头结点。则需要把待删除节点的后一个节点设置为头结点。如果不为空，就需要把待删除的节点的前、后节点链接起来（你不能删个节点，就把人家LinkedList弄断了吧(⊙o⊙)…），此刻只需要链接一部分，通过pre.next=next；x.prev= null设置（这里也是JDK设计的技巧的部分，一般我们都会直接在这里把链接全部设置上），接着判断一下待删除的节点是否为空，如果为空的话，则表明待删除节点是尾节点，所以需要我们把待删除节点的前一个节点设置为尾节点。如果不为空的，则把next.prev=prev，x.next=null（看到了吧，JDK直接把链接分到了两次判断中分别设置）。最后把待删除节点的值设置为空。切记不要忘了把size和modCount自减，最后返回被删除节点的值（机制的JDK一开始就把要返回的值保存起来了。）

    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

计算指定索引上的节点（返回Node）
LinkedList还对整个做了优化，不是盲目地直接从头进行遍历，而是先比较一下index更靠近链表（LinkedList）的头节点还是尾节点。然后进行遍历，获取相应的节点。

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            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;
        }
    }

到目前大部分的私有方法全部讲完了，接下来的方法大多引用了上面的工具方法。

5：提供给用户使用的删除头结点，并返回删除的值。
直接调用了上面的工具方法unlinkFirst（Node f）

public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

6:删除链表中的最后一个节点，并返回被删除节点的值。
和上面一样调用了unlinkLast（Node last）方法。

public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

7：在LinkedList头部添加一个新的元素、尾部添加一个新元素。
都是调用了私有方法。

public void addFirst(E e) {
        linkFirst(e);
    }
public void addLast(E e) {
        linkLast(e);
    }

判断LinkedList是否包含某一个元素。
底层通过调用indexof()。该方法主要用于计算元素在LinkedList中的位置。
其实indexof（）方法也非常简单：
首先依据obejct是否为空，分为两种情况：
然后通过在每种情况下，从头节点开始遍历LinkedList，判断是否有与object相等的元素，如果有，则返回对应的位置index，如果找不到，则返回-1。

public boolean contains(Object o) {
        return indexOf(o) != -1;
    }
public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

8：计算LinkedList的大小。
直接返回实例域size。

    public int size() {
        return size;
    }

9：添加一个新元素。
直接在最后面添加，调用了linkLast（）方法。

public boolean add(E e) {
        linkLast(e);
        return true;
    }

10：从LinkedList中删除指定元素。（且只删除第一次出现的指定的元素）（如果指定的元素在集合中不存在，则返回false，否则返回true）
该方法也是通过object是否为空分为两种情况去和LinkedList中的每一个元素比较，如果找到了，就删掉，返回true即可。如果找不到，则返回false
这个方法包括前面的方法，一眼就能看懂的就不分析了（显得我很啰嗦(艹皿艹 )）

 public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

12：清空LinkedList中的所有元素
该方法也简单，直接遍历整个LinkedList，然后把每个节点都置空。最后要把头节点和尾节点设置为空，size也设置为空，但是modCount仍然自增

    public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        // more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }

13：获取对应index的节点的值。
通过node（）方法返回其值。（node（）方法依据索引的值返回其对应的节点。）

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

14：设置对应index的节点的值。
首先检查一下索引是否合法，然后通过node（）方法求出旧值，然后设置新值。最后把旧值返回回去。

public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

15：在指定的位置上添加新的元素。
在方法中先判断新添加的元素是否是位于LinkedList的最后，然后是，则直接调用linkLast（）方法添加即可。否则的话，调用linkBefore（）添加即可。

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

16：移除指定位置上的元素
还是调用上面的方法。

    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

17：判断参数index是否是元素的索引
这个方法也是辅助方法，它用来判断index是否在LinkedList索引范围内，所以index

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

18：LinkedList的这个方法用于判断当我们新添加元素的时候，传进来的index是否合法，而且我们新添加的元素可能在LinkedList最后一个元素的后面，所以这里允许index<=size。

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

19：返回越界的信息：
也是一个辅助方法。

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

20：判断参数index是否是元素的索引（如果不是则抛出异常）

private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

21：LinkedList的这个方法用于判断当我们新添加元素的时候，传进来的index是否合法，（调用的是isPositionIndex(index)方法）而且我们新添加的元素可能在LinkedList最后一个元素的后面，所以这里允许index<=size。如果不合法，则抛出异常。

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

22：在LinkedList中查找object在LinkedList中的位置。（从后向前遍历，只返回第一出线的元素的索引，如果没找到，则返回-1）

 public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

后面大部分都是实现双端队列接口的方法。

（很多都太简单了，就不分析了。）

23：返回头结点的值。（即使头结点为空，也直接返回空）

    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

24：返回头节点的值。这次的实现方式和上面的方式不同。（调用该方法：如果头节点为空，则抛出NoSuchElementException。）

  public E element() {
        return getFirst();
    }

25：移除头结点，并返回移除的头结点的值。（如果头结点为空，则返回null）

    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

26：移除头结点的值，并返回移除的头结点的值。如果头结点为空，则抛出NoSuchElementException异常。

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

27：移除元素（移除头节点的元素，如果为空，则抛出异常）

    public E remove() {
        return removeFirst();
    }

28：在链表的尾部添加一个元素

    public boolean offer(E e) {
        return add(e);
    }

29：在链表的头部添加一个新的元素

    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

30：在链表的头部添加一个元素

    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

31：在链表的尾部添加一个元素

    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

32：弹出链表的头结点的元素，如果为空，则返回null

    public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

33：弹出链表尾节点的元素，如果为空，则返回null

    public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

34：取出链表头节点的值，并删除该头节点。如果头结点为空，则返回null

    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

35：取出链表尾节点的值，并删除该尾节点，如果尾节点为空，则返回null。

    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

36：增加一个新的元素：（新添加的元素位于LinkedList的头结点。）

   public void push(E e) {
        addFirst(e);
    }

37：弹出头结点的元素。（删除头结点的值，并返回删除的值）（都是队列中才有的操作。）

    public E pop() {
        return removeFirst();
    }

38：移除第一次出现的元素。（从前向后遍历集合）
底层调用remove（）方法，通过从前向后遍历集合。

    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

39：移除第一次出现的元素。（从后向前遍历集合）

  public boolean removeLastOccurrence(Object o) {
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

40：克隆的辅助方法。
直接调用超类的clone（）方法，然后把得到的Object对象转换为LinkedList类型。
Object的clone（）方法是本地方法（通过native修饰）

    @SuppressWarnings("unchecked")
    private LinkedList<E> superClone() {
        try {
            return (LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

41：克隆方法：
首先获取从辅助方法返回的LinkedList对象，接着把该对象的所有域都设置为初始值。
然后把LinkedList中所有的内容复制到返回的对象中。

    public Object clone() {
        LinkedList<E> clone = superClone();

        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;

        // Initialize clone with our elements
        for (Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);

        return clone;
    }

42：转化为数组：（没有参数）
通过遍历LinkedList中的每个节点，把值添加到数组中。

    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

43：转化为数组：（参数是数组）

    /** * 泛型方法 * 在方法内部，如果a的长度小于集合的大小的话， * 通过反射创建一个和集合同样大小的数组， * 接着把集合中的所有元素添加到数组中。 * 如果数组的元素的个数大于集合中元素的个数，则把a[size]设置 * 为空。 * 我估计代码设计者这样设计代码的目的是为了能够通过返回值观察到 * LinkedList集合中原来的元素有哪些。通过null把集合中的元素凸显出来。 * ArrayList中也有同样的考虑和设计。 * * @param a * @param <T> * @return */
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;

        if (a.length > size)
            a[size] = null;

        return a;
    }

44：将LinkedList写入到流中。（也就是把LinkedList状态保存到流中）（序列化）

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out size
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (Node<E> x = first; x != null; x = x.next)
            s.writeObject(x.item);
    }

45：从流中把LinkedList读取出来（读取流，拼装成LinkedList）（反序列化）

    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read in size
        int size = s.readInt();

        // Read in all elements in the proper order.
        for (int i = 0; i < size; i++)
            linkLast((E)s.readObject());
    }

46：LinkedList提供了两种迭代器，一种是返回Iterator，另一种返回ListIterator。

①返回ListIterator迭代器：

    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

②返回Iterator迭代器：

    public Iterator<E> descendingIterator() {
        return new DescendingIterator();
    }

LinkedList的迭代器也是提供了两种，一种是指提供向后遍历的Iterator，另一种是List的专有迭代器ListIterator。