注释
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; // 头结点