LinkedList是另外一种常见的list实现类，底层基于链表实现，不仅实现了List接口，还是实现了Deque接口，所以说LinkedList也是一种队列。LinkedList是双向链表，它的插入删除效率较高，但是查询效率较低（虽然有一定的优化）。first、last表示列表的首尾节点，容量大小用size表示。下面就具体讲讲LinkedList的源码。
1.Node节点信息
Node的构造方法已经使node节点插入了链表，但此时整个链表还不是双向链表。还需要将node前驱的后继(node.prev.next=node)、后继的前驱(node.next.prev=node)指向node，如此，整个链表构成了双向链表。
2.构造函数
LinkedList有两个构造函数。传入Collection对象的构造函数调用了addAll(size, c)。
addAll(index, c)首先会检查index和c，检查通过后用succ保存后继节点，然后再pred、succ之间插入c的元素并且不停的跟新pred节点，如果pred为空，表示是从首节点插入，所以需要让first指向newNode；否则使pred的后继指向newNode。所有元素插入到队列后，如果succ为空，则last指向pred节点；否则关联pred与succ，即使succ的前驱指向pred，succ的后继执行pred。最后修改size和modCount。
3.重要方法
① linkFirst方法。此方法使构造一个新节点并使first指向新节点。先把first备份，在利用构造函数构造新的首节点。如果原来first为空，表示链表为空，则把last指向newNode；否则是原首节点的前驱执行newNode；最后修改size和monCount。
② linkLast方法。类似linkFirst方法，此方法构造一个新节点，并使last指向新节点。先用l备份last，在创建一个新的节点，并使last指向新节点。如果last为空，意味着原链表为空，需要把first指向新节点；否则使l的后继指向新节点。
③ linkBefore方法。此方法在succ节点之前插入一个新节点。这里有一个条件，那就是succ不能为空。先利用pred记录原succ的前驱。在创建一个新节点。succ的前驱指向新节点，再根据pred是否为空判断到底把first指向新节点还是把pred的后继指向新节点。
④ unlinkFirst方法。此方法删除首节点f。先用next保存f的后继，在使f的引用指向空（f是首节点所以不用置空f的前驱），使next指向first。如果next为空，则链表现在没有元素，所有last也为空，否则把next.prev也置空，使jvm回收原first的资源。
⑤ unlinkLast方法。删除非空尾节点l。类似unlinkFirst方法。先保存前驱，在置空l，接着把前驱赋值给last。最后根据前驱是否为空判断链表是否有元素，根据结果把first赋空或者把现在last的后继赋空。
⑥ unlink方法。此方法删除节点x。主要使x的前驱和后继直接关联上即可。这里要说明的如果前驱为空，没必要再次使x.prev = null。最后还要修改size和modCount。详细过程请看代码。
⑦ node方法。此方法得到指定index序号的元素节点。如果index小于0.5*size，从前往后遍历寻找序号为index的节点；否则，从后向前遍历寻找node。
⑧contains与indexOf方法。如同ArrayList，contains也是利用indexOf判断元素是否存在。indexOf方法返回元素第一次出现的位置，如果不存在则返回-1.
LinkedList剩下的方法（包括queue接口的方法）主要就是利用size、first、last以及上诉提到的几个方法实现。很简洁。
clear方法清空元素。
