LinkedList

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

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

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

Node

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;
       }
   }

属性

size：用来记录LinkedList的大小
Node first：用来表示LinkedList的头节点。
Node last：用来表示LinkedList的尾节点

    transient int size;
    transient LinkedList.Node<E> first;
    transient LinkedList.Node<E> last;

构造器

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

public LinkedList() {
   }

addall

// 首先调用一下空的构造器。
//然后调用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;
    }

增加

函数

源码

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

//因为我们需要把该元素设置为头节点，所以需要新建一个变量把头节点存储起来。
//然后新建一个节点，把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++;
    }

指定值之前插入元素

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++;
    }

删除

函数

源码

删除头结点

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;
    }

删除末尾节点

rivate 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;
    }

变量用来存储当前被删除节点的值，因为我们最后需要把这个返回回去。第二个变量用来存储待删除节点的前一个节点，第三个变量用来存储待删除节点的后一个节点。
接下来判断一下，待删除节点的前一个节点是否为空，如果为空的话，表明待删除的节点是我们的头结点。则需要把待删除节点的后一个节点设置为头结点。如果不为空，就需要把待删除的节点的前、后节点链接起来，此刻只需要链接一部分，通过pre.next=next；x.prev= null设置（这里也是JDK设计的技巧的部分，一般我们都会直接在这里把链接全部设置上），接着判断一下待删除的节点是否为空，如果为空的话，则表明待删除节点是尾节点，所以需要我们把待删除节点的前一个节点设置为尾节点。如果不为空的，则把next.prev=prev，x.next=null。最后把待删除节点的值设置为空。把size和modCount自减，最后返回被删除节点的值

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;
    }

查找

方法

源码

先比较一下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;
        }
    }