首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

Java 容器源码分析之 LinkedList(5)

Java 容器源码分析之 LinkedList(5)

迭代器通过 next 的指向依次进行遍历。还提供了反向的迭代(从尾部到头部),通过 prev 的指向依次遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    //创建迭代器时的modCount,检测并发修改,fail-fast
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        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;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        //如果next == null, 前一个为尾节点
        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex - 1;
    }

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();

        Node<E> lastNext = lastReturned.next;
        //调用unlink方法移除元素
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        //修改modCount
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        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;            nextIndex++;        }        checkForComodification();    }    //检查并发修改,fail-fast    final void checkForComodification() {        if (modCount != expectedModCount)            throw new ConcurrentModificationException();    }}
小结LinkedList 是 List 接口基于双向链表的一种实现,同时还实现了 Deque 接口,可以作为 FIFO 和 LIFO 队列使用。双向链表的实现使得插入和删除操作的代价降低,可以在常数时间内完成;然而查找操作需要遍历列表,尽管双向列表使得可以从两端进行查找,但在长度较长时仍然需要较长的时间。
在大多数情况下会选择使用 ArrayList,尽管插入和删除代价相较于 LinkedList 更高,但随机访问的特性使得在查找方面 ArrayList 比 LinkedList 具有更多的优势。关于 ArrayList 和 LinkedList 的使用选择上可以参考 StackOverflow 上的 。
返回列表