Java源码解析 —— LinkedList

Contents
  1. 前言
  2. LinkedList简介
    1. 定义
    2. LinkedList属性
    3. LinkedList构造函数
  3. 源码解析
    1. 增加
    2. 删除
    3. 修改
    4. 查找
    5. 是否包含
    6. Deque双端队列
    7. 总结
  4. 对LinkedList以及ArrayList的迭代效率比较
  5. 总结

前言

LinkedList与ArrayList一样实现List接口,只是ArrayList是List接口的大小可变数组的实现,LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList,而随机访问则比ArrayList逊色些。

构造图如下:
蓝色线条:继承
绿色线条:接口实现

LinkedList

LinkedList简介

LinkedList是基于链表结构的一种List,LinkedList就是基于双向链表设计的。

定义

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

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口,能对它进行队列操作。
LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
LinkedList 是非同步的。

LinkedList属性

1
2
3
transient int size = 0;
transient Node<E> first;
transient Node<E> last;

LinkedList中提供了上面三个属性,其中size和ArrayList中一样用来计数,表示list的元素数量;first是链表的第一个节点,last是链表的最后一个节点。Node则是链表的节点对象。

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;
}
}

Node为LinkedList的内部类,其中定义了当前存储的元素,以及该元素的上一个元素和下一个元素。

LinkedList构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 构造一个空的LinkedList .
*/
public LinkedList() {
}
/**
* 构造一个包含指定 collection 中的元素的列表,这些元素按其 collection 的迭代器返回的顺序排列
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

源码解析

增加

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
/**
* 将一个元素添加至list尾部
*/
public boolean add(E e) {
// 将节点e连至末尾
linkLast(e);
return true;
}
/**
* 在指定位置添加元素
*/
public void add(int index, E element) {
// 检查index是否越界
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
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;
}
}
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++;
}
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++;
}
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++;
}
/**
* 添加一个集合元素到list中
*/
public boolean addAll(Collection<? extends E> c) {
// 将集合元素添加到list最后的尾部
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 越界检查
checkPositionIndex(index);
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) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}

看似代码逻辑比较复杂,其实核心就是双向链表的存储结构,核心逻辑:

  1. 将元素转换为链表节点;
  2. 增加该节点的前后引用(即prev和next分别指向哪一个节点);
  3. 前后节点对该节点的引用(前节点的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
public E remove() {
return removeFirst();
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
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;
}

修改

1
2
3
4
5
6
7
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}

只要修改该节点上的元素就好了。

查找

get()方法的主体还是调用了node(int index)方法。

1
2
3
4
5
6
7
/**
* 查找指定索引位置的元素
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}

为了优化查询效率,LinkedList采用了一次简单的二分,判断index和size中间位置的距离,采取从后向前还是从前向后遍历。

到这里我们明白,基于双向链表实现的LinkedList,通过索引Index的操作时低效的,index所对应的元素越靠近中间所费时间越长。而向链表两端插入和删除元素则是非常高效的(如果不是两端的话,都需要对链表进行遍历查找)。

是否包含

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean contains(Object o) {
return indexOf(o) != -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;
}

indexOf查询元素位于容器的索引位置,都是需要对链表进行遍历操作,当然也就是低效了。

Deque双端队列

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
/**
* Adds the specified element as the tail (last element) of this list.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Queue#offer})
* @since 1.5
*/
public boolean offer(E e) {
return add(e);
}
/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Returns the first element in this list.
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* Pushes an element onto the stack represented by this list. In other
* words, inserts the element at the front of this list.
*
* <p>This method is equivalent to {@link #addFirst}.
*
* @param e the element to push
* @since 1.6
*/
public void push(E e) {
addFirst(e);
}
/**
* Inserts the specified element at the beginning of this list.
*
* @param e the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* Links e as first element.
*/
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++;
}

Deque的实现还是很简单的,逻辑都是基于上面讲的链表操作的。

总结

  1. LinkedList实际上是通过双向链表去实现的。
    它包含一个非常重要的内部类:Node。Node是双向链表节点所对应的数据结构,它包括的属性有:当前节点所包含的值,上一个节点,下一个节点。
  2. 从LinkedList的实现方式中可以发现,它不存在容量不足的问题。
  3. LinkedList的克隆函数,即是将全部元素克隆到一个新的LinkedList对象中。
  4. LinkedList实现java.io.Serializable。当写入到输出流时,先写入“容量”,再依次写入“每一个节点保护的值”;当读出输入流时,先读取“容量”,再依次读取“每一个元素”。
  5. 由于LinkedList实现了Deque,而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式:一种形式在操作失败时抛出异常,另一种形式返回一个特殊值(null 或 false,具体取决于操作)。

对LinkedList以及ArrayList的迭代效率比较

先说结论:ArrayList使用最普通的for循环遍历比较快,LinkedList使用foreach循环比较快

ArrayList是实现了RandomAccess接口而LinkedList则没有实现这个接口。事实上,如果使用普通for循环遍历LinkedList,其遍历速度将慢得令人发指

1
2
3
4
5
6
7
8
9
// for循环
for (int i = 0; i < list.size; i++) {
list.get(i);
}
// foreach or iterator(做foreach的时候,编译器默认使用这个集合的iterator)
for (Iterator i = list.iterator(); i.hasNext()) {
i.next();
}

我们上面说到了LinkedList的get()方法实现,也就不难理解为何使用for循环迭代LinkedList如此之慢了。

总结

ArrayList和LinkedList的比较

  1. 顺序插入速度ArrayList会比较快,因为ArrayList是基于数组实现的,数组是事先new好的,只要往指定位置塞一个数据就好了;LinkedList则不同,每次顺序插入的时候LinkedList将new一个对象出来,如果对象比较大,那么new的时间势必会长一点,再加上一些引用赋值的操作,所以顺序插入LinkedList必然慢于ArrayList。
  2. 基于上一点,因为LinkedList里面不仅维护了待插入的元素,还维护了Node的前置Node和后继Node,如果一个LinkedList中的Node非常多,那么LinkedList将比ArrayList更耗费一些内存。
  3. 数据遍历的速度,看最后一部分,这里就不细讲了,结论是:使用各自遍历效率最高的方式,ArrayList的遍历效率会比LinkedList的遍历效率高一些
  4. 有些说法认为LinkedList做插入和删除更快,这种说法其实是不准确的:
  • LinkedList做插入、删除的时候,慢在寻址,快在只需要改变前后Entry的引用地址
  • ArrayList做插入、删除的时候,慢在数组元素的批量copy,快在寻址

所以,如果待插入、删除的元素是在数据结构的前半段尤其是非常靠前的位置的时候,LinkedList的效率将大大快过ArrayList,因为ArrayList将批量copy大量的元素;越往后,对于LinkedList来说,因为它是双向链表,所以在第2个元素后面插入一个数据和在倒数第2个元素后面插入一个元素在效率上基本没有差别,但是ArrayList由于要批量copy的元素越来越少,操作速度必然追上乃至超过LinkedList。

从这个分析看出,如果你十分确定你插入、删除的元素是在前半段,那么就使用LinkedList;如果你十分确定你删除、删除的元素在比较靠后的位置,那么可以考虑使用ArrayList。如果你不能确定你要做的插入、删除是在哪儿呢?那还是建议你使用LinkedList吧,因为一来LinkedList整体插入、删除的执行效率比较稳定,没有ArrayList这种越往后越快的情况;二来插入元素的时候,弄得不好ArrayList就要进行一次扩容,记住,ArrayList底层数组扩容是一个既消耗时间又消耗空间的操作