LinkedList也是Java集合类中运用比较广泛的一个结构，它与上篇介绍的ArrayList都是实现List接口，但是它们的特点不同。这篇文章是阅读LinkedList类做的记录来加深对LinkedList的理解。
LinkedList类图
下图是LinkedList类图，其中蓝色线条意味着继承，绿色线条意味着接口实现。
LinkedList的描述
LinkedList位于java.util包下面，下面是官方对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/**
* Doubly-linked list implementation of the {@code List} and {@code Deque}
* interfaces. Implements all optional list operations, and permits all
* elements (including {@code null}).
*
* <p>All of the operations perform as could be expected for a doubly-linked
* list. Operations that index into the list will traverse the list from
* the beginning or the end, whichever is closer to the specified index.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access a linked list concurrently, and at least
* one of the threads modifies the list structurally, it <i>must</i> be
* synchronized externally. (A structural modification is any operation
* that adds or deletes one or more elements; merely setting the value of
* an element is not a structural modification.) This is typically
* accomplished by synchronizing on some object that naturally
* encapsulates the list.
*
* If no such object exists, the list should be "wrapped" using the
* {@link Collections#synchronizedList Collections.synchronizedList}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the list:<pre>
* List list = Collections.synchronizedList(new LinkedList(...));</pre>
*
* <p>The iterators returned by this class's {@code iterator} and
* {@code listIterator} methods are <i>fail-fast</i>: if the list is
* structurally modified at any time after the iterator is created, in
* any way except through the Iterator's own {@code remove} or
* {@code add} methods, the iterator will throw a {@link
* ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than
* risking arbitrary, non-deterministic behavior at an undetermined
* time in the future.
*
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw {@code ConcurrentModificationException} on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
主要意思就是以下几点：
- 双向链表LinkedList实现了List和Deque这两个接口的所有任意的list操作，而且接受放入所有的元素（包括null）。
- 所有操作都建立在一个双向链表之上，使用索引来获取一个元素将是从链表的头或者从链表的尾部开始遍历这个链表到制定的节点。
- 记住，LinkedList的实现不是线程安全的。如果当前有多个线程使用这个list，同时至少有一个线程修改这个list的结构（一个结构化的修改的意思是所有所有增加或者删除至少一个元素，修改一个元素的值不属于结构化修改）。这些操作在list的外层必须被加上锁。通常大佬会熟练地使用某个object为这个list加上锁。
- 如果没有object用来为list加锁，使用Collections.syncharonizedList方法来包装这个list。为了预防额外的不安全的操作通过这个list，这个操作做好在创建list的时候就执行。
- 这个通过iterator或者listIterator方法返回的迭代器是fail-fast的，这意味着这个迭代器在创建之后，如果原来的list其中的元素在任何地方（除了在通过迭代器使用remove或者add方法）被结构化的修改，都会使下一次迭代器的操作抛出一个ConcurrentModrfcationException异常。因此，迭代器在当前修改的时候是快速清除地失败而不是有风险地保存含糊不清地数据在list中。
- 记住，这个迭代器的fail-fast行为不能完全担保可以应对不安全的线程，迭代器只是最大能力地抛出ConcurrentModrfcationException异常。所以，使用依赖这个异常来维护一个程序的正确性是很不好的行为，fail-fast行为只应该被用来发现bug!
LinkedList的定义
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
LinkedList 是一个继承于AbstractSequentialList的双向循环链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList实现List接口，能对它进行队列操作。
LinkedList实现Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList属性
1 | transient int size = 0; |
LinkedList有上面三个属性，size表示双向链表的大小，first指向的是双向链表的第一个结点，last指向最后一个结点。元素在内部被封装成Node对象，这是一个内部类，看一下它的代码：1
2
3
4
5
6
7
8
9
10
11private 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;
}
}
这是一个双向链表的结构，每个结点保存它的前驱结点和后继结点。
LinkedList的构造方法
1 | public LinkedList() { |
LinkedList有一个空参构造函数和一个集合参数构造函数。
LinkedList常用方法
私有方法
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
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//头部插入
private void linkFirst(E e) {
final Node<E> f = first; //先保存当前头节点
//创建一个新节点，节点值为e，前驱节点为空，后继节点为当前头节点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;//让first指向新节点
if (f == null)//如果链表原来为空，把last指向这个唯一的节点
last = newNode;
else //否则原来的头节点的前驱指向新的头节点
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last element.
*/
void linkLast(E e) {//尾部插入
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) //如果链表原来为空，让first指向这个唯一的节点
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) { //中间插入，插入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++;
}
/**
* Unlinks non-null first node 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;//让first指向下一个节点
if (next == null)//如果下一个节点为空，说明链表原来只有一个节点，现在成空链表了，要把last指向null
last = null;
else //否则下一个节点的前驱节点要置为null
next.prev = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null last node 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; //last指向前一个节点
if (prev == null) //与头节点删除一样，判断是否为空
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null node 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要指向下一个节点
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;
}
上面代码中都给出详细的解释，就是我们数据结构课中所学的双向链表，当删除和插入时怎么移动指针的问题。
公开方法
公开的方法，例如添加和删除，几乎都是调用上面几个方法实现的,我们来看一下：
add添加
1 | public void addFirst(E e) { |
这些添加的方法，都是涉及到指针的怎么移动，当在指定位置插入时，都会涉及到先找到指定位置，即调用node(index)这个方法，我们来看一下这个方法：1
2
3
4
5
6
7
8
9
10
11
12
13
14Node<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;
}
}
这里查找指定位置的元素时，先判断位置是在链表的前半段还是后半段，然后决定从链表的头还是尾去寻找节点。
remove删除
1 | public E remove(int index) { |
第一个删除指定位置的元素，第二个删除指定的元素。第一个remove(int index)方法同样要调用node(index)寻找节点，然后调用unlink(Node x)。第二个方法要依次遍历节点进行元素的比较，最坏情况下要比较到最后一个元素，比调用node方法更慢，时间复杂度为O(n)。
set修改
1 | public E set(int index, E element) { |
get查询
1 | public E get(int index) { |
set,get方法都比较简单就不再解释了。
indexOf
1 | public int indexOf(Object o) { |
可以看出LinkedList的元素可以是null。
LinkedList实现的Deque双端队列的一些方法
1 | // 双向队列操作，链表首部插入新节点 |
- elemet和getFirst一样，都返回列表的头，并且不移除它，如果列表为空，都会抛出NoSucnElement异常；
- peek也会返回第一个元素，但是为空时返回null, 不抛异常；
- remove方法内部就是调用removeFirst，所以表现相同，返回移除的元素，如果列表为空，都会抛出NoSucnElement异常；
- poll也是移除第一个元素，只是会在列表为空时只返回null；
- offer和offerLast在尾部add节点， 最终调用的都是addLast方法，offerFirst在头保护add节点，调用的就是addFirst方法；
- peekFirst返回头节点，为空时返回null，peekLast返回尾节点，为空时返回null，都不会删除节点；
- pollFirst删除并返回头节点，为空时返回null ，pollLast删除并返回尾节点，为空时返回null；
- push和pop也是让LinkedList具有栈的功能，也只是调用了addFirst和removeFirst函数。
ListIterator迭代器
ListIterator是一个更加强大的Iterator迭代器的子类型，它只能用于各种List类的访问。尽管Iterator只能向前移动，但是ListIterator可以双向移动。它还可以产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引，可以用set()方法替换它访问过得最后一个元素。
定义：1
2
3
4public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
指定index，可以在一开始就获取一个指向index位置元素的迭代器。实际上调用的是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
98private class ListItr implements ListIterator<E> {
private Node<E> lastReturned = null;
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();
}
}
LinkedList的迭代器与ArrayList相比有一些额外的用法，LinkedList的迭代器也是用来遍历数据，同时也有fail-fast特性帮助程序员排除线程上的bug。除此之外，LinkedList的迭代器还提供了更好的删除与添加的性能。
使用迭代器的遍历LinkedList，每一次移动，删除，增加这些操作，迭代器都会将当前节点的索引保存下来。
Deque接口还有一个逆向迭代器descendingIterator()可以注意一下。