注释

LinkedList 是一个实现了 List 和 Deque 接口的双向链表实现。它支持所有可选的列表操作，并且允许包括 null 在内的所有元素。

该链表的操作表现符合我们对双向链表的期望。对于需要索引的操作，它会从离指定索引更近的一端开始遍历链表。

需要注意的是，这个实现不是线程安全的。如果多个线程同时访问链表，并且其中至少一个线程对链表进行结构性修改（添加或删除一个或多个元素），则必须在外部进行同步操作。（结构性修改是指添加或删除元素的操作，仅仅修改元素的值不属于结构性修改。）通常可以通过对一个自然封装了链表的对象进行同步操作来实现。如果不存在这样的对象，应该在创建链表时使用 Collections.synchronizedList 方法对链表进行包装，以避免意外的非同步访问。例如：

List list = Collections.synchronizedList(new LinkedList(...));

LinkedList 类返回的迭代器（通过 iterator 和 listIterator 方法获得的迭代器）是”快速失败”（fail-fast）的。如果在迭代器创建后，通过除迭代器自身的 remove 或 add 方法之外的任何方式对列表进行了结构性修改，迭代器将抛出 ConcurrentModificationException 异常。这样，在并发修改的情况下，迭代器能够快速、干净地失败，而不是在未确定的将来时间出现任意的、不确定的行为。

需要注意的是，在存在非同步的并发修改的情况下，无法保证迭代器的快速失败行为。快速失败迭代器仅尽最大努力抛出 ConcurrentModificationException 异常。因此，不能编写依赖于此异常来确保正确性的程序。迭代器的快速失败行为主要用于检测代码中的错误。

总之，LinkedList 类提供了一个灵活高效的双向链表实现，支持各种操作。但是，在并发环境中使用时，必须进行适当的同步操作以确保线程安全。

类签名

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

继承关系

内部类

private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;
}

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;
    }
}

private class DescendingIterator implements Iterator<E> {       // 这里设计很巧妙，改成向前遍历
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

// LinkedList的一个内部静态final类LLSpliterator，它实现了Spliterator接口。Spliterator接口是Java 8引入的用于支持并行遍历的接口，用于将数据源拆分成多个部分进行并行处理。
static final class LLSpliterator<E> implements Spliterator<E> {
    static final int BATCH_UNIT = 1 << 10;  // batch array size increment批处理数组大小的增量，使用位移操作符<<表示左移10位，即2的10次方，表示增量为1024。
    static final int MAX_BATCH = 1 << 25;  // max batch array size;最大批处理数组大小，使用位移操作符<<表示左移25位，即2的25次方，表示最大数组大小为33554432。
    final LinkedList<E> list; // null OK unless traversed在进行遍历操作之前，允许 list 字段为 null。一旦开始对 list 进行遍历操作，就要确保 list 不为 null，否则可能会导致 NullPointerException 异常。
    Node<E> current;      // current node; null until initialized 当前节点，初始化为null，直到第一次使用时才进行初始化。
    int est;              // size estimate; -1 until first needed估计的链表大小，初始化为-1，直到第一次需要时才设置。
    int expectedModCount; // initialized when est set初始化时预期的链表修改次数。
    int batch;            // batch size for splits用于拆分的批处理大小。
}

类属性

transient int size = 0;     // 大小
transient Node<E> last;     // 尾节点
transient Node<E> first;    // 头结点