鏈表是對上一篇博文所說的順序表的一種實現。
與ArrayList思路截然不同，鏈表的實現思路是：
不同元素實際上是存儲在離散的內存空間中的。
每一個元素都有一個指針指向下一個元素，這樣整個離散的空間就被“串”成了一個有順序的表。
從鏈表的概念來講，它可以算是一種遞歸的數據結構，因為鏈表拿掉第一個元素剩下的部分，依然構成一個鏈表。
時間空間復雜度
通過索引定位其中的一個元素。由于不能像ArrayList那樣直接通過計算內存地址偏移量來定位元素，只能從第一個元素開始順藤摸瓜來數，因此為O(n)。
插入元素。實際上插入元素需要看情況：
如果指定鏈表中某個元素將其插之其后，那么首先得找出該元素對應的節點，還是O(n)。
如果能夠直接指定節點往其后插入(如通過迭代器)，那么僅僅需要移動指針即可完成，O(1)。
移除元素。移除和插入類似，得看提供的參數是什么。如果提供的是元素所在的節點，那么也只需要O(1)。
LinkedList的繼承結構
首先繼承結構和ArrayList類似，實現了List接口。
但是，它繼承的是繼承了AbstractList類的AbstractSequentialList類，
這個類的作用也是給List中的部分函數提供默認實現，只是這個類對鏈表這種List的實現提供了更多貼合的默認函數實現。
還有可以注意到，LinkedList實現了Deque接口，這也很顯然，鏈表這種結構天然就適合當做雙端隊列使用。
LinkedList源碼分析
節點定義
先來看鏈表的節點定義：
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
可以看到，鏈表節點除了保存數據外，還需要保存指向前后節點的指針。
這里，鏈表即有后繼指針也有前驅指針，因此這是一個雙向鏈表。
一組節點之間按順序用指針指起來，就形成了鏈表的鏈狀結構。
屬性和構造函數
transient int size = 0;
transient Node first;
transient Node last;
三個屬性，first和last分別指向鏈條的首節點和尾節點。
這樣有個好處，就是鏈表即可以使用頭插法也可以采用尾插法。
size屬性跟蹤了鏈表的元素個數。雖然說遍歷一遍鏈表也能統計到元素個數，
但是那是O(n)的費時操作。
因此，我們可以發現鏈表的size方法是O(1)的時間復雜度。
public LinkedList() {
}
LinkedList的代碼很簡單，構造函數空空如也。
空表中，first和last字段都為null。
get和set方法
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
public E set(int index, E element) {
checkElementIndex(index);
Node x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
Node node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
get和set的思路都是先根據索引定位到鏈表節點，然后獲得或設置節點中的數據，這抽象出了node函數，根據索引找到鏈表節點。
node的思路也很顯然，遍歷一遍即可得到。
這里做了一點優化，我們可以發現LinkedList的實現是一個雙向鏈表，并且LinkedList持有了頭尾指針。
那么，根據索引和size就可以知道該節點是在鏈表的前半部分還是后半部分，
從而決定從頭節點開始遍歷還是從尾節點開始遍歷，這樣最多遍歷 N / 2次即可找到。
添加/刪除
public boolean add(E e) {
linkLast(e);
return true;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node succ) {
final Node pred = succ.prev;
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
添加/刪除的思路都類似，刪除的代碼就不貼了。如果能夠提供需要被操作的節點，就能直接移動下指針，O(1)完成。否則就需要遍歷找到這個節點再操作。
需要關注兩點：
有的操作是操作頭指針，有的操作是操作尾指針。但是不管操作哪一個，都需要維護另外一個指針及size的值。
如果是刪除，刪除后及時把相關節點的item字段置為null，以幫助gc能更快的釋放內存。
modCount字段分析
之前閱讀ArrayList的代碼時發現了modCount這一字段，它是定義在AbstractList類中的。之前不知道它起到什么作用，這次給弄明白了。
迭代器
迭代器迭代中表被修改
考慮以下這段代碼：
List list = new LinkedList<>();
Iterator it = list.listIterator();
list.add(1);
it.next();
在迭代器創建之后，對表進行了修改。這時候如果操作迭代器，則會得到異常java.util.ConcurrentModificationException。
這樣設計是因為，迭代器代表表中某個元素的位置，內部會存儲某些能夠代表該位置的信息。當表發生改變時，該信息的含義可能會發生變化，這時操作迭代器就可能會造成不可預料的事情。
因此，果斷拋異常阻止，是最好的方法。
實際上，這種迭代器迭代過程中表結構發生改變的情況，更經常發生在多線程的環境中。
記錄表被修改的標記
這種機制的實現就需要記錄表被修改，那么思路是使用狀態字段modCount。
每當會修改表的操作執行時，都將此字段加1。使用者只需要前后對比該字段就知道中間這段時間表是否被修改。
如linkedList中的頭插和尾插函數，就將modCount字段自增：
private void linkFirst(E e) {
final Node f = first;
final Node newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
迭代器
迭代器使用該字段來判斷，
private class ListItr implements ListIterator {
private Node lastReturned;
private Node 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 void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
迭代器開始時記錄下初始的值：
private int expectedModCount = modCount;
然后與現在的值對比判斷是否被修改：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
這是一個內部類，隱式持有LinkedList的引用，能夠直接訪問到LinkedList中的modCount字段。
 詳解)
)
