0%

LinkedList详解

LinkedList详解

LinkedList是List接口的一个主要的实现类之一。以java8为例来了解一下LinkedList的源码实现

继承关系

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

继承了AbstractSequentialList,实现了List接口、Deque接口、Cloneable接口、Serializable接口

关键变量

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
/**
* 链表的长度
*/
transient int size = 0;

/**
* 头节点
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;

/**
* 尾结点
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;

// 这里用到了一个内部类Node,看到Node的结构就知道是一个双向链表了,保存了前驱节点和后继节点
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
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
// 无参默认构造器
public LinkedList() {
}

/**
* 传入一个集合作为参数
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

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;
// 前置节点和后置节点
Node<E> pred, succ;
// index == size时表示是从链表尾部添加元素,所以前置节点为当前链表的尾结点
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);
// 前置节点为null,表示这是头节点
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// succ == null,说明是从尾部添加的,将最后一个节点赋给尾结点
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}

size += numNew;
modCount++;
return true;
}

// 获取index位置的节点
Node<E> node(int index) {
// assert isElementIndex(index);
// index小于链表长度的一半,从链表头部开始遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // index不小于链表长度的一半,从链表尾部开始遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

add方法

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
// 逻辑比较简单,与上边addAll类似,一通插
public void add(int index, E element) {
checkPositionIndex(index);
// index == size表示在链表尾部添加
if (index == size)
linkLast(element);
else // 否则在中间插入 先找到index所在位置的节点
linkBefore(element, node(index));
}

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

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

remove方法

LinkedList的remove方法比较

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
public E remove(int index) {
// 检测该索引位置是否符合要求 index >= 0 && index < size
checkElementIndex(index);
return unlink(node(index));
}

// 找到当前索引位置的节点
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;
}
}

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;
// 前驱节点为null,表示为头节点,头节点指向后继节点即可
if (prev == null) {
first = next;
} else {
// 前驱节点的后继节点指向该元素的后继节点
prev.next = next;
x.prev = null;
}
// 后继节点为null,表示为尾节点,尾节点指向前驱节点即可
if (next == null) {
last = prev;
} else {
// 后继节点的前驱节点指向该元素的前驱节点
next.prev = prev;
x.next = null;
}

x.item = null;
size--;
modCount++;
return element;
}

迭代器

LinkedList使用的迭代器是其父类AbstractSequentialList中的iterator方法

1
2
3
4
5
6
7
8
9
10
// AbstractSequentialList类方法
public Iterator<E> iterator() {
return listIterator();
}

// LinkedList类方法
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
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
//  与ArrayList的迭代器不同的是,ArrayList的迭代器实现的是Iterator接口 而LinkedList为ListIterator接口,相当于ArrayList的listIterator()方法
// Iterator只能向前遍历,ListIterator可以向前也可以向后
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;

ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
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;
}

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