概述
相较于 ArrayList，LinkedList 在平时使用少一些。
LinkedList 内部是一个双向链表，并且实现了 List 接口和 Deque 接口，因此它也具有 List 的操作以及双端队列和栈的性质。双向链表的结构如下：
前文分析了 Queue 和 Deque 接口，正是因为 LinkedList 实现了 Deque 接口。LinkedList 的继承结构如下：
结点类 Node
查看 LinkedList 的源码可发现它内部有个嵌套类 Node，代码如下：
LinkedList 是双向链表的实现，而该 Node 类则是链表的结点。
此外，LinkedList 还有几个成员变量如下：
构造器
LinkedList 有两个构造器，如下：
PS: 由于链表的容量可以一直增加，因此没有指定容量的构造器。
其中第一个为无参构造器；第二个为使用指定的集合构造，并调用 addAll()，继续跟进该方法，代码如下：
其中 node(index) 方法为获取指定位置的结点，代码如下：
该方法通过遍历链表获取指定的元素。
值得注意的是，该方法并非直接从头到尾遍历整个链表，而是先判断下标的位置，若在前一半则从前往后遍历；否则就从后往前遍历。这样能减少遍历结点的个数。
PS: 前文「数据结构与算法笔记（一）」对链表进行过分析，由于其内存空间非连续，因此不支持随机访问（下标访问）。所以，查询某个结点是通过遍历整个链表来实现的。
与此同时，get(index) 方法内部也是这样实现的：
常用方法
之前分析 Queue 和 Deque 的时候提到：Queue 中的方法在 Deque 中都有对应的。下面简单分析 LinkedList 中一些常用的方法。
新增结点方法：add(), addLast(), offerLast()
可以看到他们都是调用了同一个方法 linkLast(e) 实现的，如下：
该操作就是将指定的结点添加到链表末尾。
删除结点方法：poll(), pollFirst(), removeFirst()
可以看到这三个方法都是调用 unlinkFirst() 方法实现的，其代码如下：
该方法的操作就是从链表头部移除一个结点。
向单链表插入和删除结点的操作示意图如下（双链表比这里多了前驱结点）：
栈的入栈（push）和出栈（pop）操作：
可以看到这两个方法直接调用了双端队列的实现方法。即，该栈是一个「链式栈」。
线程安全性
线程安全的概念不再赘述。分析以下场景：
若有线程 T1 对 LinkedList 进行遍历，同时线程 T2 对其进行结构性修改。
对 LinkedList 的遍历是通过 listIterator(index) 方法实现的，如下：
该类的 next(), add(e) 等方法在执行时会检测 modCount 与创建时是否一致（checkForComodification() 方法），从而判断是否有其他线程对该对象进行了结构修改，若有则抛出 ConcurrentModificationException 异常。
因此，LinkedList 是线程不安全的。
小结
1. LinkedList 内部是「双向链表」，同时实现了 List 接口和 Deque 接口，因此也具备 List、双端队列和栈的性质；
2. 线程不安全。
Stay hungry, stay foolish.