Java LinkedList源码浅析

简介

LinkedList是一种双向链表数据结构,每个节点维护了自身的数据及前后节点的指针。

链表

链表是由一系列非连续节点组成的数据结构。链表分为担心链表、双向链表。又可以分别循环链表和非循环链表。

  1. 单向链表。每个节点有一个指向下一个节点的指针next,最后一个节点next指向null。如图1所示
  2. 单向循环链表。单向循环链表和单向链表唯一不同的是最后一个节点的next指向head,形成一个“环”。如图2所示
  3. 双向链表。双向两边每个节点包含两个指针,prev指向前一个节点,next指向下一个节点,第一个节点的prev指向null,最后一个节点的next指向null。如图3所示
  4. 双向循环链表。双向循环链表与双向链表不同的是第一个节点的prev指针指向最后一个节点(tail),最后一个节点(tail)的next指针指向第一个节点(head),形成双向的“环”。如图4所示
    链表

LinkedListUML图

LinkedList

LinkedList 定义

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

LinkedList属性

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

内部类Node定义

1
2
3
4
5
6
7
8
9
10
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
3
4
5
6
public LinkedList() {}

public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

方法摘要

返回类型 方法名称 描述
boolean add(E e) 增加指定的元素
void add(int, index, E e) 在指定位置元素
boolean addAll(Collection<? extends E> c) 增加指定集合的所有元素
boolean addAll(int index, Collection<? extends E> c) 在指定位置开始增加集合的所有元素
void addFirst(E e) 在表头插入
void addLast(E e) 在表尾插入
void clear() 清空所有元素
Object clone() 克隆副本
boolean contains(Object o) 判断是否包含指定的元素。如存在返回true,否则返回false
Iterator descendingIterator() 返回一个从队尾到队头的反向迭代器
E get(int index) 返回指定位置的元素
E getFirst() 返回第一个元素(队头)
E getLast() 返回最后一个元素(队尾)
int indexOf(Object o) 返回列表中首次出现指定元素的位置,不存在返回-1
int lastIndexOf(Object o) 返回列表中最后一次出现指定元素的位置,不存在返回-1
boolean offer(E e) 同add
boolean offerFirst(E e) 同addFirst
boolean offerLast(E e) 同addLast
E peek() 和getFirst类似,唯一的区别是getFirst时first存在抛出NoSuchElementException,peek时first不存在返回null
E peekFirst()
E peekLast()
E poll() 表头出队(返回表头元素并删除表头)
E pollFirst() 同poll
E pollLast() 表尾出队(返回表尾元素并删除表尾)
E pop() 同removeFirst()
void push(E e) 同addFirst(E e)
E remove() 同removeFirst()
E remove(int index) 删除指定位置元素
boolean remove(Object o) 删除指定的元素
E removeFirst() 表头出队(返回表头元素并删除表头),表头为空抛出NoSuchElementException
E removeLast() 表尾出队(返回表尾元素并删除表尾).表尾为空抛出NoSuchElementException
E set(int index, E e) 用指定的元素替换列表中指定位置的元素
int size() 返回集合元素大小
Object[] toArray()
T [] toArray(T [])
void trimToSize() 容量调整为当前元素大小

核心源码(基于1.8)

增加元素

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
public boolean add(E e) {
// 连接到队尾
linkLast(e);
return true;
}
void linkLast(E e) {
// 列表原队尾节
final Node<E> l = last;
// 创建包含元素e的节点newNode
final Node<E> newNode = new Node<>(l, e, null);
// 队尾指向newNode
last = newNode;
// 如果列表原队尾节为空,则把对头节点也指向newNode。否则把原队尾节点的下一个节点指向newNode
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

/**
* 指定位置插入
*/
public void add(int index, E element) {
// 下标检查
checkPositionIndex(index);
if (index == size)
// 插入到队尾
linkLast(element);
else
// 队尾之前插入
linkBefore(element, node(index));
}
/**
* 查找index位置的节点
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// 如果 index < size/2 (size >> 1即一除以2取整)
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;
}
}
/**
* succ节点之前插入元素
*/
void linkBefore(E e, Node<E> succ) {
// 原index位置前一个节点pred
final Node<E> pred = succ.prev;
// 创建包含元素e的节点newNode
final Node<E> newNode = new Node<>(pred, e, succ);
// 修改succ.prev指向
succ.prev = newNode;
// 如果pred为空,即插入到队头。否则succ前一个节点的下一个节点(pred.next)指向newNode
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
/**
* 将集合中所有元素插入到列表
*/
public boolean addAll(Collection<? extends E> c) {
// 从队尾开始插入
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;
// index位置前节点pred及index位置前节
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;
}
// 如果队尾插入,last指向pred(即最后一个元素节点)
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}

size += numNew;
modCount++;
return true;
}
/**
* 队头插入
*/
public void addFirst(E e) {
linkFirst(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 void addLast(E e) {
linkLast(e);
}
public void push(E e) {
addFirst(e);
}
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}

获取元素

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
public E get(int index) {
// 下标检查
checkElementIndex(index);
// 迭代查找
return node(index).item;
}
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 element() {
return getFirst();
}
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;
}
public E pop() {
return removeFirst();
}
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);
}
/**
* 解开非空节点x
*/
E unlink(Node<E> x) {
// 取出节点元素
final E element = x.item;
// 取出next指针
final Node<E> next = x.next;
// 取出prev指针
final Node<E> prev = x.prev;
// 如果prev为空,即unlink节点是表头
if (prev == null) {
first = next;
} else {
// prev.next下移
prev.next = next;
// 置空
x.prev = null;
}
// 如果next为空,即unlink的是表尾节点
if (next == null) {
last = prev;
} else {
// next.prev前移
next.prev = prev;
x.next = null;
}
// 置空,帮助gc
x.item = null;
// 实际元素-1
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
29
30
31
32
33
34
35
public E remove() {
return removeFirst();
}
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 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);
}

查找

1
2
3
4
5
public E get(int index) {
// 下标检查
checkElementIndex(index);
return node(index).item;
}

更新

1
2
3
4
5
6
7
8
9
10
11
public E set(int index, E element) {
checkElementIndex(index);
// 查找节点
Node<E> x = node(index);
// 取出旧值
E oldVal = x.item;
// 修改值
x.item = element;
// 返回旧值
return oldVal;
}

总结

  1. 顺序插入ArrayList较快(不涉及扩容的情况下)。因为LinkedList需要new节点,ArrayList是基于数组的,直接赋值即可
  2. LinkedList是一个双向链表,不仅维护元素本身,还维护了前置和后继,内存消耗上大于ArrayList
  3. ArrayList遍历速度高于LinkedList
  4. 插入/删除:在队头/队尾插入/删除删除较快,在中间插入因为需要整个列表寻找,所以较慢(越往后插入/删除需要寻址次数越多)

本系列文章是为团队内部分享参考网络资料及个人理解整理而成

-------------本文结束感谢您的阅读-------------