Java 容器源码分析之 LinkedList

概览

同 ArrayList 一样,LinkedList 也是对 List 接口的一种具体实现。不同的是,ArrayList 是基于数组来实现的,而 LinkedList 是基于双向链表实现的。LinkedList 类的声明如下:

1
2
3
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 继承自 AbstractSequentialList,实现了 List 接口,同时还实现了 Deque 接口。AbstractSequentialList 是 AbstractList 的子类,为基于顺序访问的链表提供了一些基本的实现。LinkedList 实现了 Deque 接口,Deque 接口是一种双端队列,可以作为 FIFO 队列和 LIFO 队列(栈)来使用。LinkedList 支持所有元素,包括 null。

下面基于JDK 8 中的代码对LinkedList的实现加以分析。

底层结构

LinkedList 基于双向链表进行实现,并使用两个引用 first 和 last 分别指向双向链表的头尾元素。同 ArrayList 一样,使用 modCount 来记录结构化修改的次数,并依此实现 fail-fast 机制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
transient int size = 0;

/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/

transient Node<E> first;

/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/

transient Node<E> last;

双向链表的节点结构如下,分别用 prev 和 next 指向该节点的前驱和后继结点。

1
2
3
4
5
6
7
8
9
10
11
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;
}
}

双向链表操作

LinkedList 提供的所有操作都是在双向链表的基础上完成的。Dqeue 接口的一些实现就是在 双向链表的两端进行操作,也是基于对头和尾部元素的操作。总的来说,双向链表的操作并不复杂,下面简单地进行解析,大部分操作都是对以下几种操作的封装。

向头部添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//将一个元素加入双向链表的头部
private void linkFirst(E e) {
final Node<E> f = first;
//新节点的前驱节点为null,后继节点为原来的头节点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null) //原来的头节点为空
//新加入的节点是第一个也是最后一个
last = newNode;
else
//修改原来头节点的前驱指向
f.prev = newNode;
//调整链表大小
size++;
//修改计数器
modCount++;
}

向尾部添加元素

1
2
3
4
5
6
7
8
9
10
11
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++;
}

从中间插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//在一个非空节点前插入元素
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
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++;
}

移除头部节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//将头节点从链表移除
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
//引用修改为null,方便GC
f.item = null;
f.next = null; // help GC
//调整头节点
first = next;
if (next == null) //移除后链表为空
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}

移除尾部节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}

移除任意一个非空节点

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
//移除一个非空节点
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; //后继

//注意对前驱为null的处理
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}

//注意对后继为null的处理
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}

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

清空链表

主要是为了方便垃圾回收器进行垃圾回收。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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++;
}

根据索引获取元素

因为是双向链表,可向前遍历,也可向后遍历。查找时双向进行,靠近头节点则从前向后查找;靠近尾部,则从后向前查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//根据索引获取元素
Node<E> node(int index) {
// assert isElementIndex(index);
//双向查找,根据index和size判断
//前半段,从头节点向后查找
//后半段,从尾节点向前查找
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;
}
}

反查一个元素的索引

第一次出现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}

迭代器

通过 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 上的这个问答