前言

　　前文分析了ArrayList的源码，这一篇分享的是LinkedList。我们都知道它的底层是由链表实现的，所以我们要明白什么是链表？

一、LinkedList简介

1.1、LinkedList概述

LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于双向链表实现的。

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。

1.2、LinkedList的数据结构

　　1）基础知识补充

　　　　1.1）单向链表：

　　　　　　element：用来存放元素

　　　　　　next：用来指向下一个节点元素

　　　　　　通过每个结点的指针指向下一个结点从而链接起来的结构，最后一个节点的next指向null。

　　　　1.2）单向循环链表

　　　　　　element、next 跟前面一样

　　　　　　在单向链表的最后一个节点的next会指向头节点，而不是指向null，这样存成一个环。

　　　　1.3）双向链表

　　　　　　element：存放元素

　　　　　　pre：用来指向前一个元素

　　　　　　next：指向后一个元素

　　　　　　双向链表是包含两个指针的，pre指向前一个节点，next指向后一个节点，但是第一个节点head的pre指向null，最后一个节点的tail指向null。

　　　　1.4）双向循环链表

　　　　　　element、pre、next 跟前面的一样

　　　　　　第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成一个“环”。

　　2）LinkedList的数据结构

如上图所示，LinkedList底层使用的双向链表结构，有一个头结点和一个尾结点，双向链表意味着我们可以从头开始正向遍历，或者是从尾开始逆向遍历，并且可以针对头部和尾部进行相应的操作。

1.3、LinkedList的特性

　　在我们平常中我们只知道一些常识性的特点：

　　　　1）是通过链表实现的，

　　　　2）如果在频繁的插入，或者删除数据时，就用linkedList性能会更好。

　　那我们通过API去查看它的一些特性

　　　　1）Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

　　　　　　这告诉我们，linkedList是一个双向链表，并且实现了List和Deque接口中所有的列表操作，并且能存储任何元素，包括null，

　　　　　　这里我们可以知道linkedList除了可以当链表使用，还可以当作队列使用，并能进行相应的操作。

　　　　2）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.

　　　　　　这个告诉我们，linkedList在执行任何操作的时候，都必须先遍历此列表来靠近通过index查找我们所需要的的值。通俗点讲，这就告诉了我们这个是顺序存取，

　　　　　　每次操作必须先按开始到结束的顺序遍历，随机存取，就是arrayList，能够通过index。随便访问其中的任意位置的数据，这就是随机列表的意思。

　　　　3）api中接下来讲的一大堆，就是说明linkedList是一个非线程安全的(异步)，其中在操作Interator时，如果改变列表结构(add\delete等)，会发生fail-fast。

　　通过API再次总结一下LinkedList的特性：　　

　　　　1）异步，也就是非线程安全

　　　　2）双向链表。由于实现了list和Deque接口，能够当作队列来使用。

　　　　　　链表：查询效率不高，但是插入和删除这种操作性能好。

　　　　3）是顺序存取结构（注意和随机存取结构两个概念搞清楚）

二、LinkedList源码分析

2.1、LinkedList的继承结构以及层次关系

分析：

　　　　我们可以看到，linkedList在最底层，说明他的功能最为强大，并且细心的还会发现，arrayList只有四层，这里多了一层AbstractSequentialList的抽象类，为什么呢？

　　　　通过API我们会发现：

　　　　　　1）减少实现顺序存取（例如LinkedList）这种类的工作，通俗的讲就是方便，抽象出类似LinkedList这种类的一些共同的方法

　　　　　　2）既然有了上面这句话，那么以后如果自己想实现顺序存取这种特性的类(就是链表形式)，那么就继承这个AbstractSequentialList抽象类，

　　　　　　　　如果想像数组那样的随机存取的类，那么就去实现AbstracList抽象类。

　　　　　　3）这样的分层，就很符合我们抽象的概念，越在高处的类，就越抽象，往在底层的类，就越有自己独特的个性。自己要慢慢领会这种思想。

　　　　　　4）LinkedList的类继承结构很有意思，我们着重要看是Deque接口，Deque接口表示是一个双端队列，

　　　　　　　　那么也意味着LinkedList是双端队列的一种实现，所以，基于双端队列的操作在LinkedList中全部有效。　　

public abstract class AbstractSequentialList<E>
extends AbstractList<E>
//这里第一段就解释了这个类的作用，这个类为实现list接口提供了一些重要的方法，
//尽最大努力去减少实现这个“顺序存取”的特性的数据存储(例如链表)的什么鬼，对于
//随机存取数据(例如数组)的类应该优先使用AbstractList
//从上面就可以大概知道，AbstractSwquentialList这个类是为了减少LinkedList这种顺//序存取的类的代码复杂度而抽象的一个类，
This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "sequential access" data store (such as a linked list). For random access data (such as an array), AbstractList should be used in preference to this class.

//这一段大概讲的就是这个AbstractSequentialList这个类和AbstractList这个类是完全//相反的。比如get、add这个方法的实现
This class is the opposite of the AbstractList class in the sense that it implements the "random access" methods (get(int index), set(int index, E element), add(int index, E element) and remove(int index)) on top of the list's list iterator, instead of the other way around.

//这里就是讲一些我们自己要继承该类，该做些什么事情，一些规范。
To implement a list the programmer needs only to extend this class and provide implementations for the listIterator and size methods. For an unmodifiable list, the programmer need only implement the list iterator's hasNext, next, hasPrevious, previous and index methods.

For a modifiable list the programmer should additionally implement the list iterator's set method. For a variable-size list the programmer should additionally implement the list iterator's remove and add methods.

The programmer should generally provide a void (no argument) and collection constructor, as per the recommendation in the Collection interface specification.

AbstractSequentialList

实现接口分析：

　　　　　　1）List接口：列表，add、set、等一些对列表进行操作的方法

　　　　　　2）Deque接口：有队列的各种特性，

　　　　　　3）Cloneable接口：能够复制，使用那个copy方法。

　　　　　　4）Serializable接口：能够序列化。

　　　　　　5）应该注意到没有RandomAccess：那么就推荐使用iterator，在其中就有一个foreach，增强的for循环，其中原理也就是iterator，我们在使用的时候，使用foreach或者iterator都可以。

2.2、类的属性

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 实际元素个数
    transient int size = 0;
    // 头结点
    transient Node<E> first;
    // 尾结点
    transient Node<E> last;
}

　　LinkedList的属性非常简单，一个头结点、一个尾结点、一个表示链表中实际元素个数的变量。注意，头结点、尾结点都有transient关键字修饰，这也意味着在序列化时该域是不会序列化的。

2.3、LinkedList的构造方法

　　两个构造方法(两个构造方法都是规范规定需要写的）

　　1）空参构造函数

/**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

　　2）有参构造函数

/**
     * 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
     */
   //将集合c中的各个元素构建成LinkedList链表。
    public LinkedList(Collection<? extends E> c) {

     // 调用无参构造函数
        this();
        // 添加集合中所有的元素
        addAll(c);
}

//根据前面介绍双向链表就知道这个代表什么了，linkedList的奥秘就在这里。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;
        }
    }