Java 容器源码分析之 LinkedList（5）
|
- UID
- 1066743
|
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 上的 。 |
|
|
|
|
|
