Java -- 基于JDK1.8的LinkedList源码分析
1，上周末我们一起分析了ArrayList的源码并进行了一些总结，因为最近在看Collection这一块的东西，下面的图也是大致的总结了Collection里面重要的接口和类，如果没有意外的话后面基本上每一个都会和大家一起学习学习，所以今天也就和大家一起来看看LinkedList吧！
哦，不对，放错图了，是下面的图，嘿嘿嘿。。。
2，记得首次接触LinkedList还是在大学Java的时候，当时说起LinkedList的特性和应用场景：LinkedList基于双向链表适用于增删频繁且查询不频繁的场景，线程不安全的且适用于单线程（这点和ArrayList很像）。然后还记得一个很深刻的是可以用LinkedList来实现栈和队列，那让我们一起看一看源码到底是怎么来实现这些特点的
2.1 构造函数
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
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
{
transient int size = 0;
transient Node first;
transient Node last;
public LinkedList() {
}
public LinkedList(Collection c) {
this();
addAll(c);
}
public boolean addAll(Collection c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node 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 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;
}
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Node node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
}
首先我们知道常见的构造是LinkedList()和LinkedList(Collection c)两种，然后再来看看我们继承的类和实现的接口
1
2
3
4
5
LinkedList 集成AbstractSequentialList抽象类，内部使用listIterator迭代器来实现重要的方法
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
可以看到，相对于ArrayList，LinkedList多实现了Deque接口而少实现了RandomAccess接口，且LinkedList继承的是AbstractSequentialList类，而ArrayList继承的是AbstractList类。那么我们现在有一个疑问，这些多实现或少实现的接口和类会对我们LinkedList的特点产生影响吗？这里我们先将这个疑问放在心里，我们先走正常的流程，先把LinkedList的源码看完（主要是要解释这些东西看Deque的源码，还要去看Collections里面的逻辑，我怕扯远了）
第5-7行：定义记录元素数量size，因为我们之前说过LinkedList是个双向链表，所以这里定义了链表链表头节点first和链表尾节点last
第60-70行：定义一个节点Node类，next表示此节点的后置节点，prev表示侧节点的前置节点，element表示元素值
第22行：检查当前的下标是否越界，因为是在构造函数中所以我们这边的index为0，且size也为0
第24-29行：将集合c转化为数组a，并获取集合的长度；定义节点pred、succ，pred用来记录前置节点，succ用来记录后置节点
第70-89行：node()方法是获取LinkedList中第index个元素，且根据index处于前半段还是后半段 进行一个折半，以提升查询效率
第30-36行：如果index==size，则将元素追加到集合的尾部，pred = last将前置节点pred指向之前结合的尾节点，如果index！=size表明是插入集合，通过node(index)获取当前要插入index位置的节点，且pred = succ.prev表示将前置节点指向于当前要插入节点位置的前置节点
第38-46行：链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作，第40行以前置节点 和 元素值e，构建new一个新节点；第41行如果前置节点是空，说明是头结点，且将成员变量first指向当前节点，如果不是头节点，则将上一个节点的尾节点指向当前新建的节点；第45行将当前的节点为前置节点了，为下次添加节点做准备。这些走完基本上我们的新节点也都创建出来了，可能这块代码有点绕，大家多看看
第48-53行：循环结束后，判断如果后置节点是null， 说明此时是在队尾添加的，设置一下队列尾节点last，如果不是在队尾，则更新之前插入位置节点的前节点和当前要插入节点的尾节点
第55-56行：修改当前集合数量、修改modCount记录值
ok,虽然说是分析的构造函数的源码，但是把node(int index)、addAll(int index, Collection c)方法也都看了，所以来小结一下：链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作；通过下标index来获取节点Node是采用的折半法来提升效率的
2.2 增加元素
常见的方法有以下三种
1
2
3
linkedList.add(E e)
linkedList.add(int index, E element)
linkedList.addAll(Collection 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
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = 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));
}
void linkBefore(E e, Node succ) {
// assert succ != null;
final Node pred = succ.prev;
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
public boolean addAll(Collection c) {
return addAll(size, c);
}
第2、6-16行：创建一个newNode它的prev指向之前队尾节点last，并记录元素值e，之前的队尾节点last的next指向当前节点，size自增，modcount自增
第18-20，27-38行：首先去检查下标是否越界，然后判断如果加入的位置刚好位于队尾就和我们add（E element）的逻辑一样了，如果不是则需要通过 node(index)函数定位出当前位于index下标的node，再通过linkBefore()函数创建出newNode将其插入到原先index位置
第40-42行：就是我们在构造函数中看过的批量加入元素的方法
OK，添加元素也很简单，如果是在队尾进行添加的话只需要创建一个新Node将其前置节点指向之前的last，如果是在队中添加节点，首选拆散原先的index-1、index、index+1之间的联系，新建节点插入进去即可。
2.3 删除元素
常见方法有以下这几个方法
1
2
3
linkedList.remove(int index)
linkedList.remove(Object o)
linkedList.remove(Collection 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
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
unlink(Node x) {
// assert x != null;
final E element = x.item;
final Node next = x.next;
final Node 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;
}
public boolean remove(Object o) {
if (o == null) {
for (Node x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
public boolean removeAll(Collection c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
第1-4，6-30行：首先根据index通过方法值node(index)来确定出集合中的下标是index的node，咋们主要看unlink()方法，代码感觉很多，其实只是将当前要删除的节点node的头结点的尾节点指向node的尾节点、将node的尾结点的头节点指向node的头节点，可能有点绕（哈哈），看一下代码基本上就可以理解了，然后将下标为index的node置空，供GC回收
第32-49行：首先判断一下当前要删除的元素o是否为空，然后进行for循环定位出当前元素值等于o的节点node，然后再走的逻辑就是上面我们看到过的unlink()方法，也很简单，比remove(int index) 多了一步
第51-62行：这一块因为涉及到迭代器Iterator，而我们LinkedList使用的是ListItr，这个后面我们将迭代器的时候一起讲，不过大致的逻辑是都可以看懂的，和我们的ArrayList的迭代器方法的含义一样的，可以先那样理解
ok，小结一下， 按下标删，也是先根据index找到Node，然后去链表上unlink掉这个Node。 按元素删，会先去遍历链表寻找是否有该Node，考虑到允许null值，所以会遍历两遍，然后再去unlink它。
2.5 修改元素
1
2
3
4
5
6
7
public E set(int index, E element) {
checkElementIndex(index);
Node x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
只有这一种方法，首先检查下标是否越界，然后根据下标获取当前Node，然后修改节点中元素值item，超级简单
2.6 查找元素
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
public E get(int index) {
checkElementIndex(index);//判断是否越界 [0,size)
return node(index).item; //调用node()方法 取出 Node节点，
}
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
获取元素的源码也很简单，主要是通过node(index)方法获取节点，然后获取元素值，indexOf和lastIndexOf方法的区别在于一个是从头向尾开始遍历，一个是从尾向头开始遍历
2.7 迭代器
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
public Iterator iterator() {
return listIterator();
}
public ListIterator listIterator() {
return listIterator(0);
}
public ListIterator listIterator(final int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
private class ListItr extends Itr implements ListIterator {
ListItr(int index) {
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public E previous() {
checkForComodification();
try {
int i = cursor - 1;
E previous = get(i);
lastRet = cursor = i;
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
AbstractList.this.add(i, e);
lastRet = -1;
cursor = i + 1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
可以看到，其实最后使用的迭代器是使用的ListIterator类，且集成自Itr，而Itr类就是我们昨天ArrayList内部使用的类，hasNext()方法和我们之前的一样，判断不等于size大小，然后next()获取元素主要也是E next = get(i);这行代码，这样就又走到我们之前的获取元素的源码当中，获得元素值。
OK，这样我们上面的基本方法都看完了，再来看看我们上面遗留的问题，首先来看Deque接口有什么作用，我们来一起看看
1
2
3
4
Deque 是 Double ended queue (双端队列) 的缩写,读音和 deck 一样，蛋壳。
Deque 继承自 Queue,直接实现了它的有 LinkedList, ArayDeque, ConcurrentLinkedDeque 等。
Deque 支持容量受限的双端队列，也支持大小不固定的。一般双端队列大小不确定。
Deque 接口定义了一些从头部和尾部访问元素的方法。比如分别在头部、尾部进行插入、删除、获取元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Deque extends Queue {
void addFirst(E e);//插入头部，异常会报错
boolean offerFirst(E e);//插入头部，异常不报错
E getFirst();//获取头部，异常会报错
E peekFirst();//获取头部，异常不报错
E removeFirst();//移除头部，异常会报错
E pollFirst();//移除头部，异常不报错
void addLast(E e);//插入尾部，异常会报错
boolean offerLast(E e);//插入尾部，异常不报错
E getLast();//获取尾部，异常会报错
E peekLast();//获取尾部，异常不报错
E removeLast();//移除尾部，异常会报错
E pollLast();//移除尾部，异常不报错
}
Deque也就是一个接口，上面是接口里面的方法，然后了解Deque就必须了解Queue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public interface Queue extends Collection {
//往队列插入元素，如果出现异常会抛出异常
boolean add(E e);
//往队列插入元素，如果出现异常则返回false
boolean of
