Java集合之LinkedList源码解析

LinkedList

  • 在Java.util包下
  • 继承自AbstractSequentialList
  • 实现 List 接口,能对它进行队列操作。
  • 实现 Deque 接口,即能将LinkedList当作双端队列使用。
  • 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
  • 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
  • 允许包含null值
  • 迭代器可以快速报错
  • 非线程安全的,如果在多线程中使用(修改),需要在外部作同步处理。

LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列,它是基于双向链表实现的。内部有三个变量,size表示链表中元素的个数, first指向链表头部,last指向链表尾部。 结构图如下图所示

LinkedList.png

下面是LinkedList中Node节点的定义,Node类是LinkedList的静态内部类。

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

构造方法(Construction method)

LinkedList提供了两种种方式的构造器,构造一个空列表、以及构造一个包含指定collection的元素的列表,
这些元素按照该collection的迭代器返回的顺序排列的。

1
2
3
4
5
6
7
public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
this();
addAll(c); // 调用addAll方法,构建一个包含指定集合c的列表
}

添加元素

因为LinkedList即实现了List接口,又实现了Deque接口,所以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
//添加元素作为第一个元素
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; //如果之前首节点为空(size==0),那么尾节点就是首节点
else
f.prev = newNode; //如果之前首节点不为空,之前的首节点的前一个节点为当前首节点
size++; //长度+1
modCount++; //修改次数+1
}
//使用对应参数作为尾节点
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; //如果之前尾节点为空(size==0),首节点即尾节点
else
l.next = newNode; //如果之前尾节点不为空,之前的尾节点的后一个就是当前的尾节点
size++;
modCount++;
}

//在非空节点succ之前插入元素E。
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;//如果前一个节点为null,新的节点就是首节点
else
pred.next = newNode;//如果存在前节点,那么前节点的向后指向新节点
size++;
modCount++;
}

//添加指定集合的元素到列表,默认从最后开始添加
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);//size表示最后一个位置
}

/*
从指定位置(而不是下标!下标即索引从0开始,位置可以看做从1开始,其实也是0)后面添加指定集合的元素到列表中,只要有至少一次添加就会返回true
index换成position应该会更好理解,所以也就是从索引为index(position)的元素的前面索引为index-1的后面添加!
当然位置可以为0啊,为0的时候就是从位置0(虽然它不存在)后面开始添加嘛,所以理所当然就是添加到第一个位置(位置1的前面)的前面

比如列表:0 1 2 3,如果此处index=4(实际索引为3),就是在元素3后面添加;如果index=3(实际索引为2),就在元素2后面添加。
*/
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); //检查索引是否正确(0<=index<=size)
Object[] a = c.toArray(); //得到元素数组
int numNew = a.length; //得到元素个数
if (numNew == 0) //若没有元素要添加,直接返回false
return false;
Node<E> pred, succ;
if (index == size) { //如果是在末尾开始添加,当前节点后一个节点初始化为null,前一个节点为尾节点
succ = null; //这里可以看做node(index),不过index=size了(index最大只能是size-1),所以这里的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; //若当前节点为null,则新加的节点为首节点
else
pred.next = newNode;//如果存在前节点,前节点会向后指向新加的节点
pred = newNode; //新加的节点成为前一个节点
}
if (succ == null) {
//pred.next = null //加上这句也可以更好的理解
last = pred; //如果是从最后开始添加的,则最后添加的节点成为尾节点
} else {
pred.next = succ; //如果不是从最后开始添加的,则最后添加的节点向后指向之前得到的后续第一个节点
succ.prev = pred; //当前,后续的第一个节点也应改为向前指向最后一个添加的节点
}
size += numNew;
modCount++;
return true;
}

//将指定的元素(E element)插入到列表的指定位置(index)
public void add(int index, E element) {
checkPositionIndex(index); //index >= 0 && index <= size

if (index == size)
linkLast(element); //尾插入
else
linkBefore(element, node(index)); //中间插入
}

linkBefore的添加步骤:

  1. 创建newNode节点,将newNode的后继指针指向succ,前驱指针指向pred
  2. 将succ的前驱指针指向newNode
  3. 根据pred是否为null,进行不同操作。
  • 如果pred为null,说明该节点插入在头节点之前,要重置first头节点
  • 如果pred不为null,那么直接将pred的后继指针指向newNode即可

addAll的添加步骤:

  1. 检查index索引范围
  2. 得到集合数据
  3. 得到插入位置的前驱和后继节点
  4. 遍历数据,将数据插入到指定位置

删除元素

同样的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
// 删除首节点并返回删除前首节点的值,内部使用 (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) //如果不存在下一个节点,则首尾都为null
last = null;
else
next.prev = null; //如果存在下一个节点,那它的前指针为null
size--;
modCount++;
return element;
}

// 删除尾节点,并返回尾节点的元素 (assert l == last && l != null)
private E unlinkLast(Node<E> l) {
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; //如果前一个节点不存在,则首尾都为null
else
prev.next = null;//如果前一个节点存在,先后指向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; //help GC
}
if (next == null) {
last = prev; //如果后一个节点为空(如当前节点为尾节点),当前节点前一个成为新的尾节点
} else {
next.prev = prev;//如果后一个节点不为空,后一个节点向前指向当前的前一个节点
x.next = null; //help GC
}
x.item = null; //help GC
size--;
modCount++;
return element;
}

//删除第一个元素并返回删除的元素
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
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static final long serialVersionUID = 876323262645176354L;

//序列化:将linkedList的“大小,所有的元素值”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
s.defaultWriteObject();
s.writeInt(size);

for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}

//反序列化:先将LinkedList的“大小”读出,然后将“所有的元素值”读出
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
int size = s.readInt();

for (int i = 0; i < size; i++)
linkLast((E)s.readObject()); //以尾插入的方式
}

队列操作

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
//提供普通队列和双向队列的功能,当然,也可以实现栈,FIFO,FILO
//出队(从前端),获得第一个元素,不存在会返回null,不会删除元素(节点)
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//出队(从前端),不删除元素,若为null会抛出异常而不是返回null
public E element() {
return getFirst();
}
//出队(从前端),如果不存在会返回null,存在的话会返回值并移除这个元素(节点)
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//出队(从前端),如果不存在会抛出异常而不是返回null,存在的话会返回值并移除这个元素(节点)
public E remove() {
return removeFirst();
}
//入队(从后端),始终返回true
public boolean offer(E e) {
return add(e);
}
//入队(从前端),始终返回true
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//入队(从后端),始终返回true
public boolean offerLast(E e) {
addLast(e);//linkLast(e)
return true;
}
//出队(从前端),获得第一个元素,不存在会返回null,不会删除元素(节点)
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//出队(从后端),获得最后一个元素,不存在会返回null,不会删除元素(节点)
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
//出队(从前端),获得第一个元素,不存在会返回null,会删除元素(节点)
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//出队(从后端),获得最后一个元素,不存在会返回null,会删除元素(节点)
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
//入栈,从前面添加
public void push(E e) {
addFirst(e);
}
//出栈,返回栈顶元素,从前面移除(会删除)
public E pop() {
return removeFirst();
}

迭代器

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
//返回迭代器
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
//迭代器
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}

public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}

private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;//保存当前modCount,确保fail-fast机制

ListItr(int index) {
next = (index == size) ? null : node(index);//得到当前索引指向的next节点
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;
}

//获取前一个节点,将next节点向前移
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();

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(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
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();
}

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

在ListIterator的构造器中,得到了当前位置的节点,就是变量next。next()方法返回当前节点的值并将next指向其后继节点,previous()方法返回当前节点的前一个节点的值并将next节点指向其前驱节点。

由于Node是一个双向节点,所以这用了一个节点就可以实现从前向后迭代和从后向前迭代。另外在ListIterator初始时,exceptedModCount保存了当前的modCount,如果在迭代期间,有操作改变了链表的底层结构,那么再操作迭代器的方法时将会抛出ConcurrentModificationException。

fail-fast

fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。例如:当某一个线程A通过iterator去遍历某集合的过程中,若该集合的内容被其他线程所改变了;那么线程A访问集合时,就会抛出ConcurrentModificationException异常,产生fail-fast事件。

快速失败(fail—fast)

在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出Concurrent Modification Exception。

原理:迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出异常,终止遍历。

注意:这里异常的抛出条件是检测到 modCount!=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值,则异常不会抛出。因此,不能依赖于这个异常是否抛出而进行并发操作的编程,这个异常只建议用于检测并发修改的bug。

场景:java.util包下的集合类都是快速失败的,不能在多线程下发生并发修改(迭代过程中被修改)。

安全失败(fail—safe)

采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先复制原有集合内容,在拷贝的集合上进行遍历。

原理:由于迭代时是对原集合的拷贝进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会触发Concurrent Modification Exception。

缺点:基于拷贝内容的优点是避免了Concurrent Modification Exception,但同样地,迭代器并不能访问到修改后的内容,即:迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的。

场景:java.util.concurrent包下的容器都是安全失败,可以在多线程下并发使用,并发修改。

其他方法

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
//获取第一个元素
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;
}

//检查是否包含某个元素,返回bool
public boolean contains(Object o) {
return indexOf(o) != -1;//返回指定元素的索引位置,不存在就返回-1,然后比较返回bool值
}
//返回列表长度
public int size() {
return size;
}

//清空表
public void clear() { // help GC
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++;
}
//获取指定索引的节点的值
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//修改指定索引的值并返回之前的值
public E set(int index, E element) {
checkElementIndex(index); // 检查下标是否合法
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}

//获取指定位置的节点
Node<E> node(int index) {
if (index < (size >> 1)) {//如果位置索引小于列表长度的一半(或一半减一),从前面开始遍历;
Node<E> x = first;//index==0时不会循环,直接返回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;
}
}

//获取指定元素从first开始的索引位置,不存在就返回-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;
}
//获取指定元素从first开始最后出现的索引,不存在就返回-1
//但实际查找是从last开始的
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;
}

//返回此 LinkedList实例的浅拷贝
public Object clone() {
LinkedList<E> clone = superClone();

clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;

for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);

return clone;
}

//返回一个包含LinkedList中所有元素值的数组
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;
}

//如果给定的参数数组长度足够,则将ArrayList中所有元素按序存放于参数数组中,并返回
//如果给定的参数数组长度小于LinkedList的长度,则返回一个新分配的、长度等于LinkedList长度的、包含LinkedList中所有元素的新数组
@SuppressWarnings("unchecked")
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;
}