LinkedList
简介
LinkedList是一个以双向链表实现的List
基本概念：
- 链表每个节点叫做 Node，Node 有 prev 属性，代表前一个节点的位置，next 属性，代表后一个节点的位置；
- first 是双向链表的头节点，它的前一个节点是 null。
- last 是双向链表的尾节点，它的后一个节点是 null；
- 当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null；
- 因为是个双向链表，只要机器内存足够强大，是没有大小限制的。
类图
源码
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;
}
}
属性
1
2
3
4
5
6
//元素个数
transient int size = 0;
//链表首节点
transient Node<E> first;
//链表尾节点
transient Node<E> last;
构造方法
无界队列
1
2
3
4
5
6
7
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
//将指定的元素追加到此列表的末尾
public boolean add(E e) {
linkLast(e);
return true;
}
//将指定的元素插入此列表的开头
public void addFirst(E e) {
linkFirst(e);
}
//将指定的元素追加到此列表的末尾
public void addLast(E e) {
linkLast(e);
}
//将指定的元素添加为此列表的尾部
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;
}
linkLast(E e)
将e链接为最后一个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void linkLast(E e) {
final Node<E> l = last;
//包装为新Node,prev指向链表的last,e是元素本身，next设置为null
final Node<E> newNode = new Node<>(l, e, null);
//新Node成为尾节点
last = newNode;
if (l == null)
first = newNode;
else
//之前的尾节点的next设置为新Node
l.next = newNode;
size++;
//修改次数加1
modCount++;
}
linkFirst(E e)
将e链接为第一个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
private void linkFirst(E e) {
final Node<E> f = first;
//包装为新Node,prev设置为null,e是元素本身，next设置为头节点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
//之前的头节点的prev设置为新Node
f.prev = newNode;
size++;
modCount++;
}
add(int index, E element)
LinkedList 作为List支持中间添加元素。
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
//元素插入列表中的指定位置
public void add(int index, E element) {
//检查是否越界
checkPositionIndex(index);
//index=size，直接加在尾节点
if (index == size)
linkLast(element);
else
//插在node(index)节点之前
linkBefore(element, 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;
}
}
//在非null节点succ之前插入元素e
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//元素succ的前节点
final Node<E> pred = succ.prev;
//包装e为新Node,prev设置为pred,e是Node本身，succ设置为next
final Node<E> newNode = new Node<>(pred, e, succ);
//元素succ的prev设置为新Node
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
在队列首尾添加元素很高效，时间复杂度为O(1)。
在中间添加元素比较低效，首先要先找到插入位置的节点，再修改前后节点的指针，时间复杂度为O(n)。
删除
作为双端队列，删除元素也有两种方式，一种是队列首删除元素，一种是队列尾删除元素。
作为List，支持中间删除元素。
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
//删除头节点
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);
}
//删除指定节点
public boolean remove(Object o) {
if (o == null) {
//删除第一个null元素
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
//遍历删除第一个o元素
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//删除指定位置节点
public E remove(int index) {
//检查是否越界
checkElementIndex(index);
//删除指定index位置的节点
return unlink(node(index));
}
//检索并删除此列表的第一个元素，如果此列表为空，则返回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);
}
//删除头节点
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
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;
size--;
modCount++;
return element;
}
//删除尾节点
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;
size--;
modCount++;
return element;
}
//删除制定节点
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;
size--;
modCount++;
return element;
}
在队列首尾删除元素很高效，时间复杂度为O(1)。
在中间删除元素比较低效，首先要找到删除位置的节点，再修改前后指针，时间复杂度为O(n)。
栈
LinkedList可以作为栈使用。
1
2
3
4
5
6
7
8
//元素压入此列表表示的堆栈
public void push(E e) {
addFirst(e);
}
//元素出栈
public E pop() {
return removeFirst();
}
迭代器
LinkedList.iterator()返回的是ListItr内部类实现的迭代器。
1
2
3
4
5
6
7
8
9
10
11
12
13
//AbstractSequentialList.iterator()
public Iterator<E> iterator() {
return listIterator();
}
//AbstractList.listIterator()
public ListIterator<E> listIterator() {
return listIterator(0);
}
//LinkedList复写listIterator()方法
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
LinkedList的内部类ListItr，实现了双向的迭代访问。
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
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
//期望版本号；modCount：目前最新版本号
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();
}
}
总结
LinkedList是一个以双链表实现的List；LinkedList还是一个双端队列，具有队列、双端队列、栈的特性；LinkedList在队列首尾添加、删除元素非常高效，时间复杂度为O(1)；LinkedList在中间添加、删除元素比较低效，时间复杂度为O(n)；LinkedList不支持随机访问，所以访问非队列首尾的元素比较低效；LinkedList在功能上等于ArrayList + ArrayDeque；
