简介
　　LinkedList 是一个常用的集合类，用于顺序存储元素。 LinkedList 经常和 ArrayList 一起被提及。大部分人应该都知道 ArrayList 内部采用数组保存元素，适合用于随机访问比较多的场景，而随机插入、删除等操作因为要移动元素而比较慢。 LinkedList 内部采用链表的形式存储元素，随机访问比较慢，但是插入、删除元素比较快，一般认为时间复杂都是 O(1) (需要查找元素时不是了，下面会说明)。本文分析 LinkedList 的具体实现。
　　继承关系
　　public class LinkedList<E>
　　extends AbstractSequentialList<E>
　　implements List<E>， Deque<E>， Cloneable， java.io.Serializable
　　LinkedList 继承了一个抽象类 AbstractSequentialList ，这个类是用调用 ListIterator 实现了元素的增删查改，比如 add 方法：
　　public void add(int index， E element) {
　　try {
　　listIterator(index).add(element);
　　} catch (NoSuchElementException exc) {
　　throw new IndexOutOfBoundsException("Index: "+index);
　　}
　　}
　　不过这些方法在 LinkedList 中被复写了。
　　LinkedList 实现了 List 、 Deque 、 Cloneable 以及 Serializable 接口。其中 Deque 是双端队列接口，所以 LinkedList 可以当作是栈、队列或者双端队队列。
　　内部变量
　　transient int size = 0;
　　transient Node<E> first;
　　transient Node<E> last;
　　总共三个内部变量， size 是元素个数， first 是指向第一个元素的指针， last 则指向后一个。元素在内部被封装成 Node 对象，这是一个内部类，看一下它的代码：
　　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;
　　}
　　}
　　可以看到这是一个双向链表的结构，每个节点保存它的前驱节点和后继节点。
　　私有方法
　　LinkedList 内部有几个关键的私有方法，它们实现了链表的插入、删除等操作。比如在表头插入：
　　private void linkFirst(E e) {
　　final Node<E> f = first;    //先保存当前头节点
　　//创建一个新节点，节点值为e，前驱节点为空，后继节点为当前头节点
　　final Node<E> newNode = new Node<>(null， e， f);
　　first = newNode;    //让first指向新节点
　　if (f == null)    //如果链表原来为空，把last指向这个的节点
　　last = newNode;
　　else    ·        //否则原来的头节点的前驱指向新的头节点
　　f.prev = newNode;
　　size++;
　　modCount++;
　　}
　　其实是双向链表的插入操作，调整指针的指向，时间复杂度为 O(1) ，学过数据结构的应该很容易看懂。其它还有几个类似的方法：
　　//尾部插入
　　void linkLast(E e) {
　　final Node<E> l = last;
　　final Node<E> newNode = new Node<>(l， e， null);
　　last = newNode;
　　if (l == null)    //如果链表原来为空，让first指向这个的节点
　　first = newNode;
　　else
　　l.next = newNode;
　　size++;
　　modCount++;
　　}
　　//中间插入
　　void linkBefore(E e， Node<E> succ) {
　　// assert succ != null;
　　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;
　　final E element = f.item;
　　final Node<E> next = f.next; //先保存下一个节点
　　f.item = null;   
　　f.next = null; // help GC
　　first = next;    //让first指向下一个节点
　　if (next == null)    //如果下一个节点为空，说明链表原来只有一个节点，现在成空链表了，要把last指向null
　　last = null;
　　else        //否则下一个节点的前驱节点要置为null
　　next.prev = null;
　　size--;
　　modCount++;
　　return element;
　　}
　　//删除尾节点
　　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;    //last指向前一个节点
　　if (prev == null)    //与头节点删除一样，判断是否为空
　　first = null;
　　else
　　prev.next = null;
　　size--;
　　modCount++;
　　return element;
　　}
　　//从链表中间删除节点
　　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要指向下一个节点
　　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;
　　}
　　公开方法
　　公开的方法几乎都是调用上面几个方法实现的，例如 add 方法：
　　public boolean add(E e) {
　　linkLast(e);
　　return true;
　　}
　　public boolean add(E e) {
　　linkLast(e);
　　return true;
　　}
　　public void add(int index， E element) {
　　checkPositionIndex(index);
　　if (index == size)
　　linkLast(element);
　　else
　　linkBefore(element， node(index));
　　}