源码阅读-LinkedList

Tips:

  1. 如果要在集合中使用自定义类,建议重写equals函数
  2. 如果集合内元素较多,使用结束后建议清空(GC)
  3. LinkedList所提供的原生函数无批处理,所以会有线程安全的假象,但是它并非线程安全,并且因为不想ArrayList提供批处理函数(函数内针对线程安全做了一定的处理),所以在使用LinkedList时需要格外注意
  4. 链表核心在于指针(即引用),可以先行了解这部分
  5. 本次未像ArrayList提供基础代码调用实现

继承实现关系图

LinkedList
蓝色实线为继承,色虚线为实现,红色为内部类

链表简单结构示意图

LinkedList_Node
此为LinkedList的节点结构与队列模拟展示,属于数据结构中的双向链表

参数解释

参数 释义
size 链表节点数目
first 链表头节点指针
last 链表尾节点指针

数据结构

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
// 创建空链表
public LinkedList() {
}

//根据集合创建链表
//实际是先创建空链表,再遍历集合加入链表
public LinkedList(Collection<? extends E> c) {
this();
addAll(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
public void addFirst(E e) {
linkFirst(e);
}

//@since 1.6
//个人认为就是为了修改方法名而存在的方法
//push和pop应该算是链表的标准操作
public void push(E e) {
addFirst(e);
}

private void linkFirst(E e) {
// 创建指针指向头指针指向地址
final Node<E> f = first;
//创建节点,该节点next指针使用刚刚创建的指针f
//即将新节点的后节点指向头结点
final Node<E> newNode = new Node<>(null, e, f);
//first指针指向刚创建的节点
first = newNode;

if (f == null)
//如果当前链表为空,则f将会指向null
//则新节点不仅是头结点也是尾节点
last = newNode;
else
//因为f指向的是之前的头节点,目前的第二节点
//因此需要将节点的prev指针指向现在的头结点,完成结构搭建
f.prev = newNode;
//节点数目+1
size++;
//修改次数+1
modCount++;
}
尾部增加节点
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
public void addLast(E e) {
linkLast(e);
}

void linkLast(E e) {
//创建指针指向尾指针指向地址
final Node<E> l = last;
//创建新节点,新节点的前指针指向尾指针(l)指向地址
//后指针指向null
final Node<E> newNode = new Node<>(l, e, null);
//链表尾指针指向新节点
last = newNode;

if (l == null)
//如果原链表为空,则新节点同时也是头结点
first = newNode;
else
//l原本指向尾节点,现在是倒数第二
//因此l指向的节点的后指针应指向新节点完成结构搭建
l.next = newNode;
//节点数目+1
size++;
//修改次数+1
modCount++;
}
增加一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean add(E e) {
//使用尾部添加方式
linkLast(e);
return true;
}

public boolean offer(E e) {
return add(e);
}

public boolean offerFirst(E e) {
addFirst(e);
return true;
}

public boolean offerLast(E e) {
addLast(e);
return true;
}

public void push(E e) {
addFirst(e);
}
指定位置添加一个节点
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
public void add(int index, E element) {
//索引位置校验
checkPositionIndex(index);

if (index == size)
//尾部追加方式
linkLast(element);
else
//指定index插入方式
linkBefore(element, node(index));
}

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;
//节点数目+1
size++;
//修改次数+1
modCount++;
}
指定位置通过集合添加节点
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
public boolean addAll(int index, Collection<? extends E> c) {
//检查索引位置是否合法[0,size]
checkPositionIndex(index);

//利用collection函数,将集合元素抽取为数组
Object[] a = c.toArray();

int numNew = a.length;
if (numNew == 0)
//如果集合为空,则直接返回
return false;

//声明前指针,后指针
Node<E> pred, succ;
if (index == size) {
//如果插入位置与数量size相等
//则是尾部追加
succ = null;
pred = last;
} else {
//将后指针指向指定位置节点
succ = node(index);
//将前指针指向指定位置节点的前一个节点
pred = succ.prev;
}

for (Object o : a) {
//使用pred作为前指针,创建只有前指针的节点
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
//前指针为空意味着链表为空,当前创建节点为链表头结点
//需要将首指针指向该节点
first = newNode;
else
//链表不为空,则需要将前面的节点的后指针指向创建节点
pred.next = newNode;
//pred指针后移
pred = newNode;
}

//succ指向原本位置在index的节点
if (succ == null) {
//succ为空,则至少说明是尾部追加
//需要将尾指针指向该节点
last = pred;
} else {
//将创建的最后一个节点的后指针指向原本位于index的节点
//将原节点的前指针指向创建的最后一个节点
//完成最后的连接构建
pred.next = succ;
succ.prev = pred;
}

//刷新链表大小
size += numNew;
//修改次数+1
modCount++;
return true;
}

//根据索引找到节点
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;
}
}
尾部添加集合
1
2
3
4
public boolean addAll(Collection<? extends E> c) {
//直接传入size
return addAll(size, 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 removeFirst() {
final Node<E> f = first;
if (f == null)
//防止链表为空
throw new NoSuchElementException();
return unlinkFirst(f);
}

//该方法与上一个方法的区别就是健壮性
//当链表为空时,不会抛出异常,而是null
//@since 1.5
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

//@since 1.6
//只改了 一个方法名称,之所以保留上一个方法
//应该是出于兼容问题考虑,防止有的用户升级了jdk版本
//但是没有完全的修改好已经使用的方法
//也怀疑是方便推广
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

//@since 1.6
//同考虑为只是修改方法名,或者说降低使用难度(针对英语为母语)
public E pop() {
return removeFirst();
}

//个人认为该方法只是为了重载,无明显含义
public E remove() {
return removeFirst();
}

private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//保留下头结点内部value
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;
//链表节点数目-1
size--;
//修改次数+1
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
36
37
38
39
public E removeLast() {
final Node<E> l = last;
if (l == null)
//防止链表为空
throw new NoSuchElementException();
return unlinkLast(l);
}

//@since 1.6
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}

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;
//刷新链表大小-1
size--;
//修改次数+1
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
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
//@since 1.6
//来自语言的满满恶意
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}

public boolean remove(Object o) {
if (o == null) {
//区分null是因为空无法使用equals函数比较
//从头结点开始,正向遍历查找
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) {
//因为使用的是传入对象的equals方法进行对比,因此
//使用自定义对象的时候,建议重写equals方法
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

//@since 1.6
//来自语言的满满恶意
//此方法有些许不同,它是删除最后一个出现的,即反向查找
public boolean removeLastOccurrence(Object o) {
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;
}

E unlink(Node<E> x) {
// assert x != null;
//将待移除节点值域、指针保留,一份副本
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;
//节点数目-1
size--;
//修改次数+1
modCount++;
返回被移除节点保存内容
return element;
}
删除指定位置节点
1
2
3
4
5
public E remove(int index) {
//校验index合法
checkElementIndex(index);
return unlink(node(index));
}
节点清空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
//理论上不用清除每一个节点的指针连接,但是这能帮助减少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;
//修改次数+1
modCount++;
}

修改节点

修改指定索引节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//该方法虽然修改了节点
//但是并没有修改modCount
public E set(int index, E element) {
//校验index合法
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
//返回的是节点的值
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}

//@since 1.5
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}

//@since 1.5
public E element() {
return getFirst();
}

//@since 1.6
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
获取尾节点
1
2
3
4
5
6
7
//返回节点值
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
判断是否含有节点
1
2
3
4
//通过值判断
public boolean contains(Object o) {
return indexOf(o) != -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
//正向,返回第一次出现的索引
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;
}

//反向,返回第一次出现的索引
//因为是反向查找,所以结果对于正向来说是最后一次出现
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;
}
查询指定索引节点
1
2
3
4
5
//返回值
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}