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）是通过链表实现的，
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在最底层，说明他的功能最为强大，并且细心的还会发现，arrayList只有四层，这里多了一层AbstractSequentialList的抽象类，为什么呢？
通过API我们会发现：
1）减少实现顺序存取（例如LinkedList）这种类的工作，通俗的讲就是方便，抽象出类似LinkedList这种类的一些共同的方法
2）既然有了上面这句话，那么以后如果自己想实现顺序存取这种特性的类(就是链表形式)，那么就继承这个AbstractSequentialList抽象类，
如果想像数组那样的随机存取的类，那么就去实现AbstracList抽象类。
3）这样的分层，就很符合我们抽象的概念，越在高处的类，就越抽象，往在底层的类，就越有自己独特的个性。自己要慢慢领会这种思想。
4）LinkedList的类继承结构很有意思，我们着重要看是Deque接口，Deque接口表示是一个双端队列，
那么也意味着LinkedList是双端队列的一种实现，所以，基于双端队列的操作在LinkedList中全部有效。
实现接口分析：
1）List接口：列表，add、set、等一些对列表进行操作的方法
2）Deque接口：有队列的各种特性，
3）Cloneable接口：能够复制，使用那个copy方法。
4）Serializable接口：能够序列化。
5）应该注意到没有RandomAccess：那么就推荐使用iterator，在其中就有一个foreach，增强的for循环，其中原理也就是iterator，我们在使用的时候，使用foreach或者iterator都可以。
LinkedList的属性非常简单，一个头结点、一个尾结点、一个表示链表中实际元素个数的变量。注意，头结点、尾结点都有transient关键字修饰，这也意味着在序列化时该域是不会序列化的。
两个构造方法(两个构造方法都是规范规定需要写的）
1）空参构造函数
2）有参构造函数
说明：会调用无参构造函数，并且会把集合中所有的元素添加到LinkedList中。
说明：内部类Node就是实际的结点，用于存放实际元素的地方。
1）add(E)
说明：add函数用于向LinkedList中添加一个元素，并且添加到链表尾部。具体添加到尾部的逻辑是由linkLast函数完成的。
分析：
LinkLast(XXXXX)
说明：对于添加一个元素至链表中会调用add方法 -> linkLast方法。
举例一：
首先调用无参构造函数，之后添加元素5，之后再添加元素6。具体的示意图如下：
上图的表明了在执行每一条语句后，链表对应的状态。
addAll有两个重载函数，addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型，我们平时习惯调用的addAll(Collection<? extends E>)型会转化为addAll(int, Collection<? extends E>)型。
1）addAll(c);
2）addAll(size，c)：这个方法，能包含三种情况下的添加，我们这里分析的只是构造方法，空链表的情况(情况一)看的时候只需要按照不同的情况分析下去就行了。
说明：参数中的index表示在索引下标为index的结点（实际上是第index + 1个结点）的前面插入。
在addAll函数中，addAll函数中还会调用到node函数，get函数也会调用到node函数，此函数是根据索引下标找到该结点并返回，具体代码如下：
说明：在根据索引查找结点时，会有一个小优化，结点在前半段则从头开始遍历，在后半段则从尾开始遍历，这样就保证了只需要遍历最多一半结点就可以找到指定索引的结点。
举例说明调用addAll函数后的链表状态：
上述代码内部的链表结构如下：
addAll()中的一个问题：
在addAll函数中，传入一个集合参数和插入位置，然后将集合转化为数组，然后再遍历数组，挨个添加数组的元素，但是问题来了，为什么要先转化为数组再进行遍历，而不是直接遍历集合呢？
从效果上两者是完全等价的，都可以达到遍历的效果。关于为什么要转化为数组的问题，我的思考如下：1. 如果直接遍历集合的话，那么在遍历过程中需要插入元素，在堆上分配内存空间，修改指针域，
这个过程中就会一直占用着这个集合，考虑正确同步的话，其他线程只能一直等待。2. 如果转化为数组，只需要遍历集合，而遍历集合过程中不需要额外的操作，
unlink(xxxx)
get(index)查询元素的方法
node(index)
在LinkedList中除了有一个Node的内部类外，应该还能看到另外两个内部类，那就是ListItr，还有一个是DescendingIterator。
看一下他的继承结构，发现只继承了一个ListIterator，到ListIterator中一看：
看到方法名之后，就发现不止有向后迭代的方法，还有向前迭代的方法，所以我们就知道了这个ListItr这个内部类干嘛用的了，就是能让linkedList不光能像后迭代，也能向前迭代。
看一下ListItr中的方法，可以发现，在迭代的过程中，还能移除、修改、添加值得操作。
1）linkedList本质上是一个双向链表，通过一个Node内部类实现的这种链表结构。2）能存储null值3）跟arrayList相比较，就真正的知道了，LinkedList在删除和增加等操作上性能好，而ArrayList在查询的性能上好4）从源码中看，它不存在容量不足的情况5）linkedList不光能够向前迭代，还能像后迭代，并且在迭代的过程中，可以修改值、添加值、还能移除值。6）linkedList不光能当链表，还能当队列使用，这个就是因为实现了Deque接口。