1. 概述
相较于 ArrayList，LinkedList 在平时应用少一些。
LinkedList 外部是一个双向链表，并且实现了 List 接口和 Deque 接口，因而它也具备 List 的操作以及双端队列和栈的性质。双向链表的构造如下：
前文剖析了 Queue 和 Deque 接口，正是因为 LinkedList 实现了 Deque 接口。LinkedList 的继承构造如下：
2. 代码剖析
2.1 结点类 Node
查看 LinkedList 的源码可发现它外部有个嵌套类 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 是双向链表的实现，而该 Node 类则是链表的结点。
此外，LinkedList 还有几个成员变量如下：
// list 的长度transient int size = 0;// 链表头结点transient Node<E> first;// 链表尾结点transient Node<E> last;2.2 结构器
LinkedList 有两个结构器，如下：
public LinkedList() {}public LinkedList(Collection<? extends E> c) { this(); addAll(c);}PS: 因为链表的容量能够始终减少，因而没有指定容量的结构器。
其中第一个为无参结构器；第二个为应用指定的汇合结构，并调用 addAll()，持续跟进该办法，代码如下：
public boolean addAll(Collection<? extends E> c) { return addAll(size, c);}public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); // 将汇合元素转为数组 Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; // 获取以后链表的前驱和后继结点 Node<E> pred, succ; if (index == size) { // 尾结点的前驱和后继结点 succ = null; pred = last; } else { // 若非尾结点，获取指定地位的结点 succ = node(index); pred = succ.prev; } // 循环将数组中的元素插入到链表 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } // 若插入到开端，则数组中的最初一个元素就是尾结点 if (succ == null) { last = pred; } else { // 若插入到指定地位，将数组中最初一个元素与下一个地位关联起来 pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true;}其中 node(index) 办法为获取指定地位的结点，代码如下：
Node<E> node(int index) { // assert isElementIndex(index); // 若下标在前一半，则从前往后遍历；否则从后往前遍历 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }}该办法通过遍历链表获取指定的元素。
值得注意的是，该办法并非间接从头到尾遍历整个链表，而是先判断下标的地位，若在前一半则从前往后遍历；否则就从后往前遍历。这样能缩小遍历结点的个数。
PS: 前文「数据结构与算法笔记（一）」对链表进行过剖析，因为其内存空间非间断，因而不反对随机拜访（下标拜访）。所以，查问某个结点是通过遍历整个链表来实现的。
与此同时，get(index) 办法外部也是这样实现的：
public E get(int index) { checkElementIndex(index); return node(index).item;}2.3 罕用办法
之前剖析 Queue 和 Deque 的时候提到：Queue 中的办法在 Deque 中都有对应的。上面简略剖析 LinkedList 中一些罕用的办法。
新增结点办法：add(), addLast(), offerLast()
public boolean offerLast(E e) { addLast(e); return true;}public void addLast(E e) { linkLast(e);}public boolean add(E e) { linkLast(e); return true;}能够看到他们都是调用了同一个办法 linkLast(e) 实现的，如下：
void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; // 若链表为空，则新结点为头结点 if (l == null) first = newNode; // 若链表不为空，将新结点插入到链表尾部 else l.next = newNode; size++; modCount++;}该操作就是将指定的结点增加到链表开端。
删除结点办法：poll(), pollFirst(), removeFirst()
public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f);}public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f);} public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f);}能够看到这三个办法都是调用 unlinkFirst() 办法实现的，其代码如下：
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; if (next == null) last = null; else next.prev = null; size--; modCount++; return element;}该办法的操作就是从链表头部移除一个结点。
向单链表插入和删除结点的操作示意图如下（双链表比这里多了前驱结点）：
栈的入栈（push）和出栈（pop）操作：
public void push(E e) { addFirst(e);}public E pop() { return removeFirst();}能够看到这两个办法间接调用了双端队列的实现办法。即，该栈是一个「链式栈」。
3. 线程安全性
线程平安的概念不再赘述。剖析以下场景：
若有线程 T1 对 LinkedList 进行遍历，同时线程 T2 对其进行结构性批改。
对 LinkedList 的遍历是通过 listIterator(index) 办法实现的，如下：
public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index);}private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; // 初始化时二者是相等的 private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public void remove() { checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; } // ... // 是否有其余线程对以后对象进行构造批改 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }}该类的 next(), add(e) 等办法在执行时会检测 modCount 与创立时是否统一（checkForComodification() 办法），从而判断是否有其余线程对该对象进行了构造批改，若有则抛出 ConcurrentModificationException 异样。
因而，LinkedList 是线程不平安的。
4. 小结
- LinkedList 外部是「双向链表」，同时实现了 List 接口和 Deque 接口，因而也具备 List、双端队列和栈的性质；
- 线程不平安。
相干浏览：JDK源码-Queue, Deque