Java源码阅读之LinkedList - JDK1.8

文章目录
  1. 1. 前言
  2. 2. 基本介绍
    1. 2.1. 静态常量
    2. 2.2. 成员变量
    3. 2.3. 构造函数
  3. 3. 功能方法
  4. 4. remove
  5. 5. 最后

阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方,欢迎指正~
转载请注明出处https://blog.lzoro.com

前言

前文基于缓冲数组的ArrayList已经分析过,那么同样作为List实现的LinkedList又有什么不一样呢?

在阅读LinkedList源码之前,开头处先简单总结一下两者的区别

ArrayList

  • 基于缓冲数组进行数据存储
  • 查询/修改方便,因为基于下标容易定位数据
  • 插入/删除不方便,需要移动数据

LinkedList

  • 基于双向链表进行数据存储
  • 查询/修改不方便,因为要移动指针
  • 插入/删除方便,因为基于指针,不需要移动数据

带着这些概念,再次打开你的IDE,挽起袖子,开撸代码,加上注释,总计1262行代码,比ArrayList还少呢。

基本介绍

静态常量

嗯,没有,你没看错,LinkedList内部没有含业务属性的静态常量。

成员变量

工欲善其事,必先利其器。

虽然没什么太大关系,但为了提供逼格还是来了个引用。

要透彻理解整个LinkedList,那首先得先了解下它的内部提供了哪些成员变量,分别是做什么用的,这样有助于我们在看功能方法时提高效率。

其实,LinkedList内部定义的成员变量也少,但是没办法,谁让我为了提升篇幅,多说两句了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 大小
*/
transient int size = 0;

/**
* 首节点
* 恒定的: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;

/**
* 尾节点
* 恒定的: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;

可以看出来首节点/尾节点都是Node<E>的实例,那么Node<E>是何方神圣呢

它是一个私有的静态内部类,内部定义了当前元素和前置/后继指针,和一个构造函数,是整个双向链表的基础。

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

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 构造一个空的List
*/
public LinkedList() {
}

/**
* 根据给定的集合构造一个List
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
//调用上面的构造函数
this();
//添加集合到List中
addAll(c);
}

简洁明了。你应该也注意到了第二个构造函数中的addAll方法,看名字也知道是将集合c中的所有元素添加到LinkedList中。所以不能错过,往下看

可以看到,addAll(Collection<? extends E> c)是调用addAll(int index, Collection<? extends E> c)的,而这两个方法都是public的,第一个方法是在链表尾部添加指定的集合,而第二个方法比第一个方法多了一个参数,用来指定在某个位置添加指定集合。

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
/**
* 将指定集合的所有元素添加都list尾部
*
* 如果操作过程中指定的集合被修改,则此操作的行为未定义。
* (注意,如果指定的集合是该列表,并且它不是空的,则会发生这种情况。)
* 其实就是线程不安全。
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}

/**
*
* 从指定位置插入指定集合的所有元素
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
//检查指针是否合法
checkPositionIndex(index);

//集合转数组
Object[] a = c.toArray();
//集合长度
int numNew = a.length;
//如果是空集合,则返回false
if (numNew == 0)
return false;
//定义前置/继任节点
Node<E> pred, succ;
//如果指定的位置是尾部(index==size)
//无论当前链表是不是空的,只要index==size,就是往尾部插入元素
if (index == size) {
//继任节点为null
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;
}
//如果没有继任节点
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
//修改大小
size += numNew;
//修改操作计数
modCount++;
return true;
}

这里的addAll添加一个集合的元素操作,整体逻辑还是比较清晰的,包含了指定集合c的非空判断,插入位置判断,断开链表,修改引用,后续判断和修改计数。

功能方法

了解了一些基础之后,那就该上大菜了。

接下来阅读,平时我们用的比较频繁的一些功能方法的源码。

还是老生常谈,对于这种集合框架来说,常用方法无外乎增/删/改/查。

另外,由于LinkedList不仅实现了List接口,还实现了Deque双端队列接口,所以也提供了队列相关方法。

add

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
/**
* 尾部添加元素,返回true
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//调用linkLast,后续分析
linkLast(e);
return true;
}

/**
* 指定位置添加元素
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
//检查指针
checkPositionIndex(index);
//判断是不是从尾部添加
if (index == size)
linkLast(element);
else
//不是尾部添加的,调用linkBefore,后续分析
linkBefore(element, node(index));
}

/**
* 头部插入
*
* @param e the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}

/**
* 尾部插入
*
* @param e the element to add
*/
public void addLast(E e) {
linkLast(e);
}

方法都很简单,没有什么操作逻辑,可以看出来,是linkLast/linkFirst/linkBefore在提供实际实现。

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
/**
* 作为首节点
*/
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++;
}


/**
* 作为尾节点
*/
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++;
}

/**
* 在非null继任节点前插入
*/
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++;
}

看完上面内容,大概也就能了解为什么LinkedList适合插入/删除节点了,因为插入操作对于LinkedList来说,不需要移动数据,只需要在指定位置修改指针引用即可,即,断开->插入->修改引用。

移除其实也是同样的道理,即,断开->移除->修改引用。

remove

移除分为以下几种

  • 根据下标移除
  • 根据对象移除
  • 移除头部(实现Deque接口的方法)
  • 移除尾部((实现Deque接口的方法)
  • 移除首个匹配的对象(实现Deque接口的方法)
  • 移除最后一个匹配的对象(实现Deque接口的方法)
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
/**
* 根据下标移除元素,并移动相关指针
*
* @param index 要移除元素的下标
* @return 返回删除元素的前一个元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//下标合法性判断
checkElementIndex(index);
//调用node进行节点查找之后调用unlink进行移除
//后续分析这两个方法
return unlink(node(index));
}

/**
* 如果存在的话从list中移除第一个匹配的元素
* 如果不存在,则list不改变
*
* 更正式点说,是移除在低位匹配到的元素
* 如下所示
* <tt>(o==null?get(i)==null:o.equals(get(i)))</tt>
* (假如元素存在).
* Returns {@code true} 如果列表存在元素 (等价理解,该链表被改变).
*
* @param o 要移除的元素
* @return {@code true} 如果存在要移除的元素
*/
public boolean remove(Object o) {
//先判断要移除的元素是不是null
if (o == null) {
//从首节点遍历查找
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
//匹配到null,在调用unlink移除(之后分析这个方法)
unlink(x);
return true;
}
}
//要移除的元素不是 null
} else {
//仍然是遍历,不过比较方法换成equals
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}


/**
* 移除并返回首个元素
*
* @return 返回list首元素
* @throws NoSuchElementException list为空时,抛异常
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
//调用unlinkFirst,后面和unlink一起分析
return unlinkFirst(f);
}


/**
* 移除并返回尾部元素
*
* @return 返回list尾元素
* @throws NoSuchElementException list为空时,抛异常
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
////调用unlinkLast,后面和unlink一起分析
return unlinkLast(l);
}

/**
* 从list头部->尾部进行遍历,如果存在指定元素的话,则移除第一个匹配的元素,如果不存在,则list不改变
*
* @param o 要移除的元素
* @return {@code true} 如果存在的话,返回true
* @since 1.6
*/
public boolean removeFirstOccurrence(Object o) {
//直接调用remove(o),因为remove(o)就是从头部遍历并移除第一个匹配的元素
return remove(o);
}

/**
* 从list尾部->头部进行遍历,如果存在指定元素的话,则移除第一个匹配的元素,如果不存在,则list不改变
*
* @param o 要移除的元素
* @return {@code true} 如果存在的话,返回true
* @since 1.6
*/
public boolean removeLastOccurrence(Object o) {
//判断o是不是null,如果是null,则用==比较
if (o == null) {
//从尾部遍历
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
//移除
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

//上面这个方法,通过条件分支,循环在两个分支里都有,看似可以抽离循环,然后再循环内部判断o==null来精简代码。

//但是实际上,把o==null抽离出来循环之外,虽然多写了些代码,但是不用在每次循环中做两次判断,可以提供效率。

//如果有类似的场景,我们也可以参考这种写法。

好了,看完上面的remove类方法,遗留了几个实际实现nodeunlinkunlinkFirstunlinkLast未阅读,下面继续

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
/**
* 返回非指定位置的非null节点
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//判断下标在list的上游/下游
//如果是上游的话,从头部进行查找
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;
}
}


/**
* 移除非null节点x
*/
E unlink(Node<E> x) {
// assert x != null;
//取出元素待返回
final E element = x.item;
//取出x的前/后节点
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//如果前置节点不存在,则证明x是首节点
if (prev == null) {
//首节点指向x的后置节点
first = next;
} else {
//如果x不是首节点
//则将x的前置节点与后置节点相连
prev.next = next;
//x与前置节点断开
x.prev = null;
}

//如果x的后置节点不存在,则证明x是尾节点
if (next == null) {
//尾节点指向x的前置节点
last = prev;
} else {
//如果不是尾节点
//则将x的尾首节点相连
//修改引用
next.prev = prev;
//x与后置节点断开
x.next = null;
}
//x的元素置null
x.item = null;
//size - 1
size--;
//操作计数 + 1
modCount++;
return element;
}


/**
* 移除非null的f首节点.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//老规矩,取出f节点元素,待返回
final E element = f.item;
//取出f的后置节点
final Node<E> next = f.next;
//下面两个置null帮助垃圾收集器进行GC
f.item = null;
f.next = null; // help GC
//首节点指向f的后置节点
first = next;
//如果后置节点不存在,证明list只有一个节点
if (next == null)
//置null
last = null;
else
//list不只一个节点
//后置节点变成首节点了,所以首节点的prev置null
next.prev = null;
//常规操作
size--;
modCount++;
return element;
}


/**
* 移除非null的l尾节点
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//取出元素待返回
final E element = l.item;
//取出l的前置节点
final Node<E> prev = l.prev;
//两个置null帮助垃圾收集器GC
l.item = null;
l.prev = null; // help GC
//尾节点指向l的前置节点
last = prev;
//如果前置节点尾null,证明list只有一个节点
if (prev == null)
//首节点置null,此时list为空
first = null;
else
//list不只一个节点
//前置节点变成尾节点了,所以尾节点的后置为null
prev.next = null;
//常规操作
size--;
modCount++;
return element;
}

set

设置/修改元素操作,需要提供下标和对应的元素,逻辑比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 提供下标和元素来替换指定位置的元素
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
//下标合法性判断
checkElementIndex(index);
//获取指定节点(在remove章节已经分析过该方法)
Node<E> x = node(index);
//进行替换
E oldVal = x.item;
x.item = element;
return oldVal;
}

get

LinkedList的查找元素方式跟ArrayList有点不同,由于它是双端链表形式存储数据,所以额外提供了getFirstgetLast,方法实现都很简单,下面看一下这三个方法的实现

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
/**
* 返回指定位置的元素
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
//这里其实也是调用node(index)方法进行定位
checkElementIndex(index);
return node(index).item;
}

/**
* 返回list的首元素
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}

/**
* 返回list的尾元素
*
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}

contains

判断list是否包含指定元素,跟ArrayList一样,通过查找元素的下标后判断下标是否存在,来判断元素是否存在,不一样的是元素的查找方法。

LinkedList是双端链表实现,所以查找方法时从首节点进行遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean contains(Object o) {
return indexOf(o) != -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;
}

其他方法

其他还有一些方法,如clear以及Deque接口中定义的方法实现如offer等,避免篇幅过长,这里不一一分析,有兴趣的可自行阅读源码,实现逻辑都相对比较简单。

  • clear
  • offer
  • peek

只要了解了双端链表的基本原理,和常规操作,基本上内部的方法实现都能掌握得差不多,所以。

我犯懒了,就差不多分析到这里。

最后

惯例求点赞~~

3Q~

分享到