LinkedList概览
与ArrayList一样，LinkedList也实现了List接口。ArrayList由于基于数组，在中间删除元素或插入元素的操作中，效率较低。而LinkedList适合于修改较频繁的场景、集合元素先入先出和先入后出的场景（队列）。
ArrayList的底层数据结构，是一个双向链表。如下图所示：
LinkedList中，有以下重要概念：
LinkedList中每个节点，被称为Node。
prev 即 前驱节点。
next 即 后继节点。
first 是 头节点，它的前驱节点恒为null
last 是 尾节点，它的后继节点恒为null
当LinkedList 为空、或只有一个数据时，first=last
LinkedList中每个节点，被称为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;
}
}
类介绍（注释）
类注释大致内容如下：
- 允许 null 值，实现了List接口的所有方法，并实现了
_Deque_接口； - 所有的操作结果，都可以参考
双向链表（Doubly-linked list） - 是非线程安全的，多线程情况下，推荐在创建时，使用：
_Collections.synchronizedList(new LinkedList(...))_； - 增强 for 循环，或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出
**ConcurrentModificationException**异常。
常用方法源码
增加元素
add（从尾部添加）
public boolean add(E e) {
// 直接调用了linkLast方法
linkLast(e);
return true;
}
void linkLast(E e) {
// 备份尾节点
final Node<E> l = last;
// 为插入的元素，创建一个新节点
final Node<E> newNode = new Node<>(l, e, null);
// 将 新节点 赋值给 尾节点
last = newNode;
// 如果操作前，尾节点（备份尾节点）是null，即链表为空，则在链表只有一个元素时，first = last = 该元素
if (l == null)
first = newNode;
else
// 如果操作前，尾节点（备份尾节点）不是null，则将l的next，指向新增的节点。
l.next = newNode;
// 记录长度的增加
size++;
// 记录版本号的变更
modCount++;
}
addFirst（从头部添加）
public void addFirst(E e) {
// 直接调用了linkLast方法
linkFirst(e);
}
private void linkFirst(E e) {
// 备份 头节点
final Node<E> f = first;
// 为插入的元素，创建一个新节点
final Node<E> newNode = new Node<>(null, e, f);
// 将 新节点 赋值给 头节点
first = newNode;
// 如果操作前，头节点（备份头节点）是null，即链表为空，则在链表只有一个元素时，first = last = 该元素
if (f == null)
last = newNode;
else
// 如果操作前，头节点（备份头节点）不是null，则将f的前驱节点，指向新增的节点。
f.prev = newNode;
// 记录长度、版本号的变更
size++;
modCount++;
}
add和addFirst非常类似，只是前者是移动头节点的 prev 指向，后者是移动尾节点的 next 指向。
删除元素
removeFirst（从头部删除）
public E removeFirst() {
// 头结点为null (链表为空时) 抛出错误
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
// 主要逻辑
return unlinkFirst(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 （头结点的前驱节点，本身就为null）
f.item = null;
f.next = null; // help GC
// 将原先的第二个节点，作为头节点
first = next;
// 如果原先的第二个节点为null （即整个链表只有一个节点）
if (next == null)
last = null;
else
// 如果原先的第二个节点不为null （即整个链表有多于一个的节点）
// 需要将现在 头结点的前驱节点，设置为null
next.prev = null;
// 记录长度、版本号的变更
size--;
modCount++;
return element;
}
removeLast（从尾部删除）
public E removeLast() {
// 尾结点为null (链表为空时) 抛出错误
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
// 主要逻辑
return unlinkLast(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 （尾结点的后继节点，本身就为null）
l.item = null;
l.prev = null; // help GC
// 将原先的倒数第二个节点，作为尾节点
last = prev;
// 如果原先的倒数第二个节点为null （即整个链表只有一个节点）
if (prev == null)
first = null;
else
// 如果原先的倒数第二个节点不为null （即整个链表有多于一个的节点）
// 需要将现在 尾结点的后继节点，设置为null
prev.next = null;
// 记录长度、版本号的变更
size--;
modCount++;
return element;
}
从源码中我们可以了解到，链表结构的节点新增、删除都非常简单，仅仅把前驱/后继节点的指向修改下就好了，所以 LinkedList 新增和删除速度很快。并不像ArrayList中，删除、新增时可能还需要移动大量元素。
**
查找元素
链表结构中，查找元素是比较耗时的，一般先想到的，是直接遍历链表，这无可厚非。下面是LinkedList实现根据索引来查找元素的方法：
Node<E> node(int index) {
// assert isElementIndex(index);
// 如果索引小于 size的一半 （size >> 1 等同 size/2 ）
if (index < (size >> 1)) {
Node<E> x = first;
// 查找 从头开始，到index-1 个Node
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
// 查找 从尾开始，到index+1 个Node
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
从源码中我们可以发现，LinkedList 并没有采用从头循环到尾的做法，而是采取了简单二分法，首先看看 index 是在链表的前半部分，还是后半部分。如果是前半部分，就从头开始寻找，反之从尾开始寻找。通过这种方式，使循环的次数至少降低了一半，提高了查找的性能，这种思想值得我们借鉴。
LinkedList的双向迭代
Java 中存在一个双向迭代器的接口：ListIterator，这个接口提供了向前和向后的迭代方法，如下所示：
LinkedList通过实现ListIterator来实现 双向迭代的功能。其中有如下重要概念：
private Node lastReturned ：上一次执行 next() 或者 previos() 方法时获得的节点
private Node next ：下一个节点
private int nextIndex：下一个节点的索引
expectedModCount：期望版本号
modCount：目前版本号
正向迭代（next）
正向迭代的思路，较为简单，就是判断 hasNext，后使用next方法取下一个元素。
public boolean hasNext() {
// 如果下一个元素的位置，未超过链表大小，则还有 后继节点
return nextIndex < size;
}
public E next() {
// 判断版本号是否被修改
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
// 保存本次获得的元素。（next其实是当前节。点在上一次执行 next() 方法时被赋值的。
// 第一次执行时，是在创建迭代器的时候，next 被赋值
lastReturned = next;
// next.next 是下一个节点，为下次迭代做准备
next = next.next;
// 变更当前索引
nextIndex++;
return lastReturned.item;
}
// 迭代器的构造方法，next第一次在这里被赋值
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
反向迭代（previous）
public boolean hasPrevious() {
// 如果上次节点索引大于0，则还有前驱节点
return nextIndex > 0;
}
// 取出前驱节点元素
public E previous() {
// 判断版本号是否被修改
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
// 这里比正向迭代复杂。
// next 为空场景：1:说明是第一次迭代，取尾节点(last); 2:上一次操作把尾节点删除掉了
// next 不为空场景：说明已经发生过迭代了，直接取前一个节点即可(next.prev)
lastReturned = next = (next == null) ? last : next.prev;
// 变更当前索引
nextIndex--;
return lastReturned.item;
}
迭代时删除（remove）
public void remove() {
// 判断版本号是否被修改
checkForComodification();
// lastReturned 是本次需要删除的值，分以下空和非空两种情况：
// lastReturned 为空，说明调用者没有主动执行过 next() 或者 previos()，直接抛出错误
// lastReturned 不为空，是在上次执行 next() 或者 previos()方法时获得的值
// ListIterator.remove方法注释中提到 抛出错误，有以下几种可能
// 1. 没有主动执行过 next() 或者 previos()
// 2. 在最后一次调用next/previous方法后，再调用了remove方法或add方法
if (lastReturned == null)
throw new IllegalStateException();
// 先准备好被删除节点的后继节点
Node<E> lastNext = lastReturned.next;
// 删除此节点，其中有 将size--
unlink(lastReturned);
if (next == lastReturned)
// next == lastReturned 的场景分析：从尾到头迭代，是第一次迭代，或者要删除最后一个元素的情况
// 这种情况下，previous() 方法里面设置了 lastReturned = next = last,所以 next 和 lastReturned会相等
// 这时候 lastReturned 是尾节点，lastNext 是 null，所以 next 也是 null，这样在 previous() 执行时，发现 next 是 null，就会把尾节点赋值给 next
next = lastNext;
else
// 其他情况下，需要减小当前索引
nextIndex--;
lastReturned = null;
// 修改版本号
expectedModCount++;
}
