死磕 Java 系列(二)—— 集合(3) LinkedList 源码解析

一、引言

在前面的文章《死磕 Java 系列(二)—— 集合(2) ArrayList 源码解析》中,博主对 ArrayList 进行了详细的分析。但是由于其基于数组的特性,虽然查找元素比较快,但是在频繁增删元素的场景下,显然它不是最优的选择。因此,jdk 给我们提供了 LinkedList,它更加适用于增删频繁的场景。


二、LinkedList 概述

  1. LinkedList 的长度可以动态增减,底层为双向链表结构;
  2. 插入和删除元素快,随机访问元素慢;
  3. 元素有序可重复,可以存储 null
  4. 效率高,但是线程不安全;

三、LinkedList 源码

3.1 链表

在正式进入学习之前,我们先来补充一点关于链表的基础知识。链表主要分为如下四种:

  1. 单向链表:通过每个节点的指针指向下一个节点而链接起来的结构,最后一个节点指向 null。

    单向链表

  2. 单向循环链表:在单向链表中,最后一个节点指向头节点。

    单向循环链表

  3. 双向链表:每个节点包含两个指针,分别指向前后两个节点;对于头节点和尾节点而言,其前后指向的节点分别为为 null。

    双向链表

  4. 双向循环链表:在双向链表中,头尾节点互相呼应。

    双向循环链表

  5. 关于顺序存储结构和随机存储结构的区别?

    • 随机存储结构:存取第 N 个数据时,不需要访问前 (N-1) 个数据,直接就可以对第 N 个数据操作,比如数组;
    • 顺序存储结构:存取第 N 个数据时,必须先访问前 (N-1) 个数据,以获得访问元素的位置,比如链表;

3.2 继承树

下面是 LinkedList 的继承树。

LinkedList继承树

由继承树可以看到,LinkedList 继承了 AbstractSequentialList,同时实现了 List 和 Deque 接口。除此之外,LinkedList 还实现了 Cloneable 和 Serializable 接口。

分析:

  • 关于 AbstractSequentialList?

    通过前面的学习我们知道,通过在抽象父类中将子类的通用方法实现,然后将特性方法交由子类自己去完成,这样使得代码更加简洁,同时也降低了子类的复杂度。其中,AbstractSequentialList 就是将顺序存储的集合中的通用方法在本类中提前实现了,从而降低了底层类设计时的工作量。

  • 关于 Deque 接口?

    Deque 表示双端队列,实现了该接口的元素支持从队列的头尾检索和插入元素。LinkedList 实现了这一接口,意味着其具有了双端队列的所有特性。

  • 关于 List、Cloneable 以及 Serializable 接口?

    这三个接口的内容已经在博主的上一篇博客《死磕 Java 系列(三)—— 集合(2) ArrayList 源码解析》中介绍过了,这里不再赘述。


3.3 源码解析

3.3.1 成员变量

1
2
3
4
5
6
7
8
9
10

// LinkedList 的成员变量
// 1.集合中元素的个数
transient int size = 0;

// 2.代表该集合中的头节点
transient Node<E> first;

// 3.代表该集合中的尾节点
transient Node<E> last;
1
2
3
4
5
6
7
8
9
10
11
12
13

// Node<E> 为静态内部类,代表每一个节点
private static class <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;
}
}

分析:

LinkedList 中的成员变量非常简单,值得的有以下两点:

  • 所有的成员变量都带有 transient 关键字,这意味着成员变量不会参与序列化过程;
  • 节点的类型为 Node,这是一个静态内部类,在下面会有介绍;

3.3.2 构造方法

1
2
3
4
5
6
7
8
9
10
11
12

// LinkedList 的构造方法
// 1.无参构造方法
public LinkedList() {
}

// 2.有参构造方法,将集合对象 C 转化为 LinkedList 对象
public LinkedList(Collection<? extends E> c) {
this();
// addAll() 是 LinkedList 本身的通用方法,用以将集合对象的元素添加到本集合中
addAll(c);
}

分析:

  • 一些注意点

    与 ArrayList 不同的是,LinkedList 不存在“默认容量”一说,也没有自动扩容机制。如前面所言,LinkedList 的底层结构为链表,当我们向集合中添加元素时,只需要在指定的位置将链断开,然后将新建节点插入,最后更新节点的相互引用即可。


3.3.3 私有方法

下面有些方法的权限修饰符为 default,姑且当作“私有”方法看待。这些方法都是为后面的公共方法服务的,提取出来便于在不同的公共方法中多次调用。

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

// LinkedList 的私有方法,选取几个作为分析,剩下的难度不大,不再赘述
// 这些“私有”方法会在下面得通用方法和迭代器中多次调用

// 1.添加元素到头节点
private void linkFirst(E e) {
// 保存旧的头节点
final Node<E> f = first;
// 创建新的头节点,同时让旧的头节点成为后继节点
final Node<E> newNode = new Node<>(null, e, f);
// 更新头节点信息
first = newNode;
// 判断最开始的旧的头节点是否存在
if (f == null)
// 如果不存在,说明之前的集合中不存在任何节点;那么新增的节点既是头节点,也是尾节点
last = newNode;
else
// 如果存在旧的头节点,则更新它的前驱节点(即新的头节点)
f.prev = newNode;
// 元素个数++
size++;
// 修改次数++
modCount++;
}

// 2.添加元素到尾节点,逻辑同上,不再赘述
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

// 3.在指定节点的前面添加新的节点
void linkBefore(E e, Node<E> succ) {
// 找到指定节点的前一个节点
final Node<E> pred = succ.prev;
// 在指定节点和其前一个节点间插入新的节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 让新的节点成为指定节点的前驱节点
succ.prev = newNode;
// 验证指定节点的前驱节点是否存在
if (pred == null)
// 如果前驱节点不存在,那么让新的节点成为集中的头节点
first = newNode;
else
// 否则让新的节点成为前驱节点的后继节点
pred.next = newNode;
size++;
modCount++;
}

// 4.删除集合中的头节点,并返回被删除的元素
private E unlinkFirst(Node<E> f) {
// 找到该节点存储的元素
final E element = f.item;
// 找到该节点的后继节点
final Node<E> next = f.next;
// 将头节点中的元素和其对后继节点的指向都清空
f.item = null;
f.next = null; // help GC
// 让头节点的后继节点成为新的头节点
first = next;
// 判断新的头节点是否为 null(即原集合中是否仅有一个节点)
if (next == null)
// 这说明原集合中仅有一个节点,删除后则没有任何节点了
last = null;
else
// 将新的头节点的前驱节点置为 null
next.prev = null;
size--;
modCount++;
// 返回被删除的头节点的元素
return element;
}

// 5.删除集合中的尾节点,并返回被删除的元素
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}

// 6.删除某个指定的节点,并返回被删除的元素
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;

if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}

if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}

x.item = null;
size--;
modCount++;
return element;
}

// 7.根据索引返回节点
Node<E> node(int index) {
// 利用二分的思想去判断 index 是离头节点更近还是尾节点更近,从而选其遍历起点
if (index < (size >> 1)) {
// 从头节点开始一级级往下遍历
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 从尾节点开始一级级往下遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

3.3.4 公共方法

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354

// LinkedList 的通用方法,只对其中的重难点进行分析,剩下相信读者也能懂
// 1.返回集合中的第一个元素
public E getFirst() {
final Node<E> f = first;
// 这个是为了判断集合中是否存在元素
if (f == null)
throw new NoSuchElementException();
// 返回头节点元素
return f.item;
}

// 2.同上,返回集合尾元素
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}

// 3.移除集合中的第一个元素
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
// 这里调用了私有方法 unlinkFirst(),在上面已经介绍过了
return unlinkFirst(f);
}

// 4.同上,删除集合中的尾元素
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}

// 5.添加元素到头节点
public void addFirst(E e) {
linkFirst(e);
}

// 6.添加元素到尾节点
public void addLast(E e) {
linkLast(e);
}

// 7.判断集合中是否包含某个元素
public boolean contains(Object o) {
return indexOf(o) != -1;
}

// 8.返回集合中元素的个数
public int size() {
return size;
}

// 9.添加元素到尾节点,并返回添加结果
public boolean add(E e) {
linkLast(e);
return true;
}

// 10.从集合中移除找到的第一个指定元素
public boolean remove(Object o) {
if (o == null) {
// 遍历集合
// 此种写法的特别之处在于从头节点开始,判断条件,执行操作,然后再让当前节点的
// 下一个节点成为新的遍历节点
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

// 11.将集合中元素添加到本集合中(从末尾开始)
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}

// 12.同上,只不过是从指定的索引位置开始添加
public boolean addAll(int index, Collection<? extends E> c) {
// 越界检查
checkPositionIndex(index);
// 将集合 C 转化成数组,并对其进行判空检查
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// 下面的工作是将插入位置节点及其前驱节点记录下来
// 可以理解为将链打断,分别记录下前半条链的链尾以及后半条链的链头节点,方便插入新的节点
Node<E> pred, succ;
if (index == size) {
// 这里意味着从链尾增加元素或者是向新链(空集合)中添加元素
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}

// 将数组中的元素插入到指定位置的前面去
for (Object o : a) {
("unchecked") E e = (E) o;
// 在指定节点和其前驱节点之间插入新的节点
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
// 若前驱节点为 null,则把新创建的节点置为头节点
first = newNode;
else
// 否则让新的节点成为前驱节点的后继节点
pred.next = newNode;
// 让新的节点成为下一轮循环中的 pred 节点
pred = newNode;
}

// 将后半条链与新链链接起来
if (succ == null) {
// 这里对应着上面 index == size 的情况(只有那时 succ == null)
// 无论是哪一种情况,最后一个添加的元素必定是集合中的最后一个元素
last = pred;
} else {
// 如果不是以上情况,对打断的链进行链接
pred.next = succ;
succ.prev = pred;
}

size += numNew;
modCount++;
return true;
}

// 13.清空集合
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}


// 14.返回指定节点的元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}

// 15.对指定位置的节点的元素值进行设置,并返回旧值
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}

// 16.在指定位置的节点的前或后(不固定)添加元素
public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
// 添加元素到链的末尾
linkLast(element);
else
// 在指定节点的前面添加元素
linkBefore(element, node(index));
}

// 17.删除某个指定的节点,并返回被删除的元素值
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}

public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}


// 查询操作
// 1.正向遍历返回第一个找到的指定元素的索引(-1 表示元素不存在)
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}

// 2.反向遍历返回第一个找到的指定元素的索引(-1 表示元素不存在)
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}


// 队列操作
// 1.返回集合的第一个元素(不会抛出异常)
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}

// 2.返回集合的第一个元素(会抛出异常)
public E element() {
return getFirst();
}

// 3.删除并返回集合的第一个元素(不会抛出异常)
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

// 4.删除并返回集合的第一个元素(会抛出异常)
public E remove() {
return removeFirst();
}

// 5.向集合的尾部添加元素
public boolean offer(E e) {
return add(e);
}


// 双端队列操作(这个是因为继承了 Deque 接口而实现的方法)
// 1.将指定元素添加到集合的头部
public boolean offerFirst(E e) {
addFirst(e);
return true;
}

// 2.将指定元素添加到集合的尾部
public boolean offerLast(E e) {
addLast(e);
return true;
}

// 3.返回集合头部的元素,不删除,不抛异常
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}

// 4.返回集合部的元素,不删除,不抛异常
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}

// 5.返回并删除集合头部的元素,抛异常
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

// 6.返回并删除集合尾部的元素,抛异常
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}

// 7.将指定的元素添加到集合的头部,和 offerFirst() 的区别在于没有返回值
public void push(E e) {
addFirst(e);
}

// 8.将集合中的第一个元素删除(不返回删除结果)
public E pop() {
return removeFirst();
}

// 9.删除指定元素(第一次在集合中遍历到的)
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}

// 10.删除指定元素(最后一次在集合中遍历到的)
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

3.3.5 迭代器

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

// LinkedLIst 的迭代器,调用迭代器实际上返回了一个实现了 List 接口的内部类
// 这与 ArrayList 的迭代器是一致的

// LinkedLIst 的普通迭代器(正向遍历)
// 按照指定的索引返回迭代器(从哪个节点开始迭代)
public ListIterator<E> listIterator(int index) {
// 越界检查
checkPositionIndex(index);
return new ListItr(index);
}

// 实现迭代器的内部类
private class ListItr implements ListIterator<E> {
// 上一次遍历的节点
private Node<E> lastReturned;
// 指定索引位置的下一个节点
private Node<E> next;
// 下一个索引位置
private int nextIndex;
private int expectedModCount = modCount;

// 但参数的构造方法,确定了下个节点即及其索引位置
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}


// 迭代器中的通用方法
// 1.判断是否有下一个元素
public boolean hasNext() {
return nextIndex < size;
}

// 2.指针后移,并返回当前遍历的元素
public E next() {
// 并发修改检查
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();

lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}

// 3.判断是否存在前驱节点
public boolean hasPrevious() {
return nextIndex > 0;
}

// 3.指针前移,并返回当前遍历的元素
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();

// 注意此时 lastReturned = next,即 lastReturned 和 next 指向了同一个节点
// 然后再把 lastReturned 和 next 的指向整体前移
// 此时若 next == null,说明到达了链尾,那么 null 的前驱节点肯定为 last(集合中的最后一个元素)
// 反之,前驱节点则为 next.prev
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}

// 4.返回下一次遍历的节点的索引
public int nextIndex() {
return nextIndex;
}

// 5.返回上一次遍历的节点的索引
public int previousIndex() {
return nextIndex - 1;
}

// 6.删除当前遍历循环中的元素
public void remove() {
checkForComodification();
// 这里说明 remove() 方法必须在 next() 之后执行
if (lastReturned == null)
throw new IllegalStateException();

Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}

// 7.修改当前遍历循环中的元素
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}

// 8.在迭代的过程中添加元素到集合中
public void add(E e) {
checkForComodification();
lastReturned = null;
// 根据“下一个节点”的位置判断插入的前后顺序
if (next == null)
linkLast(e);
else
linkBefore(e, next);
// 因为插入了新的节点,原本的“下一个节点”的索引肯定要 ++
nextIndex++;
expectedModCount++;
}

// 9.顺序遍历指针后面的节点,对每个节点上的元素执行指定的 action 操作
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();
}

// 10.并发修改检查
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

下面是 LinkedList 中的另一个迭代器 descendingIterator,此迭代器提供了一个反向遍历的功能,其底层还是基于 listIterator 实现的。在源码中可以看到 descendingIterator 借用了 listIterator 的方法,从而实现了反向遍历的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//-------------------------------------------------------------------
// LinkedLIst 的反向遍历迭代器
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}

private class DescendingIterator implements Iterator<E> {
// 可以看到 itr 是从链表的尾部开始的
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 和 ArrayList 一样,在 JDK 1.8 以后也新增了可分割的并行迭代器 spliterator。通过充分利用现代CPU的多线程能力,以提高迭代效率。

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
//-------------------------------------------------------------------
// LinkedLIst 的可分割并行迭代器
public Spliterator<E> spliterator() {
return new LLSpliterator<E>(this, -1, 0);
}

/** A customized variant of Spliterators.IteratorSpliterator */
static final class LLSpliterator<E> implements Spliterator<E> {
static final int BATCH_UNIT = 1 << 10; // batch array size increment
static final int MAX_BATCH = 1 << 25; // max batch array size;
final LinkedList<E> list; // null OK unless traversed
Node<E> current; // current node; null until initialized
int est; // size estimate; -1 until first needed
int expectedModCount; // initialized when est set
int batch; // batch size for splits

LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
this.list = list;
this.est = est;
this.expectedModCount = expectedModCount;
}

final int getEst() {
int s; // force initialization
final LinkedList<E> lst;
if ((s = est) < 0) {
if ((lst = list) == null)
s = est = 0;
else {
expectedModCount = lst.modCount;
current = lst.first;
s = est = lst.size;
}
}
return s;
}

// 1.返回未被执行指定 action 操作的元素的个数
public long estimateSize() { return (long) getEst(); }

// 2.对集合进行分割
public Spliterator<E> trySplit() {
Node<E> p;
int s = getEst();
if (s > 1 && (p = current) != null) {
int n = batch + BATCH_UNIT;
if (n > s)
n = s;
if (n > MAX_BATCH)
n = MAX_BATCH;
Object[] a = new Object[n];
int j = 0;
do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
current = p;
batch = j;
est = s - j;
return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
}
return null;
}

// 3.对指针后面的所有元素指定的 action 操作
public void forEachRemaining(Consumer<? super E> action) {
Node<E> p; int n;
if (action == null) throw new NullPointerException();
if ((n = getEst()) > 0 && (p = current) != null) {
current = null;
est = 0;
do {
E e = p.item;
p = p.next;
action.accept(e);
} while (p != null && --n > 0);
}
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
}

// 4.对当前遍历到的元素执行执行的 action 操作
public boolean tryAdvance(Consumer<? super E> action) {
Node<E> p;
if (action == null) throw new NullPointerException();
if (getEst() > 0 && (p = current) != null) {
--est;
E e = p.item;
current = p.next;
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}

// 5.返回特征值
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}

四、总结

由于 LinkedList 基于链表的特性,非常适用于频繁增删的场景。当我们需要对集合中的数据频繁进行增删时,建议使用 LinkedList 代替 ArrayList。

关于 List 的介绍到此为止,接下俩博主会介绍更多关于集合的知识,大家敬请期待!