05-LinkedList 源码解析（集合）
注：源码系列文章主要是对某付费专栏的总结记录。如有侵权，请联系删除。
LinkedList 适用于集合元素先入先出和先入后出的场景，在队列源码中被频繁使用，面试也经常被问到。
1 整体架构
LinkedList 底层数据结构是一个双向链表，整体结构如下图所示：
LinkedList 底层数据结构
上图代表了一个双向链表结构，链表中的每个节点都可以向前或向后追溯，几个概念如下：
- 链表每个节点叫做 Node，Node 有 prev 代表前一个节点，next 代表后一个节点；
- first 是双向链表的头节点，它的前一个节点是 null；
- last 是双向链表的尾节点，它的后一个节点是 null；
- 当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null；
- 因为是个双向链表，只要机器内存足够强大，是没有大小限制的。
链表中的元素叫做 Node，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;
}
}
2 源码解析
2.1 新增
追加节点时，我们可以选择追加到链表头部，还是追加到链表尾部，add 方法默认是从尾部开始追加，addFirst 方法是从头部开始追加，我们分别来看下两种不同的追加方式：
2.1.1 从尾部增加（add/addLast）
/**
* Links e as last element.
*/
void linkLast(E e) {
// 将尾节点暂存
final Node<E> l = last;
// 初始化新的节点。l: 新节点的前一个节点。e: 当前新增节点值。null: 当前新增节点的下一个节点是 null
final Node<E> newNode = new Node<>(l, e, null);
// 为尾节点赋值为当前新增的节点
last = newNode;
// 如果尾节点为空(即链表为空)
if (l == null)
// 则为头节点赋值为当前新增节点也就是尾节点
first = newNode;
// 否则把原尾节点 l 的下一个节点指向当前新增节点
else
l.next = newNode;
// 大小和版本增加
size++;
modCount++;
}
2.1.2 从头部追加（addFirst）
/**
* Links e as first element.
*/
private void linkFirst(E e) {
// 将头节点暂存
final Node<E> f = first;
// 初始化新的节点
final Node<E> newNode = new Node<>(null, e, f);
// 为头节点赋值为当前新增节点
first = newNode;
// 如果原头节点 f 为空(即链表为空)
if (f == null)
// 则为尾节点赋值为当前新增节点也就是头节点
last = newNode;
// 否则把原头节点的前一个节点指向当前新增节点
else
f.prev = newNode;
// 大小和版本增加
size++;
modCount++;
}
头部追加节点和尾部追加节点非常类似，只是前者是移动头部节点的 prev 指向，后者是移动尾部节点的 next 指向。
2.2 节点删除
节点删除和节点追加类似，我们可以选择从头部删除，也可以选择从尾部删除，删除操作会把节点的值，前后指向节点都置为 null，帮助 GC 进行回收。
2.2.1 从头部删除
// 从头部删除节点 f 是链表头部
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 拿出头节点的值
final E element = f.item;
// 拿出头节点的下一个节点
final Node<E> next = f.next;
// 赋值头节点的值和头节点的下一个节点为 null，帮助 GC 回收
f.item = null;
f.next = null; // help GC
// 原头节点的下一个节点 next 为新的头节点
first = next;
// 如果 next 为 null，表明链表为空
if (next == null)
last = null;
else
// 链表不为空，设置新的头节点的前一个节点为 null
next.prev = null;
// 大小和版本更改
size--;
modCount++;
// 返回被删除节点的值
return element;
}
2.2.2 从尾部删除
// 从尾部删除节点 l 是链表尾部
/**
* Unlinks non-null last node l.
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
// 拿出尾节点的值
final E element = l.item;
// 拿出尾节点的前一个节点
final Node<E> prev = l.prev;
// 赋值尾节点的值和尾节点的前一个节点为 null，帮助 GC 回收
l.item = null;
l.prev = null; // help GC
// 原尾节点的前一个节点 prev 为新的尾节点
last = prev;
// 如果 prev 为 null，表明链表为空
if (prev == null)
first = null;
else
// 链表为不空，设置新的尾节点的下一个节点为 null
prev.next = null;
// 大小和版本更改
size--;
modCount++;
// 返回被删除节点的值
return element;
}
从源码中我们可以了解到，链表结构的节点新增、删除都非常简单，仅仅把前后节点的指向修改而已，所以 LinkedList 新增和删除速度很快。
2.3 节点查询
链表查询某一个节点是比较慢的，需要挨个循环查找才行，源码如下：
// 根据链表索引位置查询节点
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// 如果 index 处于队列的前半部分，则从头开始查找，size >> 1 是 size 除以 2 的意思
if (index < (size >> 1)) {
Node<E> x = first;
// for 循环到 index 的前一个 node 停止
for (int i = 0; i < index; i++)
x = x.next;
return x;
}
// 如果 index 处于队列的后半部分，则从尾部开始查找
else {
Node<E> x = last;
// for 循环到 index 的后一个 node 停止
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
从源码中我们发现，LinkedList 并没有采用从头循环到尾的做法，而是采取了简单二分法，首先看看 index 是在链表的前半部分，还是后半部分。如果是前半部分，就从头开始寻找，反之亦然。通过这种方式，使循环的次数至少降低了一半，提高了查找的性能，这种思想值得我们借鉴。
2.4 方法对比
LinkedList 实现了 Queue 接口，在新增、删除、查询等方面增加了很多新的方法，这些方法平时特别容易混淆，在链表为空的情况下，返回值也不太一样，如下：
|方法含义|返回异常|返回特殊值|底层实现|
|----|----|----|----|----|
|新增(尾部)|add(e)|offer(e)|底层实现相同|
|删除(头节点)|remove()|poll()|链表为空时，remove 会抛出异常，poll 返回 null|
|查找(头节点)|element()|peek()|链表为空时，element 会抛出异常，peek 返回 null|
PS：Queue 接口注释建议 add 方法操作失败时抛出异常，但 LinkedList 实现的 add 方法一直返回 true。
LinkedList 也实现 Deque 接口，对新增、删除和查找都提供从头开始，还是从尾开始两种方向的方法，比如 remove 方法，Deque 提供了 removeFirst 和 removeLast 两种方向的使用方法，但当链表为空时的表现都和 remove 方法一样，都会抛出异常。
2.5 迭代器
因为 LinkedList 要实现双向的迭代访问，所以我们使用 Iterator 接口肯定不行，因为 Iterator 只支持从头到尾的访问。Java 新增了一个迭代接口，叫做：ListIterator，这个接口提供了向前和向后的迭代方法，如下：
| 迭代顺序 | 相关方法 |
|---|---|
| 从头到尾迭代 |
hasNext, next, nextIndex
|
| 从尾到头迭代 |
hasProvious, previous, previousIndex
|
LinkedList 实现了 ListIterator 接口，源码如图：
// 双向迭代器
private class ListItr implements ListIterator<E> {
// 按照命名，意思为上一次执行 next() 或者 previous() 方法返回的节点
private Node<E> lastReturned;
// 下一个节点
private Node<E> next;
// 下一个节点的位置
private int nextIndex;
// 期望版本号
private int expectedModCount = modCount;
........
}
从头到尾方向的迭代
// 判断有没有下一个元素
public boolean hasNext() {
// 下一个节点的索引小于链表的大小，就有
return nextIndex < size;
}
// 取下一个元素
public E next() {
// 检查版本号有无变化
checkForComodification();
// 再次检查是否还有下一个元素
if (!hasNext())
throw new NoSuchElementException();
// 赋值 lastReturned，首次执行 next() 方法时 赋值为 null
lastReturned = next;
// next 是下一个节点，
next = next.next;
// 索引变化
nextIndex++;
return lastReturned.item;
}
从尾到头方向的迭代
// 判断是否还有上一个节点，我们知道最小索引为 0, 如果 nextIndex 大于0则表示还有上一个元素
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
// 检查版本号有无变化
checkForComodification();
// 再次检查是否还有上一个元素
if (!hasPrevious())
throw new NoSuchElementException();
// 如果 next 为null， 则表示当前是从尾到头的第一次迭代，则赋值 next 为 last，
// 否则赋值 next 为 next 的前一个元素 prev
lastReturned = next = (next == null) ? last : next.prev;
// 索引变化
nextIndex--;
return lastReturned.item;
}
迭代器删除
LinkedList 在删除元素时，也推荐通过迭代器进行删除，源码如下：
public void remove() {
// 检查版本号有无变化
checkForComodification();
// 首先 lastReturned 是本次迭代的值
// 如果 lastReturned 为 null，表示未执行 next() 或 pervious() 方法，那删除直接报错
// 如果 lastReturned 不为 null 则继续执行
if (lastReturned == null)
throw new IllegalStateException();
// 将本次迭代要删除的元素 lastReturned 的下一个元素缓存
Node<E> lastNext = lastReturned.next;
// 删除 lastReturned
unlink(lastReturned);
// 如果是从尾到头的第一次迭代，则 lastReturned = next = last. 参考上面方法 previous()
if (next == lastReturned)
// 这个时候 lastReturned 是尾节点，lastNext 是 null，所以 next 也是 null，这样在执行 previous() 方法判断 next 是否为null 时，发现 next 是null，就会把尾结点 last 赋值给 next
next = lastNext;
else
// 反之索引递减
nextIndex--;
lastReturned = null;
expectedModCount++;
}
总结
LinkedList 适用于要求有顺序、并且会按照顺序进行迭代的场景，主要是依赖于底层的链表结构。
------------------------------------- END -------------------------------------
