LinkedList概述
1 | public class LinkedList<E> |
LinkedList是List和Deque接口的双向链表的实现。实现了所有可选列表操作，并允许包括null值。
LinkedList既然是通过双向链表去实现的，那么它可以被当作堆栈、队列或双端队列进行操作。并且其顺序访问非常高效，而随机访问效率比较低。
注意，此实现不是同步的。
LinkedList源码解析
节点Node数据结构
1 | private static class Node<E> { |
LinkedList类结构
1 | /通过LinkedList实现的接口可知，其支持队列操作，双向列表操作，能被克隆，支持序列化 |
LinkedList包含了三个重要的对象：first、last 和 size:
- first 是双向链表的表头，它是双向链表节点所对应的类Node的实例
- last 是双向链表的最后一个元素，它是双向链表节点所对应的类Node的实例
- size 是双向链表中节点的个数。
构造函数
1 | //构建一个空列表 |
添加元素
1 | //头插入，在列表首部插入节点值e |
删除元素
LinkedList提供了头删除removeFirst()、尾删除removeLast()、remove(int index)、remove(Object o)、clear()这些删除元素的方法。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//移除首节点，并返回该节点的元素值
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//删除非空的首节点f
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; //将原首节点的next节点设置为首节点
if (next == null) //如果原链表只有一个节点，即原首节点，删除后，链表为null
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
//移除尾节点，并返回该节点的元素值
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//删除非空的尾节点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; //将原尾节点的prev节点设置为尾节点
if (prev == null) //如果原链表只有一个节点,则删除后，链表为null
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
//移除此列表中指定位置上的元素
public E remove(int index) {
checkElementIndex(index); //index >= 0 && index < size
return unlink(node(index));
}
//删除非空节点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;
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; // help GC
size--;
modCount++;
return element;
}
//移除列表中首次出现的指定元素(如果存在)，LinkedList中允许存放重复的元素
public boolean remove(Object o) {
//由于LinkedList中允许存放null，因此下面通过两种情况来分别处理
if (o == null) {
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) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//清除列表中所有节点
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
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;
modCount++;
}
修改元素
LinkedList提供了set(int index, E element)方法来修改指定索引上的值。
1 | //替换指定索引位置节点的元素值，并返回旧值 |
查找元素
LinkedList提供了getFirst()、getLast()、contains(Object o)、get(int index)、indexOf(Object o)、lastIndexOf(Object o)这些查找元素的方法。
1 | //返回列表首节点元素值 |
由LinkedList的类结构可以看出，LinkedList是AbstractSequentialList的子类。AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些随机访问的函数，那么LinkedList也实现了这些随机访问的接口。LinkedList具体是如何实现随机访问的？即，具体是如何定义index这个参数的
在源码中，Node1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16//返回指定索引位置的节点
Node<E> node(int index) {
// assert isElementIndex(index);
//折半思想，当index < size/2时，从列表首节点向后查找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { //当index >= size/2时，从列表尾节点向前查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。 源码中先将index与长度size的一半比较，如果index
其他public方法
clone()、 toArray() 、toArray(T[] a)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//返回此 LinkedList实例的浅拷贝
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
//返回一个包含LinkedList中所有元素值的数组
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
//如果给定的参数数组长度足够，则将ArrayList中所有元素按序存放于参数数组中，并返回
//如果给定的参数数组长度小于LinkedList的长度，则返回一个新分配的、长度等于LinkedList长度的、包含LinkedList中所有元素的新数组
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
支持序列化的写入函数writeObject(java.io.ObjectOutputStream s)和读取函数readObject(java.io.ObjectInputStream s)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
30private static final long serialVersionUID = 876323262645176354L;
//序列化：将linkedList的“大小，所有的元素值”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
//反序列化：先将LinkedList的“大小”读出，然后将“所有的元素值”读出
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject()); //以尾插入的方式
}
Queue操作
Queue操作提供了peek()、element()、poll()、remove()、offer(E 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//获取但不移除此队列的头；如果此队列为空，则返回 null
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//获取但不移除此队列的头；如果此队列为空，则抛出NoSuchElementException异常
public E element() {
return getFirst();
}
//获取并移除此队列的头，如果此队列为空，则返回 null
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//获取并移除此队列的头，如果此队列为空，则抛出NoSuchElementException异常
public E remove() {
return removeFirst();
}
//将指定的元素值(E e)插入此列表末尾
public boolean offer(E e) {
return add(e);
}
Deque（双端队列）操作
Deque操作提供了offerFirst(E e)、offerLast(E e)、peekFirst()、peekLast()、pollFirst()、pollLast()、push(E e)、pop()、removeFirstOccurrence(Object o)、removeLastOccurrence(Object o)这些方法。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//获取但不移除此队列的头；如果此队列为空，则返回 null
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//获取但不移除此队列的头；如果此队列为空，则抛出NoSuchElementException异常
public E element() {
return getFirst();
}
//获取并移除此队列的头，如果此队列为空，则返回 null
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//获取并移除此队列的头，如果此队列为空，则抛出NoSuchElementException异常
public E remove() {
return removeFirst();
}
//将指定的元素值(E e)插入此列表末尾
public boolean offer(E e) {
return add(e);
}
// Deque operations
//将指定的元素插入此双端队列的开头
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//将指定的元素插入此双端队列的末尾
public boolean offerLast(E e) {
addLast(e);
return true;
}
//获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
//获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 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);
}
//将一个元素推入此双端队列所表示的堆栈（换句话说，此双端队列的头部）
public void push(E e) {
addFirst(e);
}
//从此双端队列所表示的堆栈中弹出一个元素（换句话说，移除并返回此双端队列的头部）
public E pop() {
return removeFirst();
}
//从此双端队列移除第一次出现的指定元素，如果列表中不包含次元素，则没有任何改变
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
//从此双端队列移除最后一次出现的指定元素,如果列表中不包含次元素，则没有任何改变
public boolean removeLastOccurrence(Object o) {
//由于LinkedList中允许存放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;
}
Fail-Fast机制
LinkedList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
常用的LinkedList的遍历方式
LinkedList不提倡运用随机访问的方式进行元素遍历。
通过迭代器Iterator遍历：
1
2
3
4
5Iterator iter = list.iterator();
while (iter.hasNext())
{
System.out.println(iter.next());
}通过迭代器ListIterator遍历：
1
2
3
4
5
6
7
8
9ListIterator<String> lIter = list.listIterator();
//顺向遍历
while(lIter.hasNext()){
System.out.println(lIter.next());
}
//逆向遍历
while(lIter.hasPrevious()){
System.out.println(lIter.previous());
}foreach循环遍历
1
2
3
4for(String str:list)
{
System.out.println(str);
}