注释

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;    // 头结点
分类: java

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:852 天
  • 访问总数:459651 人次
ICP备案号: 辽ICP备20003309号