java8集合框架(八)-List的实现类(LinkedList)

java8集合框架(八)-List的实现类(LinkedList)

前篇分析了ArrayList的源码,是基于数组实现的List。本篇分析基于链表的实现:LinkedList

Note:本篇源码分析基于jdk1.8版本

LinkedList

LinkedList的名字也很容易看出它的特色,核心数据结构是双向链表。通过继承关系可见它的意义还真不少:它承载了List``Queue``Deque三个接口的链表实现。链表实现的特点就是插入和删除非常高效,但随机访问就差很多了。LinkedList是非线程安全的,可接受null

数据结构

LinkedList的数据结构也很简单。链表的首尾节点加上元素个数。节点的定义也很常规。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//链表头指针
transient Node<E> first;
//链表尾指针
transient Node<E> last;
//实际元素个数
transient int size = 0;
//节点类型定义
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;
}
}

初始化

1
2
public LinkedList() {
}

说明:就这样,没有tunning的可能性。

增删改

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
//List的实现
//插入
public boolean add(E e) {
linkLast(e);
return true;
}
//指定索引位插入
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
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) {
// 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++;
}
//删
//删除指定元素,遍历
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;
}
//删除指定索引位元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
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;
}
//链表有首尾指针,如果查找的元素在前一半则从头遍历,否则从尾遍历
Node<E> node(int 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;
}
}
//改
//修改指定索引位的元素
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//Deque的实现
//增
//失败会返回特定值的插入元素
public boolean offer(E e) {
return add(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
//头部插入
public void addFirst(E e) {
linkFirst(e);
}
//尾部插入
public void addLast(E e) {
linkLast(e);
}
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++;
}
//删
//删除首节点
public E remove() {
return removeFirst();
}
//删除首节点
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//删除尾节点
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//失败会返回特定值的删除首节点
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
//模拟栈行为
//出栈
public E pop() {
return removeFirst();
}
//入栈
public void push(E e) {
addFirst(e);
}

查找

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
//List的实现
//指定索引位的查找
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//Deque的实现
//获取首节点
public E element() {
return getFirst();
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
//失败会返回特定值的获取首节点
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}

List2Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//桥梁
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
//支持泛型
public <T> T[] toArray(T[] a) {
if (a.length < size)
//反射产生数组
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}

说明:这是ListArray的桥梁方法。

思考

为什么LinkedList实现了Deque接口,但是ArrayList却没有呢?

ArrayList是披着List外皮的Array。数组是不适宜在顶部插入一个元素的,所以并没有顺便将Deque接口实现。但是Deque接口还真是有一个数组实现,那就是ArrayDeque,而这个以后会分析到。

总结

LinkedList由双向链表实现。在插入或删除的时候几乎没啥消耗,更不像ArrayList还需要数组拷贝。但是缺点也比较明显,就是不利于随机读取,需要迭代器和计数器,时间复杂度为O(n)。另外LinkedList也是Deque接口的链表实现。Deque接口的数组实现见ArrayDeque

作者: wuzhaoyang(John)
出处: http://wuzhaoyang.me/
因为作者水平有限,无法保证每句话都是对的,但能保证不复制粘贴,每句话经过推敲。希望能表达自己对于技术的态度,做一名优秀的软件工程师。