LinkedList
List和Deque接口的双向链表实现。实现所有可选的列表操作，并允许所有元素（包括null）。
所有操作均按双向链表的预期执行。索引到列表中的操作将从列表的开头或结尾开始遍历列表，从开头遍历还是从结尾遍历主要看哪个更接近指定索引的位置。
请注意，此实现是不同步的。如果多个线程同时访问一个链表，并且至少一个线程在结构上修改了链表，则它必须在外部保证同步。（结构修改是添加或删除一个或多个元素的任何操作；仅设置元素的值不是结构修改。）通常，通过在自然封装列表的某个对象上进行同步来完成此操作。
如果不存在这样的对象，则应使用Collections.synchronizedList方法“包装”列表。最好在创建时完成此操作，以防止意外的不同步访问列表：
List list = Collections.synchronizedList(new LinkedList(...));
此类的iterator和listIterator方法返回的迭代器是“快速失败”的：如果在创建迭代器后的任何时间除了通过迭代器自己的remove或add方法之外对列表进行结构修改，则迭代器将抛出ConcurrentModificationException。因此，面对并发修改，迭代器会快速干净地失败，而不会在未来的不确定时间内冒任意、不确定行为的风险。
请注意，迭代器的快速失败行为无法得到保证，因为通常来说，在存在不同步的并发修改的情况下，不可能做出任何严格的保证。快速失败的迭代器会尽最大努力抛出ConcurrentModificationException。因此，编写依赖于此异常以确保其正确性的程序是错误的：迭代器的快速失败行为应仅用于检测错误。
该类是Java集合框架的成员。
列表元素的数量。
指向第一个结点的指针。
恒成立：(first == null && last == null) || (first.prev == null && first.item != null)
指向最后一个结点的指针。
恒成立：(first == null && last == null) || (last.next == null && last.item != null)
构造一个空列表。
构造一个列表，该列表包含给定集合的元素，其顺序为该集合的迭代器返回顺序。
先调用无参构造函数，再调用 addAll 将参数中指定集合的元素添加进当前链表。
将参数中给定的元素 e 作为当前链表的第一个元素。
操作方法如下：
private void linkFirst(E e) {
// 取出链表的第一结点
final Node<E> f = first;
// 构造一个新的结点，该新结点的前驱结点为null、持有元素为e、后继结点为原第一结点
final Node<E> newNode = new Node<>(null, e, f);
// 设置新结点为第一结点
first = newNode;
if (f == null)
// 原第一结点为空，也即原链表是空的，并无结点，此时也设置当前列表的最后结点为上述新结点
last = newNode;
else
// 原第一结点不为空，说明原链表非空，此时需调整原第一结点的前驱结点为上述结点
f.prev = newNode;
size++;
modCount++;
}
将参数中给定的元素 e 作为当前链表的最后一个元素。
操作方法与 linkFirst 类似，只不过该方法是在链表的尾部进行操作。
在非null结点succ之前插入元素e。
void linkBefore(E e, Node<E> succ) {
// 此处未对succ进行判空，但要求其必须非空，否则会抛出NPE
// assert succ != null;
// 取出给定结点的前驱结点
final Node<E> pred = succ.prev;
// 构造一个新结点，以达成在给定结点与给定结点的前驱结点之间，将给定元素插入
// 该新结点的前驱结点为参数中给定结点的前驱结点
// 该新结点持有的元素为参数中给定的元素
// 该新结点的后继结点为参数中给定的结点
final Node<E> newNode = new Node<>(pred, e, succ);
// 将该新结点设置为给定结点的前驱结点
succ.prev = newNode;
if (pred == null)
// 如果给定结点的前驱结点为空，也即给定结点就是当前链表的第一结点，则设置链表的第一结点为该新结点
first = newNode;
else
// 如果给定结点的前驱结点不为空，则需要设置该前驱结点的后继结点为该新结点
pred.next = newNode;
size++;
modCount++;
}
取消到非空的第一结点f的链接。
private E unlinkFirst(Node<E> f) {
// 给定的结点f需要是头结点并且不为空
// assert f == first && f != null;
// 取出给定结点所持有的元素
final E element = f.item;
// 取出给定结点的后继结点
final Node<E> next = f.next;
// 将给定结点所持有的元素置为空
f.item = null;
// 将给定结点的后继结点置为null，帮助垃圾回收
f.next = null; // help GC
// 将上述取出的给定结点的后继结点设置为当前列表的头结点
first = next;
if (next == null)
// 如果给定结点的后继结点为空，也即原链表仅一个结点，此时将链表的最后结点设置为null
last = null;
else
// 如果给定结点的后继结点不为空，此时将该后继结点的前驱结点置为null，因为该后继结点已经成为链表的头结点了
next.prev = null;
size--;
modCount++;
return element;
}
取消到非空的尾结点l的链接。
该方法与unlinkFirst类似，只不过在链表的尾部进行操作。
取消到非null结点x链接。
本方法主要用于在链表中拆掉某个结点，其本质就是改变链表中该结点及其前驱和后继结点的关系，源码如下：
E unlink(Node<E> x) {
// 结点x不可为空，否则会抛出NPE
// assert x != null;
// 取出结点x所持有的元素
final E element = x.item;
// 取出结点x的后继结点
final Node<E> next = x.next;
// 取出结点x的前驱结点
final Node<E> prev = x.prev;
// 修改前驱关系
if (prev == null) {
// 前驱结点为空，说明给定的结点x是链表的头结点
// 此时将头结点设置给结点x的后继结点，这样就相当于从链表中拆掉了结点x
first = next;
} else {
// 前驱结点不为空，说明给定的结点x并非链表的头结点
// 此时将此前驱结点的后继结点设置为结点x的后继结点
prev.next = next;
// 同时将结点x的前驱结点设置为空
x.prev = null;
}
// 修改后继关系
if (next == null) {
// 后继结点为空，说明给定的结点x是链表的尾结点
// 此时将链表的最后结点设置为结点x的前驱结点，相当于从链表中拆掉了结点x
last = prev;
} else {
// 后继结点不为空，说明给定结点x并非链表的尾结点
// 此时，将结点x的后继结点的前驱结点设置为结点x的前驱结点
next.prev = prev;
// 同时将结点x的后继结点置为空
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
返回此列表中的第一个元素。
直接获取该链表的头结点 first ，如果该结点为空，则抛出 NoSuchElementException ，否则返回该结点所持有的元素。
返回此列表中的最后一个元素。
与 getFirst() 方法类似，只不过操作的是尾结点。
从此列表中删除并返回第一个元素。
该方法首先获取该链表的头结点 first ，如果该结点为空，则抛出 NoSuchElementException ，否则调用 unlinkFirst 方法拆除当前链表的头结点，该拆除方法将返回头结点所持有的元素，然后也作为本方法的返回值返回。
从此列表中删除并返回最后一个元素。
该方法与 removeLast 方法类似，只不过操作的是尾结点，调用的拆除方法是 unlinkLast 。
将给定的元素插入到此列表的开头。
该方法直接调用 linkFirst 方法。
将给定的元素追加到此列表的末尾。
该方法直接调用 linkLast 方法。
如果当前列表包含给定的元素 o 则返回 true 。更准确的说，当且仅当当前列表包含至少一个元素 o 满足 (o==null ? e==null : o.equals(e)) 时返回 true 。
该方法的主要逻辑是：通过 indexOf 方法判断得到的返回值是否为 -1 ，如果为 -1 则说明不包含该元素。
返回此列表中的元素数。也就是返回当前列表的属性 size 。
将指定的元素追加到此列表的末尾。
直接调用 linkLast 方法，然后返回 true 。
如果列表中存在指定元素，则从该列表中删除该元素的第一次出现。如果此列表不包含该元素，则它保持不变。更准确地说，删除满足 (o==null ? get(i)==null : o.equals(get(i))) 的最小索引 i 位置的元素（如果存在的话）。如果此列表包含指定的元素（或者等效地，如果此列表由于当前方法被调用而更改），则返回true。
该方法的源码如下：
public boolean remove(Object o) {
if (o == null) {
// 当给定元素为null时，从头开始遍历链表，找到第一个元素为null的结点，然后调用unlink方法将其从链表中拆除
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// 给定元素不为null时，从头开始遍历链表，找到第一个元素与给定元素equals的结点，调用unlink将其拆除
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
// 未找到给定元素，返回false
return false;
}
按照给定集合的迭代器返回的顺序，将给定集合中的所有元素追加到此列表的末尾。如果在操作进行过程中修改了给定的集合，则此操作的行为是不确定的。 （请注意，如果给定的集合是此列表，并且是非空的，则将发生这种情况。）
该方法的源码如下：
public boolean addAll(Collection<? extends E> c) {
// 调用可指定插入位置的addAll方法，指定的位置为列表的末尾
// 这也意味着，默认的addAll是将给定集合的元素拼接到链表的结尾的，除非用户指定插入位置
return addAll(size, c);
}
从指定位置开始，将指定集合中的所有元素插入此列表。将当前在该位置的元素（如果有）和任何后续元素右移（增加其索引）。新元素将按指定集合的迭代器返回的顺序出现在列表中。
源码如下：
public boolean addAll(int index, Collection<? extends E> c) {
// 判断给定的索引位置是否合理，需要大于等于0并小于等于size
checkPositionIndex(index);
// 将指定的集合转化为数组
Object[] a = c.toArray();
int numNew = a.length;
// 如果数组长度为0，也即指定的集合为空集合，此时返回false
if (numNew == 0)
return false;
// 定义两个结点，一个前驱结点、一个后继结点，这一步主要是找到将指定集合中元素编入链表的位置
// 指定集合的所有元素将放置在该前驱结点和后继结点之间
Node<E> pred, succ;
if (index == size) {
// index等于size，也就意味着此次是将指定集合的元素插入到列表的末尾
// 后继结点置空，
succ = null;
// 前驱结点置为当前链表的尾结点
pred = last;
} else {
// 取出指定索引位置index处的结点作为后继结点
succ = node(index);
// 取出指定索引位置index处的前驱结点作为前驱结点
pred = succ.prev;
}
// 遍历指定的集合所转化的数组a，将其中的元素逐个编入链表
for (Object o : a) {
// 将数组a中的元素强转为当前列表所持有的类型
@SuppressWarnings("unchecked") E e = (E) o;
// 创建一个新结点，持有当前遍历到的元素
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
// 如果前驱结点为null，说明是当前结点是头结点
first = newNode;
else
// 前驱结点不为null，则设置该前驱结点的后继结点为当前结点，从而实现将当前结点编入链表中
pred.next = newNode;
// 设置前驱结点变量为当前结点，作为下一个结点的前驱结点
pred = newNode;
}
// 这一步主要是将原链表指定索引位置index以后的结点挂在指定集合最后一个元素所在结点的后面
if (succ == null) {
// 后继结点为空，说明指定集合的元素是拼接到链表尾部的，则设置链表的尾部为当前结点（即指定结合最后元素所在的结点）
last = pred;
} else {
// 后继结点不为空，则设置当前结点（即指定结合最后元素所在的结点）的后继结点为该后继结点
pred.next = succ;
// 设置该后继结点的前驱结点为当前结点（即指定结合最后元素所在的结点）
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
从此列表中删除所有元素。此调用返回后，该列表将为空。
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
// 从头开始遍历链表
for (Node<E> x = first; x != null; ) {
// 先把当前结点的后继结点取出
Node<E> next = x.next;
// 然后将当前结点的元素、前驱结点、后继结点置为空
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
// 将链表的头部结点、尾部结点置为null
first = last = null;
size = 0;
modCount++;
}
返回此列表中指定位置的元素。
源码如下：
public E get(int index) {
// 校验元素索引
checkElementIndex(index);
// 使用node方法取出指定索引位置的结点，然后返回该结点所持有的元素
return node(index).item;
}
用指定的元素替换此列表中指定位置的元素。
元素如下：
public E set(int index, E element) {
// 检查指定索引是否是当前列表元素的索引
checkElementIndex(index);
// 取出指定索引位置的结点
Node<E> x = node(index);
// 取出指定位置结点的元素
E oldVal = x.item;
// 替换指定位置结点的元素为指定的元素
x.item = element;
// 返回当前结点原来的元素
return oldVal;
}
将指定的元素插入此列表中的指定位置。将当前在该位置的元素（如果有）和任何后续元素右移（将其索引添加一个）。
源码如下：
public void add(int index, E element) {
// 判断参数是否是迭代器或添加操作的有效位置的索引
checkPositionIndex(index);
if (index == size)
// 如果index等于size，则说明指定元素需要拼接到结尾
linkLast(element);
else
// index不等于size，则先使用node方法取出指定位置的结点
// 然后调用linkBefore将指定元素插入到该结点之前
linkBefore(element, node(index));
}
删除当前列表中指定位置的元素。然后将后面的元素左移（即索引减1）。返回被删除的元素。
源码如下：
public E remove(int index) {
// 先判断指定索引是否是当前列表元素的索引
checkElementIndex(index);
// 先调用node方法获取指定索引位置的结点，再调用unlink方法将此结点从当前链表中拆除
return unlink(node(index));
}
判断参数是否为现有元素的索引。要求索引大于等于0并且小于size。
源码如下：
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
判断参数是否是迭代器或添加操作的有效位置的索引。
其源码如下：
private boolean isPositionIndex(int index) {
// index必须大于等于0，并且小于等于列表的size
// 此处给定的索引位置等于size也可以是因为该方法还用于插入元素时的索引判断，而插入时可以插入到列表的末尾，此时的插入位置正好为size
return index >= 0 && index <= size;
}
构造一个 IndexOutOfBoundsException 异常的详细信息。在许多可能的错误处理代码重构中，这种“概述”在服务器和客户机vm中都表现得最好。
检查指定索引是否是当前列表元素的索引，不满足的话则抛出数组越界异常。
源码如下：
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
检查位置索引，其源码如下：
private void checkPositionIndex(int index) {
// 此处调用位置索引判断方法，如果是非合理索引位置，则抛出数组越界异常
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
返回指定元素索引处的（非空）结点。
源码如下：
Node<E> node(int index) {
// assert isElementIndex(index);
// size >> 1，对size做右移1位的操作，类似于对其做除以2的操作，但不会四舍五入而是直接舍弃
// 此处判断指定的索引index是更靠近链表的开头还是结尾，从更靠近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;
}
}
返回给定的元素在当前列表中第一次出现的索引位置，或者如果该元素在当前列表中不存在的话返回 -1 。更准确的说，返回满足 (o==null ? get(i)==null : o.equals(get(i))) 的最小索引 i ，或者无此索引的话返回 -1 。
索引，更像是基于数组的存储结构中才有的。其实， indexOf 是 List 接口中定义的方法，所以， LinkedList 中也实现了该方法，其并不能像基于数组的存储结构中那样，直接返回该元素在数组中的索引，而是从头开始遍历链表，从0开始计数，每经过一个结点，该计数值加1，命中的时候直接返回该计数值，源码如下：
public int indexOf(Object o) {
// 从0开始计数
int index = 0;
if (o == null) {
// 给定对象为空时，判断结点持有的元素是否为空，为空则命中
// 从头开始遍历当前链表
for (Node<E> x = first; x != null; x = x.next) {
// 判断结点持有的元素是否为空，若是，则返回当前计数值
if (x.item == null)
return index;
// 当前结点未命中，计数值加1
index++;
}
} else {
// 给定对象不为空空时，通过equals判断结点持有的元素与给定元素是否相等，相等则命中
// 从头开始遍历当前链表
for (Node<E> x = first; x != null; x = x.next) {
// 通过equals判断结点持有的元素与给定元素是否相等，若是，则返回当前计数值
if (o.equals(x.item))
return index;
// 当前结点未命中，计数值加1
index++;
}
}
// 当前列表中未匹配到给定的元素，返回-1
return -1;
}
返回当前列表中指定元素的最后一次出现的索引位置，或者如果指定元素在当前列表中不存在的话返回-1。更准确地说，返回满足 (o==null ? get(i)==null : o.equals(get(i))) 的最大索引 i 或者指定元素不存在的话返回-1。
该方法与 indexOf 类似，只不过当前方法是从链表的尾部开始向前遍历。
检索但不删除列表的头部元素（第一个元素）。
该方法的源码如下：
public E peek() {
// 首先取到头部结点
final Node<E> f = first;
// 如果头部结点为空，则返回空，否则返回头部结点所持有的元素
return (f == null) ? null : f.item;
}
检索但不删除列表的头部元素（第一个元素）。
该方法的源码如下：
public E element() {
// 直接调用getFirst方法
return getFirst();
}
当前方法与 peek 的不同之处在于，当前方法在获取到的头部结点为空时，抛出 NoSuchElementException 。
检索以及删除列表的头部元素（第一个元素）。
当前方法的源码如下：
public E poll() {
// 先取出列表的头部结点
final Node<E> f = first;
// 如果头部结点为空则返回空，否则调用unlinkFirst方法拆除当前头部结点
return (f == null) ? null : unlinkFirst(f);
}
检索以及删除列表的头部元素（第一个元素）。
当前方法的源码如下：
public E remove() {
// 直接调用removeFirst方法
return removeFirst();
}
该方法与 poll 方法的不同之处在于，该方法在获取到的头部结点为空时会抛出 NoSuchElementException 。
将给定的元素添加到列表的尾部（最后一个元素）。
当前方法的源码如下：
public boolean offer(E e) {
// 直接调用add方法
return add(e);
}
将指定的元素插入到列表的前面。
源码如下：
public boolean offerFirst(E e) {
// 直接调用addFirst方法
addFirst(e);
return true;
}
将指定的元素插入到列表的后面。
源码如下：
public boolean offerLast(E e) {
// 直接调用addLast方法
addLast(e);
return true;
}
检索但不删除列表的第一个元素，或者如果列表为空的话，返回 null 。
源码如下：
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
检索但不删除列表的第一个元素，或者如果列表为空的话，返回 null 。
源码如下：
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
检索并且删除列表的第一个元素，或者如果列表为空的话，返回 null 。
源码如下：
public E pollFirst() {
final Node<E> f = first;
// 与peekFirst的不同之处就在于此处不是直接返回头结点的元素，而是调用unlinkFirst方法拆除头结点
return (f == null) ? null : unlinkFirst(f);
}
检索并删除列表的最后一个元素，或者如果列表为空的话，返回 null 。
源码如下：
public E pollLast() {
final Node<E> l = last;
// 调用unlinkLast拆除尾部结点
return (l == null) ? null : unlinkLast(l);
}
将元素压入此列表所表示的堆栈。换句话说，将元素插入此列表的前面。
该方法直接调用了 addFirst 方法。
从此列表所表示的堆栈中弹出一个元素。换句话说，删除并返回此列表的第一个元素。
该方法直接调用了 removeFirst 方法。
删除此列表中第一次出现的指定元素（从头到尾遍历列表）。如果列表不包含该元素，则它保持不变。
该方法直接调用 remove 方法。
删除此列表中最后一次出现的指定元素（从头到尾遍历列表）。如果列表不包含该元素，则它保持不变。
该方法的源码如下：
public boolean removeLastOccurrence(Object o) {
// 判断指定的对象是否为空，以区分是使用 == null 进行判断还是使用equals进行判断
if (o == null) {
// 从尾部开始遍历，命中则使用unlink方法拆除结点
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
从列表中的指定位置开始（按适当顺序）返回此列表中元素的列表迭代器。遵守List.listIterator(int)的通用规范。
该列表迭代器是“快速失败”的：如果在创建Iterator之后的任何时间对列表进行结构修改，除非是通过列表迭代器自己的remove或add方法，否则列表迭代器将抛出ConcurrentModificationException。因此，面对并发修改，迭代器会干净利落地失败，而不会在未来的不确定时间内冒任意不确定行为的风险。
该方法的源码如下：
public ListIterator<E> listIterator(int index) {
// 检查指定索引是否大于等于0且小于等于size
checkPositionIndex(index);
// 返回ListItr
return new ListItr(index);
}
该类是 LinkedList 的私有类，提供了 ListIterator 的实现。
最后返回的结点。
下一个要返回的结点。
下一个结点的索引位置。
期望的修改次数。
当前类的唯一构造方法。
该方法的源码如下：
ListItr(int index) {
// assert isPositionIndex(index);
// 如果指定的索引等于当前列表的元素个数，则设定下一个结点为null，否则就设置为指定索引位置的结点
next = (index == size) ? null : node(index);
// 设定下一个结点的索引为指定索引
nextIndex = index;
}
判断当前迭代器是否还有下一个元素。源码如下：
public boolean hasNext() {
// 判断下一个结点的索引是否小于列表的元素个数，若小于则说明还有下一个元素
return nextIndex < size;
}
获取下一个元素。源码如下：
public E next() {
// 检查是否存在并发修改，存在则抛出异常
checkForComodification();
// 判断是否有下一个元素，若没有则抛出异常
if (!hasNext())
throw new NoSuchElementException();
// 设置最后返回的结点为下一个结点
lastReturned = next;
// 设置下一个结点的下一个结点为下一个结点，类似于游标后移一位
next = next.next;
// 下一个结点索引加1
nextIndex++;
// 返回最后返回结点所持有的元素，其实该最后返回的结点正是之前的下一个结点（next）
return lastReturned.item;
}
判断前面是否还有元素。源码如下：
public boolean hasPrevious() {
// 判断下一个索引是否大于0，若是，则认定为前面还有元素
return nextIndex > 0;
}
获取当前迭代器的上一个元素，源码如下：
public E previous() {
// 进行并发修改检查
checkForComodification();
// 不存在上一个元素，则抛出异常
if (!hasPrevious())
throw new NoSuchElementException();
// 如果下一个结点为空，设定上一个返回的结点、下一个结点为列表的尾结点
// 如果下一个结点不为空，设定上一个返回的结点、下一个结点为下一个结点的前驱结点
lastReturned = next = (next == null) ? last : next.prev;
// 下一个结点的索引减1
nextIndex--;
// 返回最后返回结点所持有的元素
return lastReturned.item;
}
返回下一个元素的索引，源码如下：
public int nextIndex() {
return nextIndex;
}
返回上一个元素的索引，源码如下：
public int previousIndex() {
// 返回下一个元素的索引减1
return nextIndex - 1;
}
删除当前遍历到的结点，也即最后返回的结点。源码如下：
public void remove() {
// 进行并发修改检查
checkForComodification();
// 如果最后返回的结点为空，则抛出异常
if (lastReturned == null)
throw new IllegalStateException();
// 取出最后返回结点的下一个结点
Node<E> lastNext = lastReturned.next;
// 调用unlink方法拆除最后返回的结点
unlink(lastReturned);
// 如果迭代器的下一个结点和最后返回的结点是同一个，则设置下一个结点为最后返回结点的下一个结点
// 否则，下一个结点的索引减1
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
// 设定最后返回结点为空
lastReturned = null;
// 期望修改次数加1
expectedModCount++;
}
替换最后一次返回的元素为参数中指定的元素。源码如下：
public void set(E e) {
// 如果最后一次返回的结点为空，则抛出 IllegalStateException
if (lastReturned == null)
throw new IllegalStateException();
// 检查是否存在并发修改
checkForComodification();
// 替换最后一次返回结点所持有的元素
lastReturned.item = e;
}
在最后一次返回的元素之后添加指定的元素。源码如下：
public void add(E e) {
// 进行并发修改检查
checkForComodification();
// 将最后返回的结点置为空
lastReturned = null;
// 如果next为空，说明迭代器当前所在的结点即为尾结点，直接使用linkLast方法把指定元素凭借到尾部即可
// 如果next不为空，则把指定元素加到next结点之前
if (next == null)
linkLast(e);
else
linkBefore(e, next);
// 下一个元素索引加1
nextIndex++;
// 期望并发修改次数加1
expectedModCount++;
}
对迭代器尚未遍历到的元素执行指定的操作。源码如下：
public void forEachRemaining(Consumer<? super E> action) {
// 指定的操作不可为空
Objects.requireNonNull(action);
// 在没有并发修改且尚有未遍历到的元素时进行遍历
while (modCount == expectedModCount && nextIndex < size) {
// 对当前遍历到的元素执行给定操作
action.accept(next.item);
// 设置最后返回结点为下一个结点
lastReturned = next;
// 设置下一个结点为下一个结点的下一个结点
next = next.next;
// 下一个元素索引加1
nextIndex++;
}
// 检查是否存在并发修改
checkForComodification();
}
检查是否存在并发修改，存在则抛出异常。源码如下：
final void checkForComodification() {
// 当前修改数与期望修改数不同，则抛出并发修改异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
链表中的结点，其持有一个元素，并记录当前结点的前驱结点、后继结点。
当前结点持有的元素。
当前结点持有的后继结点，用于记录当前结点的下一个结点是哪个。
当前结点持有的前驱结点，用于记录当前结点的上一个结点是哪个。
当前结点类的构造函数，也是唯一一个构造函数，用于构造一个结点。参数包括了一个结点的所需的所有要素。
获取一个降序的迭代器，即从尾部向头部开始遍历。
该方法创建一个DescendingIterator实例并返回。
通过ListItr.previous提供降序迭代器的适配器。
ListItr 实例，本类基于此实例对外提供服务。遍历的位置初始化为列表的尾部。
判断是否还有下一个，因为此类提供的是反向的遍历。所以， hasNext 返回的是列表是否还有上一个元素。其源码如下：
public boolean hasNext() {
// 遍历方向是从列表的尾部向头部，所以此处返回的是迭代器的hasPrevious()
return itr.hasPrevious();
}
获取下一个要遍历到的元素。此处也与上个方法相同， next 其实是列表的上一个元素。其源码如下：
public E next() {
return itr.previous();
}
删除当前遍历到的结点。源码如下：
public void remove() {
itr.remove();
}
调用父类的 clone 方法，也即 Object.clone 方法，源码如下：
@SuppressWarnings("unchecked")
private LinkedList<E> superClone() {
try {
// 调用父类的clone方法
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
// 如果捕获到不支持clone的异常，则包装成内部异常抛出
throw new InternalError(e);
}
}
返回此LinkedList的浅复制副本。 （元素本身不会被克隆）
public Object clone() {
LinkedList<E> clone = superClone();
// 将clone对象置为初始状态
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// 为clone对象初始化元素
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
以正确的顺序（从第一个元素到最后一个元素）返回一个包含此列表中所有元素的数组。
返回的数组将是“安全的”，因为此列表不保留对其的引用。 （换句话说，此方法必须分配一个新数组）。因此，调用者可以自由修改返回的数组。
此方法充当基于数组的API和基于集合的API之间的桥梁。
源码如下：
public Object[] toArray() {
// 创建一个数组
Object[] result = new Object[size];
int i = 0;
// 然后从头开始遍历列表，将每个元素放入数组
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
该方法返回一个数组，该数组按正确的顺序包含此列表中的所有元素（从第一个元素到最后一个元素）；返回数组的运行时类型是指定数组的运行时类型。如果列表适合指定的数组，则将其返回。否则，将使用指定数组的运行时类型和此列表的大小分配一个新数组。
如果列表适合指定的数组并有剩余空间（即，数组中的元素多于列表），则紧接列表末尾的数组中的元素将设置为null。 （如果调用者知道列表不包含任何null元素，则这对于确定列表的长度很有用。）
与toArray()方法类似，此方法充当基于数组的API和基于集合的API之间的桥梁。此外，此方法允许对输出数组的运行时类型进行精确控制，并且在某些情况下可以用来节省分配成本。
假设x是已知仅包含字符串的列表。以下代码可用于将列表转储到新分配的String数组中：
String[] y = x.toArray(new String[0]);
请注意，toArray(new Object[0])在功能上与toArray()相同。
源码如下：
public <T> T[] toArray(T[] a) {
// 如果指定的数组a的长度小于当前列表的长度，则先对数组进行扩容，扩到size大小
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
// 从头开始遍历数组，将每个元素放到数组中
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
// 如果数组a的长度大于列表的size，则设置数组列表元素的后面位置为null
if (a.length > size)
a[size] = null;
return a;
}
序列化版本ID。
将此LinkedList实例的状态保存到流中（即，对其进行序列化）。
源码如下：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// 将当前类的非静态和非瞬态字段写入此流
// Write out any hidden serialization magic
s.defaultWriteObject();
// 写出size
// Write out size
s.writeInt(size);
// 写出所有元素
// Write out all elements in the proper order.
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
63. private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException
从流中重新构造此LinkedList实例（即，将其反序列化）。
源码如下：
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// 从此流中读取所有非静态、非瞬态的属性
// Read in any hidden serialization magic
s.defaultReadObject();
// 读取size
// Read in size
int size = s.readInt();
// 读取所有元素
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
创建一个包含此列表所有元素的“后期绑定”和“快速失败”的 Spliterator 。
该Spliterator报告SIZED和ORDERED。重写该实现时应记录其他特征值的报告。
Spliterator还报告SUBSIZED并实现trySplit以允许有限的并行性。
@Override
public Spliterator<E> spliterator() {
return new LLSpliterator<E>(this, -1, 0);
}
LinkedList的拆分器实现，其 LL 即 LinkedList 的缩写。
批处理数组大小的增量，默认为1024。
批次最大数组大小，默认为33554432。因为拆分的时候会将“被拆分出”结点的元素放入数组，然后再构建成拆分器返回，此字段即是此处用作限制该数组容量上限的。
该拆分器所持有的LinkedList，除非遍历，否则可为null。
当前结点，在初始化之前为null。
估计的大小，在第一次需要之前为-1。
期望修改次数，设置 est 时初始化。
拆分的批次大小。
当前类唯一的构造方法。
LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
// 设定属性值
this.list = list;
this.est = est;
this.expectedModCount = expectedModCount;
}
获取列表预估的大小。主要用途包括确认是从头部开始遍历还是尾部开始遍历。
源代码如下：
final int getEst() {
int s; // force initialization
final LinkedList<E> lst;
// 判断如果预估的大小大于0，则直接返回。因为est在第一次使用前为-1
if ((s = est) < 0) {
if ((lst = list) == null)
// 如果列表为空，则预估大小为0
s = est = 0;
else {
// 列表不为空
// 赋值期望修改次数为列表的修改次数
expectedModCount = lst.modCount;
// 设置当前结点为列表的头结点
current = lst.first;
// 设置预估大小为列表的大小
s = est = lst.size;
}
}
return s;
}
获取预估大小，其实就是 getEst() 的 public 版本。不同之处还在于，当前方法会把返回结果强转为 long 类型。
源码如下：
public long estimateSize() { return (long) getEst(); }
执行拆分。源码如下：
public Spliterator<E> trySplit() {
Node<E> p;
// 获取预估大小
int s = getEst();
// 预估大小大于1 且 当前结点不为空 才执行拆分，否则返回空
if (s > 1 && (p = current) != null) {
// n取当前批次数 + 批次增量、列表预估大小、最大批次数组大小 三者中最小的那个
int n = batch + BATCH_UNIT;
if (n > s)
n = s;
if (n > MAX_BATCH)
n = MAX_BATCH;
// 声明一个对象数组，容量为前面计算出的n
Object[] a = new Object[n];
int j = 0;
// 从当前结点开始往后遍历，取出每个结点的元素放入数组，直至列表末尾或数组被塞满
do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
// 将上面遍历到的最后一个结点设置为拆分器的当前结点
current = p;
// 将上面遍历的结点个数设置为拆分器的批次大小
batch = j;
// 设置拆分器的预估大小为上一次的预估大小减去本次拆分出的结点数
est = s - j;
// 基于以上条件构造一个拆分器并返回
return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
}
return null;
}
对当前拆分器的剩余未遍历到的元素执行给定的操作。
源码如下：
public void forEachRemaining(Consumer<? super E> action) {
Node<E> p; int n;
// 指定操作不可为空
if (action == null) throw new NullPointerException();
// 仅在拆分器的预估大小大于0 并且 当前结点不为空时执行
if ((n = getEst()) > 0 && (p = current) != null) {
// 将当前结点置为null，也就是遍历完成后的状态
current = null;
// 将预估大小置为null，也就是遍历完成后的状态
est = 0;
// 从当前结点开始遍历，直接拆分器持有的最后一个结点，对每个元素执行给定操作
do {
E e = p.item;
p = p.next;
action.accept(e);
} while (p != null && --n > 0);
}
// 执行并发修改检查
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
}
对当前拆分器的当前结点执行给定的操作。
源码如下：
public boolean tryAdvance(Consumer<? super E> action) {
Node<E> p;
// 给定操作不可为空
if (action == null) throw new NullPointerException();
// 预估大小大于0 并且 当前结点不为空才执行
if (getEst() > 0 && (p = current) != null) {
// 对预估大小执行减1操作
--est;
// 取出当前结点所持有的元素
E e = p.item;
// 设置当前结点为下一个结点
current = p.next;
// 对元素执行给定的操作
action.accept(e);
// 判断是否存在并发修改
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 返回成功
return true;
}
return false;
}
返回当前拆分器的特征值。源码如下：
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}