Java源码之LinkedList

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2017/08/29/Java源码之LinkedList/

访问原文「Java源码之LinkedList

关于LinkedList

似乎我们在工作中很少用到LinkedList,大部分都是使用ArrayList。先来看一下LinkedList的定义吧,它是ListDeque接口的双向链表实现;实现所有可选列表操作,并允许所有元素(包括null);所有的操作都实在操作双向列表;索引到列表中的操作将从开始或结束遍历列表,以更接近指定的索引为准。从这个定义来看,这个LinkedList更适合较多插入和删除元素,较少读取元素,因为插入和删除元素不涉及重排数据。

至于Deque是什么。Deque是支持两端元素插入和移除的线性集合,而名称deque双端队列(double ended queue)的缩写,通常发音为deck。既然它是个列表,那它确实继承了Queue,也支持所有与Queue相关的方法。本文不再对deque做详细说明。

LinkedList主要成员变量

下面是LinkedList的主要成员变量。可以看到包含头指针和尾指针,而Node也是双向链表节点的表示,也就是说LinkedList真的是双向链表表示的。

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
// 列表大小
transient int size = 0;
/**
* 指向头结点的指针
*/
transient Node<E> first;
/**
* 指向尾节点的指针
*/
transient Node<E> last;
// Node类
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核心方法

LinkedList的主要方法如下所示。可以看到这些方法都是对链表的操作,包括向头、尾插入节点,向一个节点之前插入节点,删除头尾、中间节点等。

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
/**
* 将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++;
}
/**
* 将e作为尾节点加入链表中
*/
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++;
}
/**
* 将e插入至节点succ前.
*/
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++;
}
/**
* 删除头节点f,f == first && f != null;
*/
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;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
/**
* 删除尾节点l,l == last && l != null;
*/
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;
}
/**
* 删除中间节点x,x != null
*/
E unlink(Node<E> x) {
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;
}

List常用方法

为什么叫List常用方法,因为LinkedList是双向队列,包含队列操作,这节不予说明。
下面列出了addremoveget这三个常用方法。从前两个方法可以看到它用到了上节介绍的核心方法;而get方法可以看到是一个遍历搜索的方法,可以明显的发现如果这个列表的get方法在使用中频繁出现,那么我们应该选择ArrayList而不是LinkedList

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
/**
* 将元素加入至链表尾部
*
* 等同于addLast
*
* @param e 将要加入列表的元素
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 从列表中删除指定元素的第一个出现(如果存在)。如果此列表不包含该元素,则它不会更改。
* 正式的说,删除具有最低索引i的元素,使得(o==null?get(i)==null:o.equals(get(i)))。
* 如果列表包含这个元素则返回true
*
* @param o 需要删除的元素
* @return 如果列表包含这个元素则返回true
*/
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;
}
/**
* 返回指定位置的元素
*
* @param index 元素位置(索引)
* @return 指定位置的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* 返回指定位置的元素
* 位置离头节点近的话从头节点往后搜
* 位置离尾节点近的话从尾节点往前搜
*/
Node<E> node(int index) {
// assert isElementIndex(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;
}
}

Deque常用方法

与上节相似,因为LinkedList实现了Deque接口,包含队列操作,这节将介绍几个常用的队列操作。
下面列出了peekpollofferpushpop这五个常用方法。peek方法直接返回头节点,poll方法等同于第三节介绍的unlinkFirst方法,offer方法最终等同于linkLastpush方法等同于addFirst方法,而addFirst方法实际上等同于第三节介绍的linkFirst方法,pop方法最终等同于unlinkFirstpeekpolloffer这三个方法实现了队列这一先入先出的数据结构,而pushpop这两个方法实现了这一先入后出的数据结构。

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
/**
* 获取头节点,但不删除
*
* @return 返回头节点,如果队列为空则返回null
* @since 1.5
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* 获取头节点,并删除
*
* @return 返回头节点,如果队列为空则返回null
* @since 1.5
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* 将元素加入列表尾部.
*
* @param e 加入的元素
* @return true
* @since 1.5
*/
public boolean offer(E e) {
return add(e);
}
/**
* 在该列表的前面插入元素
*
* @param e 插入的元素
* @since 1.6
*/
public void push(E e) {
addFirst(e);
}
/**
* 删除并返回头节点
*
* @return 头节点
* @throws NoSuchElementException if this list is empty
* @since 1.6
*/
public E pop() {
return removeFirst();
}

总结一下

LinkedList作为一个平时不常使用的类其结构是比较简单的。由于其内部表示为链表结构,所以核心方法均为链表操作。进而所有的主要方法都是由这些核心方法扩展而来。
本文只介绍几个常用的方法,实际上LinkedList中包含了很多其他方法,例如:addFirstaddLastremoveLastofferFirstofferLast等等,实际上都是由本文第三节介绍的核心方法扩展或者仅仅是改了名字,有兴趣的同学可以详细学习一下,我这里就不详细介绍了。