一、概述
LinkedList是Java Collections Framework的一个成员，然后底层是基于双向链表来实现的。对于LinkedList来说，可能平常开发用的频率并没有ArrayList多，这并不是我们不去学习LinkedList原理的理由。我们知道，ArrayList的特点是随机访问效率很高，但是非尾部的插入和删除性能就比较低，因为要挪动元素位置。LinkedList和ArrayList一样实现了List接口，因为两者底层的实现不一样，造就了它的特点与ArrayList几乎正好相反。
接下来，本文会叙述LinkedList是如何维护这样一个双向链表的，基本操作是怎样实现的，以及其它的细节。
二、LinkedList源码解读
2.1、继承关系
从UML类图中可以看到，LinkedList直接或间接实现了Iterable、Collection、List、Deque、Queue、Cloneable、Serializable这7个接口；LinkedList直接或间接继承了AbstractSequentialList、AbstractList、AbstractCollection这3个抽象类。
可能细心的同学会发现，为什么AbstractList实现了List接口，LinkedList还要去再实现一次List接口？
关于这一点，在之前的Java集合系列：一文解读ArrayList源码「JDK11」一文中已有解答，除此之外，LinkedList和ArrayList在继承关系上是比较相似的，所以针对相同继承关系内容的叙述，本文不再次叙述，想去了解的话，可点击上文链接去了解。
2.1.1、Queue接口
Queue接口是一个队列接口，它对Collection接口进行了扩展。所谓队列，就类似于日常生活中的各种排队，特点就是先进先出，在尾部添加元素，从头部删除元素，它的接口定义为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public interface Queue<E> extends Collection<E> {
// 如果可以在不违反容量限制的情况下立即将指定的元素插入此队列，则在成功时返回true并在当前没有可用空间时抛出IllegalStateException
boolean add(E e);
// 如果可以在不违反容量限制的情况下立即将指定元素插入此队列，当使用容量受限的队列时，此方法通常优于add，后者可能仅通过抛出异常来插入元素失败
boolean offer(E e);
// 检索并删除此队列的头部。此方法与poll()的不同之处仅在于，如果此队列为空，它会抛出异常
E remove();
// 检索并删除此队列的头部，如果此队列为空，则返回null
E poll();
// 检索但不删除此队列的头部。此方法与peek不同之处仅在于，如果此队列为空，它会抛出异常
E element();
// 检索但不删除此队列的头部，如果此队列为空，则返回null
E peek();
}
|
Queue队列提供了插入、删除和检查操作。这些方法中的每一个都以两种形式存在：一种在操作失败时抛出异常，另一种返回一个特殊值（null或false ，具体取决于操作），如下图所示：
注意：Queue队列实现通常不允许插入null元素，尽管某些实现（例如 LinkedList）不禁止插入null。即使在允许它的实现中，也不应将null插入到Queue队列中，因为null也被poll方法用作特殊的返回值，以指示队列不包含任何元素。
实践一下，我们把LinkedList当作Queue队列来使用，如下代码：
1
2
3
4
5
6
7
|
Queue<String> queue = new LinkedList<>();
queue.offer("Jerry");
queue.offer("Tom");
queue.offer("May");
while (queue.peek() != null) {
System.out.println(queue.poll());
}
|
2.1.2、Deque接口
Deque接口对Queue接口进行了扩展，Deque是“double ended queue”的缩写，它定义了访问双端队列两端元素的方法，接口定义为：
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
|
public interface Deque<E> extends Queue<E> {
// 如果可以在不违反容量限制的情况下立即将指定的元素插入此双端队列的前面，如果当前没有可用空间则抛出IllegalStateException 。使用容量受限的双端队列时，通常最好使用方法offerFirst
void addFirst(E e);
// 如果可以在不违反容量限制的情况下立即插入指定的元素，则在此双端队列的末尾插入指定的元素，如果当前没有可用空间，则抛出IllegalStateException 。使用容量受限的双端队列时，通常最好使用方法offerLast。此方法等效于add
void addLast(E e);
// 将指定的元素插入此双端队列的前面，除非它违反容量限制。当使用容量受限的双端队列时，此方法通常优于addFirst方法，后者仅通过抛出异常才能插入元素失败。
boolean offerFirst(E e);
// 除非违反容量限制，否则在此双端队列的末尾插入指定的元素。当使用容量受限的双端队列时，此方法通常优于addLast方法，后者仅通过抛出异常才能插入元素失败
boolean offerLast(E e);
// 检索并删除此双端队列的第一个元素。此方法与pollFirst不同之处仅在于，如果此双端队列为空，它会抛出异常。
E removeFirst();
// 检索并删除此双端队列的最后一个元素。此方法与pollLast不同之处仅在于，如果此双端队列为空，它会抛出异常。
E removeLast();
// 检索并删除此双端队列的第一个元素，如果此双端队列为空，则返回null
E pollFirst();
// 检索并删除此双端队列的最后一个元素，如果此双端队列为空，则返回null
E pollLast();
// 检索但不删除此双端队列的第一个元素。此方法与peekFirst不同之处仅在于，如果此双端队列为空，它会抛出异常。
E getFirst();
// 检索但不删除此双端队列的最后一个元素。此方法与peekLast不同之处仅在于，如果此双端队列为空，它会抛出异常。
E getLast();
// 检索但不删除此双端队列的第一个元素，如果此双端队列为空，则返回null
E peekFirst();
// 检索但不删除此双端队列的最后一个元素，如果此双端队列为空则返回null
E peekLast();
// *** Queue methods ***
// 如果可以在不违反容量限制的情况下立即将指定元素插入此双端队列表示的队列（换句话说，在此双端队列的尾部），成功时返回true并在当前没有可用空间时抛出IllegalStateException .使用容量受限的双端队列时，通常最好使用offer 。此方法等效于addLast
boolean add(E e);
// 如果可以在不违反容量限制的情况下立即将指定元素插入此双端队列表示的队列（换句话说，在此双端队列的尾部），成功时返回true ，如果当前没有可用空间则返回false 。当使用容量受限的双端队列时，此方法通常优于add方法，后者仅通过抛出异常才能插入元素失败。此方法等效于offerLast
boolean offer(E e);
// 检索并删除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）。此方法与poll()的不同之处仅在于，如果此双端队列为空，它会抛出异常。此方法等效于removeFirst()
E remove();
// 检索并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素），或者如果此双端队列为空，则返回null 。此方法等效于pollFirst()
E poll();
// 检索但不删除由此双端队列表示的队列的头部（换句话说，此双端队列的第一个元素）。此方法与peek不同之处仅在于，如果此双端队列为空，它会抛出异常。此方法等效于getFirst()
E element();
// 检索但不删除由此双端队列表示的队列的头部（换句话说，此双端队列的第一个元素），或者如果此双端队列为空则返回null 。此方法等效于peekFirst()
E peek();
// *** Stack methods ***
// 如果可以在不违反容量限制的情况下立即将元素推入此双端队列表示的堆栈（换句话说，在此双端队列的头部），如果当前没有可用空间则抛出IllegalStateException
void push(E e);
// 从此双端队列表示的堆栈中弹出一个元素。换句话说，删除并返回此双端队列的第一个元素。此方法等效于removeFirst()
E pop();
}
|
Deque接口提供了插入、删除和检查的方法，这些方法中的每一个都以两种形式存在：一种在操作失败时抛出异常，另一种返回一个特殊值（ null或false ，具体取决于操作），如下图所示：
当双端队列用作队列时，会产生FIFO（先进先出）行为。元素在双端队列的末尾添加，并从开头删除。从Queue接口继承的方法与Deque接口方法完全等价，如下图所示：
除此之外，双端队列也可以用作LIFO（后进先出）堆栈。应优先使用此接口而不是使用Stack类。当双端队列用作堆栈时，元素从双端队列的开头被压入和弹出。Stack方法等同于Deque方法，如下图所示：
实践一下，我们把LinkedList当作Deque堆栈来使用，如下代码：
1
2
3
4
5
6
7
|
Deque<String> deque = new LinkedList<>();
deque.push("Jerry");
deque.push("Tom");
deque.push("May");
while (deque.peek() != null) {
System.out.println(deque.pop());
}
|
注意：当双端队列用作队列或堆栈时，peek方法同样有效；在任何一种情况下，元素都是从双端队列的开头提取的。
虽然并未严格要求Deque队列实现禁止插入空元素，但强烈建议它们这样做。强烈建议任何确实允许null元素的Deque实现的用户不要利用插入null的能力。之所以如此，是因为null被各种方法用作特殊的返回值，以指示双端队列为空。
Deque接口除了上面介绍的核心方法外，它还有一个迭代器方法，可以从后往前遍历，如下代码：
1
2
3
4
5
|
Deque<String> deque = new LinkedList<>(Arrays.asList(new String[]{"Jerry", "Tom", "May"}));
Iterator<String> iterator = deque.descendingIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
|
2.2、成员变量
1
2
3
4
5
6
7
8
|
// LinkedList的大小（它包含的元素数）
transient int size = 0;
// 指向第一个节点的指针
transient Node<E> first;
// 指向最后一个节点的指针
transient Node<E> last;
|
LinkedList的成员变量不多，我们重点看下内部类Node节点的实现，如下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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;
}
}
|
从上面Node节点的构造函数来看，Node节点的结构如下图所示：
LinkedList就是由一个个的Node节点双向连接而成，如下图所示：
2.3、构造方法
1
2
3
4
5
6
7
8
9
10
|
// 构造一个空列表
public LinkedList() {
}
// 构造一个包含指定集合元素的列表，按照集合迭代器返回元素的顺序
public LinkedList(Collection<? extends E> c) {
this();
// 按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾
addAll(c);
}
|
2.4、核心方法
2.4.1、插入
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
|
// ***********尾部插入***********
// 将指定的元素附加到此列表的末尾
public boolean add(E e) {
linkLast(e);
return true;
}
// 将指定的元素附加到此列表的末尾
public void addLast(E e) {
linkLast(e);
}
// 添加指定元素作为此列表的尾部（最后一个元素）
public boolean offer(E e) {
return add(e);
}
// 在此列表的末尾插入指定的元素
public boolean offerLast(E e) {
addLast(e);
return true;
}
// 按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
// ***********头部插入***********
// 在此列表的开头插入指定的元素
public void addFirst(E e) {
linkFirst(e);
}
// 在此列表的前面插入指定的元素
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
// 将一个元素推入此列表表示的堆栈中。换句话说，将元素插入此列表的前面
public void push(E e) {
addFirst(e);
}
// ***********中间插入***********
// 在此列表中的指定位置插入指定元素。将当前位于该位置的元素（如果有）和任何后续元素向右移动（将其索引加一）
public void add(int index, E element) {
// 判断参数是否是迭代器或添加操作的有效位置的索引
checkPositionIndex(index);
// 如果插入的索引位置为size，那说明是尾部插入
if (index == size)
// 执行尾部插入
linkLast(element);
else
// 先找到当前链表上指定index位置的node节点，然后再插入新节点
linkBefore(element, node(index));
}
// ***********插入核心实现***********
// 链接e作为最后一个元素
void linkLast(E e) {
// 获取当前链表的last节点
final Node<E> l = last;
// 创建一个新节点
final Node<E> newNode = new Node<>(l, e, null);
// 让新节点成为last节点
last = newNode;
// 如果last节点为null，说明这是第一次插入新节点，所以新节点也是first节点
if (l == null)
first = newNode;
else
// 否则新节点是last节点的下一个节点
l.next = newNode;
// 更新size：元素个数+1
size++;
modCount++;
}
// 链接e作为第一个元素
private void linkFirst(E e) {
// 获取当前链表的first节点
final Node<E> f = first;
// 创建一个新节点
final Node<E> newNode = new Node<>(null, e, f);
// 让新节点成为last节点
first = newNode;
// 如果first节点为null，说明这是第一次插入新节点，所以新节点也是last节点
if (f == null)
last = newNode;
else
// 否则新节点是first节点的上一个节点
f.prev = newNode;
// 更新size：元素个数+1
size++;
modCount++;
}
// 返回指定元素索引处的（非空）节点。
Node<E> node(int index) {
// assert isElementIndex(index);
// size >> 1 == size/2
// 如果index < size/2，那么就从first节点开始往后遍历查找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 如果index >= size/2，那么就从last节点开始往前遍历查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// 在非空节点 succ 之前插入元素 e
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 获取当前链表的succ节点的前一个节点pred
final Node<E> pred = succ.prev;
// 创建一个新节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 让新节点成为succ节点的前一个节点
succ.prev = newNode;
// 如果pred节点为null，说明这是插入到头节点位置，所以新节点也是first节点
if (pred == null)
first = newNode;
else
// 否则新节点是pred节点的下一个节点
pred.next = newNode;
// 更新size：元素个数+1
size++;
modCount++;
}
// 将指定集合中的所有元素插入此列表，从指定位置开始。将当前位于该位置的元素（如果有）和任何后续元素向右移动（增加它们的索引）。新元素将按照指定集合的迭代器返回的顺序出现在列表中。
public boolean addAll(int index, Collection<? extends E> c) {
// 判断参数是否是迭代器或添加操作的有效位置的索引
checkPositionIndex(index);
// 将集合c的元素按集合c的顺序转换为数组返回
Object[] a = c.toArray();
// 如果数组长度为0，那么返回false
int numNew = a.length;
if (numNew == 0)
return false;
// 定义当前链表index索引对应的succ节点，以及succ节点的前节点pred
Node<E> pred, succ;
// 如果index == size，说明是尾部插入
if (index == size) {
// size位置的节点为null
succ = null;
// pred节点为插入位置的前节点last
pred = last;
} else {
// 否则是中间插入，那么先找到当前链表上指定index位置的node节点，然后再插入新节点
succ = node(index);
// pred为succ的前节点
pred = succ.prev;
}
// 遍历数组，让数组转换为链表
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// 创建一个新节点
Node<E> newNode = new Node<>(pred, e, null);
// 如果pred节点为null，说明这是插入到头节点位置，所以新节点也是first节点
if (pred == null)
first = newNode;
else
// 否则新节点是pred节点的下一个节点
pred.next = newNode;
// 每一轮循环结束，新节点就是pred节点
pred = newNode;
}
// 如果succ节点为null，说明是尾部插入，此时插入已经完成，那么pred节点为数组的最后一个节点，所以理所应当成为last节点
if (succ == null) {
last = pred;
} else {
// 如果succ节点不为null，说明是中间插入，此时插入已经完成，那么数组的最后一个节点指向插入位置节点succ
pred.next = succ;
// 数组的最后一个节点pred，理所应当成为插入位置节点succ的上一个节点
succ.prev = pred;
}
// 更新size：元素个数+数组长度
size += numNew;
modCount++;
return true;
}
|
2.4.2、删除
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
|
// ***********尾部删除***********
// 从此列表中移除并返回最后一个元素
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// 检索并删除此列表的最后一个元素，如果此列表为空，则返回null
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
// ***********头部删除***********
// 检索并删除此列表的头部（第一个元素）
public E remove() {
return removeFirst();
}
// 检索并删除此列表的头部（第一个元素）
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// 从此列表中移除并返回第一个元素。
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// 检索并删除此列表的第一个元素，如果此列表为空，则返回null
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// 从此列表表示的堆栈中弹出一个元素。换句话说，删除并返回此列表的第一个元素
public E pop() {
return removeFirst();
}
// ***********中间删除***********
// 移除此列表中指定位置的元素。将任何后续元素向左移动（从其索引中减去一个）。返回从列表中删除的元素。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
// ***********删除核心实现***********
// 取消链接非空的第一个节点f
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 获取node节点的元素element
final E element = f.item;
// 获取node节点的后继节点
final Node<E> next = f.next;
// 将node节点持有的元素item置为null
f.item = null;
// 将node节点持有的后继节点指针置为null
f.next = null; // help GC
// node节点的下一个节点成为first节点
first = next;
// 如果next节点为null，说明最后一个节点也被删除了，那么last节点置为null
if (next == null)
last = null;
else
// 否则node节点置为null
next.prev = null;
// 更新size：元素个数-1
size--;
modCount++;
return element;
}
// 取消链接非空的最后一个节点l
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
// 获取node节点的元素element
final E element = l.item;
// 获取node节点的前驱节点
final Node<E> prev = l.prev;
// 将node节点持有的元素item置为null
l.item = null;
// 将node节点持有的前躯节点指针置为null
l.prev = null; // help GC
// node节点的上一个节点成为last节点
last = prev;
// 如果prev节点为null，说明最后一个节点也被删除了，那么first节点置为null
if (prev == null)
first = null;
else
// 否则node节点置为null
prev.next = null;
// 更新size：元素个数-1
size--;
modCount++;
return element;
}
// 取消链接非空节点x
E unlink(Node<E> x) {
// assert x != null;
// 获取node节点的元素element
final E element = x.item;
// 获取node节点的后继节点
final Node<E> next = x.next;
// 获取node节点的前驱节点
final Node<E> prev = x.prev;
// 如果prev节点为null，说明是头部删除，那么next节点成为first节点
if (prev == null) {
first = next;
} else {
// 如果prev节点不为null，说明是中间删除，那么next节点成为前驱节点prev的下一个节点
prev.next = next;
// node节点的前驱节点指针置为null
x.prev = null;
}
// 如果next节点为null，说明是尾部删除，那么prev节点成为last节点
if (next == null) {
last = prev;
} else {
// 如果prev节点不为null，说明是中间删除，那么prev节点成为后继节点next的上一个节点
next.prev = prev;
// node节点的后继节点指针置为null
x.next = null;
}
// 将node节点持有的元素item置为null
x.item = null;
// 更新size：元素个数-1
size--;
modCount++;
return element;
}
// 从此列表中移除第一次出现的指定元素（如果存在）。如果此列表不包含该元素，则它保持不变。更正式地说，删除具有最低索引i元素
public boolean remove(Object o) {
// 如果要删除的元素为null，那么就从first节点开始往后遍历，直到找到第一个为null的元素，然后执行删除
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// 如果要删除的元素不为null，那么就从first节点开始往后遍历，直到找到第一个和o相同的元素，然后执行删除
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
|
2.4.3、更改
1
2
3
4
5
6
7
8
|
// 用指定元素替换此列表中指定位置的元素
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
|
2.4.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
|
// ***********头部检索***********
// 检索但不删除此列表的头部（第一个元素）
public E element() {
return getFirst();
}
// 检索但不删除此列表的头部（第一个元素）
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
// 返回此列表中的第一个元素
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
// 检索但不删除此列表的第一个元素，如果此列表为空，则返回null
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
// ***********尾部检索***********
// 返回此列表中的最后一个元素
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
// 检索但不删除此列表的最后一个元素，如果此列表为空，则返回null
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
// ***********中间检索***********
// 返回此列表中指定位置的元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
|
2.5、其它方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
// 返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1，更正式地说，返回具有最低索引i元素
public int indexOf(Object o) {
int index = 0;
// 如果要查找的元素为null，那么就从first节点开始往后遍历，直到找到第一个为null的元素，然后返回index
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
// 如果要查找的元素不为null，那么就从first节点开始往后遍历，直到找到第一个和o相同的元素，然后返回index
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
|
三、总结
在LinkedList的源码中，并没有与并发相关的代码，所以说LinkedList是非线程安全类，在并发环境下多个线程同时操作，会引发不可预知的错误。应该使用Collections.synchronizedList方法包装列表，最好在创建时完成，如下代码：
1
|
List list = Collections.synchronizedList(new LinkedList(...));
|
另外，LinkedList要根据实际的业务场景来使用，比如说，如果列表长度未知，添加、删除操作比较多，尤其经常从两端进行操作，而按照索引位置访问相对比较少，使用LinkedList会有更好的性能。