前面学习了ArrayList的源码，
数组是顺序存储结构，存储区间是连续的，占用内存严重，故空间复杂的很大。
但数组的二分查找时间复杂度小，为O(1)，数组的特点是寻址容易，插入和删除困难。
今天学习另外的一种常用数据结构LinkedList的实现，
LinkedList使用链表作为存储结构，链表是线性存储结构，在内存上不是连续的一段空间，
占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N），链表的特点是寻址困难，插入和删除容易。
所有的代码都基于JDK 1.6。
>>关于LinkedList
LinkedList继承了AbstractSequentialList，实现了List，Deque，Cloneable，Serializable 接口，
（1）继承和实现
继承AbstractSequentialList类，提供了相关的添加、删除、修改、遍历等功能。
实现List接口，提供了相关的添加、删除、修改、遍历等功能。
实现 Deque 接口，即能将LinkedList当作双端队列使用，可以用做队列或者栈
实现了Cloneable接口，即覆盖了函数clone()，能被克隆复制，
实现java.io.Serializable接口，LinkedList支持序列化，能通过序列化传输。
（2）线程安全
LinkedList是非同步的，即线程不安全，如果有多个线程同时访问LinkedList，可能会抛出ConcurrentModificationException异常。
|
1
2
3
4
|
final
void
checkForComodification() {
if
(modCount != expectedModCount)
throw
new
ConcurrentModificationException();
}
|
代码中，modCount记录了LinkedList结构被修改的次数。Iterator初始化时，expectedModCount=modCount。任何通过Iterator修改LinkedList结构的行为都会同时更新expectedModCount和modCount，使这两个值相等。通过LinkedList对象修改其结构的方法只更新modCount。所以假设有两个线程A和B。A通过Iterator遍历并修改LinkedList，而B，与此同时，通过对象修改其结构，那么Iterator的相关方法就会抛出异常
>>双向链表结构
和普通的链表不同，双向链表每个节点不止维护指向下一个节点的next指针，还维护着指向上一个节点的previous指针。
（1）内部实现
LinkedList内部使用Entry<E>来封装双向循环链表结点。
LinkedList头结点的定义:
|
1
2
3
4
|
//头结点的定义
private
transient
Entry<E> header =
new
Entry<E>(
null
,
null
,
null
);
//链表的实际长度
private
transient
int
size =
0
;
|
Entry是一个静态内部类，
|
1
2
3
4
5
6
7
8
9
10
11
|
private
static
class
Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this
.element = element;
this
.next = next;
this
.previous = previous;
}
}
|
（2）构造函数
LinkedList内部提供了两个构造函数，
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
/**
* 初始化一个空的list，可以理解为一个双向循环链表
*/
public
LinkedList() {
header.next = header.previous = header;
}
/**
* 使用指定的collection构造一个list
*/
public
LinkedList(Collection<?
extends
E> c) {
this
();
addAll(c);
}
|
>>常用方法
（1）遍历方式
LinkedList支持多种遍历方式。建议不要采用随机访问的方式去遍历LinkedList，而采用逐个遍历的方式。
(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。for(Iterator iter = list.iterator(); iter.hasNext();) iter.next();(02) 通过快速随机访问遍历LinkedList
int size = list.size(); for (int i=0; i<size; i++) { list.get(i); }(03) 通过另外一种for循环来遍历LinkedList
for (Integer integ:list) ;(04) 通过pollFirst()来遍历LinkedList
while(list.pollFirst() != null) ;(05) 通过pollLast()来遍历LinkedList
while(list.pollLast() != null) ;(06) 通过removeFirst()来遍历LinkedList
try { while(list.removeFirst() != null) ; } catch (NoSuchElementException e) { }(07) 通过removeLast()来遍历LinkedList
try { while(list.removeLast() != null) ; } catch (NoSuchElementException e) { }
遍历LinkedList时，使用removeFist()或removeLast()效率最高。但用它们遍历时，会删除原始数据；若单纯只读取，而不删除，应该使用第3种遍历方式。
链表的特点是内存空间不连续，插入和删除简单，寻址的时间复杂度较高，随机访问去遍历LinkedList的效率是最低的。
（2）常用方法（从API摘的）
boolean add(E e)
将指定元素添加到此列表的结尾。
void add(int index, E element)
在此列表中指定的位置插入指定的元素。
boolean addAll(Collection<? extends E> c)
添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。
boolean addAll(int index, Collection<? extends E> c)
将指定 collection 中的所有元素从指定位置开始插入此列表。
void addFirst(E e)
将指定元素插入此列表的开头。
void addLast(E e)
将指定元素添加到此列表的结尾。
void clear()
从此列表中移除所有元素。
Object clone()
返回此 LinkedList 的浅表副本。
boolean contains(Object o)
如果此列表包含指定元素，则返回 true。
Iterator<E> descendingIterator()
返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。
E element()
获取但不移除此列表的头（第一个元素）。
E get(int index)
返回此列表中指定位置处的元素。
E getFirst()
返回此列表的第一个元素。
E getLast()
返回此列表的最后一个元素。
int indexOf(Object o)
返回此列表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。
int lastIndexOf(Object o)
返回此列表中最后出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。
ListIterator<E> listIterator(int index)
返回此列表中的元素的列表迭代器（按适当顺序），从列表中指定位置开始。
boolean offer(E e)
将指定元素添加到此列表的末尾（最后一个元素）。
boolean offerFirst(E e)
在此列表的开头插入指定的元素。
boolean offerLast(E e)
在此列表末尾插入指定的元素。
E peek()
获取但不移除此列表的头（第一个元素）。
E peekFirst()
获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。
E peekLast()
获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。
E poll()
获取并移除此列表的头（第一个元素）
E pollFirst()
获取并移除此列表的第一个元素；如果此列表为空，则返回 null。
E pollLast()
获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。
E pop()
从此列表所表示的堆栈处弹出一个元素。
void push(E e)
将元素推入此列表所表示的堆栈。
E remove()
获取并移除此列表的头（第一个元素）。
E remove(int index)
移除此列表中指定位置处的元素。
boolean remove(Object o)
从此列表中移除首次出现的指定元素（如果存在）。
E removeFirst()
移除并返回此列表的第一个元素。
boolean removeFirstOccurrence(Object o)
从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。
E removeLast()
移除并返回此列表的最后一个元素。
boolean removeLastOccurrence(Object o)
从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。
E set(int index, E element)
将此列表中指定位置的元素替换为指定的元素。
int size()
返回此列表的元素数。
>>双端队列
双端队列是一个限定插入和删除操作的数据结构，具有队列和栈的性质，
双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。
查看源码的实现，可以发现作为队列和栈时的相关方法。
（1）作为队列使用
add(e) 内部实现是addLast(e)
offer(e) 入队，直接返回add()
remove() 获取并移除列表第一个元素，和poll()相同，内部调用removeFirst()
poll() 出队 获取并移除队头元素 内部实现是调用removeFirst()
element() 返回列表第一个元素但不移除，内部调用getFirst()
peek() 返回列表第一个元素但不移除，和element()相同，内部调用getFirst()
（2）作为栈使用
push(e) 入栈 即addFirst(e)
pop() 出栈 即removeFirst()
peek() 获取栈顶元素但不移除 即peekFirst()
>>源码分析
（1）主要的节点更新操作
源码中的两个私有方法addBefore和remove是维护了节点更新的主要操作，
这一部分主要是数据结构中对链表的操作，理解起来比较简单，
大部分的add、remode等操作都可以通过这两个方法实现。
|
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
|
/**
* 在传入节点之前插入新的节点元素
*/
private
Entry<E> addBefore(E e, Entry<E> entry) {
//构造一个新的节点
Entry<E> newEntry =
new
Entry<E>(e, entry, entry.previous);
//调整新节点前后节点的指向
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return
newEntry;
}
/**
* 在链表中删除这个节点
*/
private
E remove(Entry<E> e) {
//e等于初始化时的空节点，抛出异常
if
(e == header)
throw
new
NoSuchElementException();
E result = e.element;
/**
* 删除操作就是调整前后结点指针的指向，绕过传入节点
* 然后再把传入节点的前后指针以及value都置为null
*/
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous =
null
;
e.element =
null
;
size--;
modCount++;
return
result;
}
|
（2）List迭代器 通过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
|
private
class
ListItr
implements
ListIterator<E> {
private
Entry<E> lastReturned = header;
private
Entry<E> next;
private
int
nextIndex;
private
int
expectedModCount = modCount;
ListItr(
int
index) {
if
(index <
0
|| index > size)
throw
new
IndexOutOfBoundsException(
"Index: "
+index+
", Size: "
+size);
if
(index < (size >>
1
)) {
next = header.next;
for
(nextIndex=
0
; nextIndex<index; nextIndex++)
next = next.next;
}
else
{
next = header;
for
(nextIndex=size; nextIndex>index; nextIndex--)
next = next.previous;
}
}
public
boolean
hasNext() {
return
nextIndex != size;
}
public
E next() {
checkForComodification();
if
(nextIndex == size)
throw
new
NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return
lastReturned.element;
}
public
boolean
hasPrevious() {
return
nextIndex !=
0
;
}
public
E previous() {
if
(nextIndex ==
0
)
throw
new
NoSuchElementException();
lastReturned = next = next.previous;
nextIndex--;
checkForComodification();
return
lastReturned.element;
}
public
int
nextIndex() {
return
nextIndex;
}
public
int
previousIndex() {
return
nextIndex-
1
;
}
public
void
remove() {
checkForComodification();
Entry<E> lastNext = lastReturned.next;
try
{
LinkedList.
this
.remove(lastReturned);
}
catch
(NoSuchElementException e) {
throw
new
IllegalStateException();
}
if
(next==lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = header;
expectedModCount++;
}
public
void
set(E e) {
if
(lastReturned == header)
throw
new
IllegalStateException();
checkForComodification();
lastReturned.element = e;
}
public
void
add(E e) {
checkForComodification();
lastReturned = header;
addBefore(e, next);
nextIndex++;
expectedModCount++;
}
final
void
checkForComodification() {
if
(modCount != expectedModCount)
throw
new
ConcurrentModificationException();
}
}
|
>>fail-fast机制
fail-fast，快速失败是Java集合的一种错误检测机制。
当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。
记住是有可能，而不是一定。例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
>>ArrayList和LinkedList的区别
ArrayList是一个基于数组的结构，里面的节点相互之间没有特别的联系，默认的大小是10，最大大小是Integer.MAX_VALUE - 8。
当大小不够时会自动增长，它可以通过get，set来直接获取、修改某一个节点数据。
LinkedList是一个基于双向链表的结构，每一个节点都有两个指针来分别指向上一个节点和下一个节点。它是可变长度的。
这两个实现类的区别在于，ArrayList的get()/set()效率比LinkedList高，而LinkedList的add()/remove()效率比ArrayList高。
具体来说：数组申请一块连续的内存空间，是在编译期间就确定大小的，运行时期不可动态改变，但为什么ArrayList可以改变大小呢，
因为在add如果超过了设定的大小就会创建一个新的更大的（增长率好像是0.5）ArrayList，
然后将原来的list复制到新的list中，并将地址指向新的list，旧的list被GC回收，显然这是非常消耗内存而且效率非常低的。
但是由于它申请的内存空间是连续的，可以直接通过下标来获取需要的数据，时间复杂度为O(1)，而链表则是O(n)，
而链表结构不一样，它可以动态申请内存空间。在需要加入的节点的上一个节点的指针解开并指向新加节点，再将新加节点的指针指向后一个节点即可。速度很快的。
所以说ArrayList适合查询，LinkedList适合增删。
