LinkedList實(shí)現(xiàn)原理（JDK1.8）
LinkedList底層采用雙向鏈表，如果對(duì)鏈表這種結(jié)構(gòu)比較熟悉的話，那LinkedList的實(shí)現(xiàn)原理看明白就相當(dāng)容易另凌。
鏈表通過(guò)“指針”將一組零散的內(nèi)存塊串聯(lián)起來(lái)使用康吵，每一個(gè)元素（節(jié)點(diǎn)）通過(guò)指針指向它的下一個(gè)元素实夹，最后一個(gè)節(jié)點(diǎn)的下一個(gè)指向?yàn)閚ull，而雙向鏈表就是除頭節(jié)點(diǎn)的每一個(gè)元素都有指針同時(shí)再指向它的上一個(gè)元素粒梦。鏈表不同于數(shù)組亮航，由于其地址的不連續(xù)，且元素占用大小的不確定匀们，所以沒(méi)法根據(jù)地址直接取值缴淋，獲取元素時(shí)需要遍歷訪問(wèn)，而雙向鏈表相比于單向鏈表泄朴，一定程度上占用了額外的內(nèi)存重抖，但支持了雙向遍歷，加快了元素索取祖灰。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList繼承于AbstractSequentialList抽象類钟沛，AbstractSequentialList又繼承于AbstractList，最終實(shí)現(xiàn)了List的接口局扶，所以LinkedList支持List集合的一些常規(guī)操作恨统，但同時(shí)LinkedList又實(shí)現(xiàn)了Queue接口，所以LinkedList也支持隊(duì)列的一些使用三妈，例如peek畜埋、pop等。
1.成員變量
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
LinkedList的主要成員變量就3個(gè)畴蒲，大小size悠鞍、頭結(jié)點(diǎn)first、尾節(jié)點(diǎn)last模燥，這也符合雙向鏈表的特點(diǎn)狞玛，根據(jù)頭或者尾部節(jié)點(diǎn)就可以遍歷整個(gè)鏈表。至于節(jié)點(diǎn)類型涧窒，則是內(nèi)部類Node心肪。
private static class Node<E> {
// 節(jié)點(diǎn)數(shù)據(jù)
E item;
// 下一節(jié)點(diǎn)
Node<E> next;
// 上一節(jié)點(diǎn)
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Node類就簡(jiǎn)簡(jiǎn)單單三個(gè)屬性，也即雙向鏈表節(jié)點(diǎn)必須的3個(gè)要素纠吴，當(dāng)前節(jié)點(diǎn)數(shù)據(jù)item硬鞍，下一節(jié)點(diǎn)next和上一節(jié)點(diǎn)prev。
2.構(gòu)造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
// 添加所有元素
addAll(c);
}
LinkedList主要就兩個(gè)構(gòu)造方法戴已，一個(gè)無(wú)參的構(gòu)造固该，什么也沒(méi)做，另一個(gè)接受集合的構(gòu)造糖儡，該方法初始化了LinkedList對(duì)象并添加了所有集合c的元素伐坏。
至于addAll方法，我們后面再看握联。
LinkedList因?yàn)榛阪湵龛氤粒圆恍枰崆吧暾?qǐng)內(nèi)存大小每瞒，也就不存在初始化指定容量大小，因而LinkedList是沒(méi)有初始化指定size的構(gòu)造方法的纯露。
3.添加元素
3.1.尾部添加
LinkedList的添加方法有很多剿骨，首先最簡(jiǎn)單也是最常用的尾部添加。
public boolean add(E e) {
linkLast(e);
return true;
}
主要邏輯就是linkLast(E e) 了埠褪。
void linkLast(E e) {
final Node<E> l = last;
// 構(gòu)造新的節(jié)點(diǎn)浓利，上一節(jié)點(diǎn)指向原來(lái)的last
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
// 操作數(shù)自增
modCount++;
}
尾部添加，就是構(gòu)造新的節(jié)點(diǎn)newNode钞速，并將改節(jié)點(diǎn)的上一節(jié)點(diǎn)prev指向原來(lái)的last贷掖，同時(shí)改節(jié)點(diǎn)為新的last節(jié)點(diǎn)。l == null判斷是否當(dāng)前是第一次添加渴语，如果 l 為 null羽资，則newNode同時(shí)也是頭結(jié)點(diǎn)，當(dāng)前集合中僅有newNode一個(gè)元素遵班，不為null時(shí)，因?yàn)殡p向鏈表潮改，所有 l 的下一個(gè)節(jié)點(diǎn)next指向了newNode狭郑。
最后就是大小size自增與操作計(jì)數(shù)modCount的自增，尾部添加元素就完成了汇在。
尾部操作除了add翰萨，還有個(gè)addLast(E e) 方法，兩者除了返回值不一樣糕殉，沒(méi)有任何差別了亩鬼，都是調(diào)用的linkLast方法。
public void addLast(E e) {
linkLast(e);
}
3.2.中間添加
public void add(int index, E element) {
// 范圍檢查
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
對(duì)于中間添加阿蝶，需要首先進(jìn)行范圍檢查雳锋，即保證插入位置index在[0, size]之間，否則拋出數(shù)組越界異常IndexOutOfBoundsException羡洁，呃……數(shù)組越界……
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
如果index == size玷过，其實(shí)就是尾部插入，所以調(diào)用了linkLast筑煮，這個(gè)剛剛尾部插入已經(jīng)說(shuō)過(guò)辛蚊。
如果index < size，中間插入的時(shí)候真仲，需要分兩步：
- node(int index)方法獲取到index位置的元素succ
- linkBefore(E e, Node<E> succ)將需要插入的元素element連接到succ后面
node方法是一個(gè)頻繁被調(diào)用的方法袋马，LinkedList 的很多操作都依賴于該方法查找到對(duì)應(yīng)的元素。根據(jù)索引 index 獲取元素時(shí)秸应，因?yàn)殡p向鏈表的支持前后遍歷虑凛，所以進(jìn)行了位置判斷碑宴，index < (size >> 1)，與中間位置比較卧檐，靠前則前序遍歷墓懂，否則后序遍歷。
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;
}
}
遍歷邏輯很簡(jiǎn)單霉囚，循環(huán)到index上一個(gè)節(jié)點(diǎn)（后序則是下一個(gè)）位置捕仔，獲取next（后序使用prev）返回index位置對(duì)應(yīng)的節(jié)點(diǎn)Node對(duì)象succ。
void linkBefore(E e, Node<E> 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++;
}
linkBefore和linkLast幾乎完全一樣盈罐，除了一個(gè)是添加到 last 節(jié)點(diǎn)后榜跌，一個(gè)是添加到 succ 節(jié)點(diǎn)后。
對(duì)于中間插入盅粪，如果index為0時(shí)钓葫，其實(shí)就是頭部插入，這個(gè)時(shí)候比不用調(diào)用node方法去查找元素了票顾，所以LinkedList也提供了一個(gè)addFirst(E e)方法础浮。
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
3.3.批量插入
LinkedList提供尾部批量插入和中間批量插入，但內(nèi)部實(shí)現(xiàn)其實(shí)都是調(diào)用的addAll(int index, Collection<? extends E> c)奠骄。
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 范圍校驗(yàn)
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// succ是index位置元素豆同，pred是index的前一個(gè)元素
Node<E> pred, succ;
if (index == size) { // 尾部插入
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
// 循環(huán)插入
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// 銜接處理
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
size += numNew;
modCount++;
return true;
}
addAll(int index, Collection<? extends E> c)方法初一看，好像有些復(fù)雜含鳞，但明白其原理后影锈，就變得清晰多了。鏈表插入就如同接水管蝉绷，先從某一個(gè)位置斷開(kāi)水管鸭廷，然后用接口連接上需要接入的部分。這個(gè)方法里熔吗，關(guān)鍵的是兩個(gè)Node對(duì)象pred, 和 succ辆床，succ 是index位置元素，pred是index的前一個(gè)元素（變動(dòng)）桅狠。
特殊情況 index == size 時(shí)佛吓，即尾部插入，所以succ 就是null了垂攘，而 pred則為尾部節(jié)點(diǎn)last维雇。
然后就是循環(huán)賦值了，在循環(huán)中構(gòu)造node節(jié)點(diǎn)晒他，類似于linkLast吱型。
最后的是銜接處理，如果尾部插入的話陨仅，那pred就是尾部節(jié)點(diǎn)了（循環(huán)賦值時(shí)有pred = newNode處理）津滞，所以只需要指定last = pred铝侵。而中間插入，指明 pred.next = succ触徐、succ.prev = pred即將index位置與新的前一個(gè)元素綁定到一起咪鲜。
4.查找元素
LinkedList 除了提供通用的 get，因?yàn)槠鋵傩灾泻?first 和 last 節(jié)點(diǎn)撞鹉，也提供了 getFirst 和 getLast 方法疟丙。
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
對(duì)于getFirst 和 getLast，因?yàn)槭浅蓡T變量鸟雏，省去了查找的過(guò)程享郊，直接返回其節(jié)點(diǎn) item 即可。
public E get(int index) {
// 范圍校驗(yàn)
checkElementIndex(index);
// node方法獲取節(jié)點(diǎn)
return node(index).item;
}
而通過(guò)指針的獲取孝鹊，主要就是調(diào)用node方法找對(duì)index對(duì)應(yīng)的節(jié)點(diǎn)炊琉，node方法前面已經(jīng)講過(guò)，不再累述又活。
5.修改元素
對(duì)于LinkedList集合中元素的修改苔咪，需要先查找到該元素，然后更改其Node節(jié)點(diǎn)數(shù)據(jù)item即可柳骄。
public E set(int index, E element) {
// 范圍檢查
checkElementIndex(index);
// 獲取index對(duì)應(yīng)位置的Node對(duì)象
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
6.刪除元素
LinkedList提供了很多種刪除元素的方法团赏，但是內(nèi)部實(shí)現(xiàn)邏輯基本都相同，即找到對(duì)應(yīng)的Node節(jié)點(diǎn)夹界，然后將指向該節(jié)點(diǎn)的指向替換。
6.1.根據(jù)索引移除
我們先來(lái)看看根據(jù)索引的remove(int index)方法隘世。
public E remove(int index) {
// 范圍檢查
checkElementIndex(index);
// 解除節(jié)點(diǎn)指針連接
return unlink(node(index));
}
刪除時(shí)的范圍檢查就不說(shuō)了可柿，node方法也不再多提，刪除的主要邏輯就是unlink(Node<E> x)方法丙者。
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
// 下一節(jié)點(diǎn)
final Node<E> next = x.next;
// 前一節(jié)點(diǎn)
final Node<E> prev = x.prev;
// 前一節(jié)點(diǎn)prev存在則將prev的下一節(jié)點(diǎn)指向next复斥，不存在則當(dāng)前移除節(jié)點(diǎn)其實(shí)就是頭結(jié)點(diǎn)，next就是新的first
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// 下一節(jié)點(diǎn)next存在械媒，則將next上一節(jié)點(diǎn)指向prev目锭，不存在則說(shuō)明當(dāng)前移除的是未節(jié)點(diǎn)
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 觸發(fā)GC工作
x.item = null;
size--;
// 操作計(jì)數(shù)器自增
modCount++;
return element;
}
整個(gè)unlink方法就是個(gè)標(biāo)準(zhǔn)的雙向鏈表刪除操作，三個(gè)節(jié)點(diǎn)prev纷捞，x痢虹，next，刪除x 其實(shí)就是將 prev指向next主儡，并next指向prev奖唯，只是其中多了一些特殊的判斷。
看了按索引刪除的remove糜值，再來(lái)看另外兩個(gè)特例removeFirst 和 removeLast丰捷。
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(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;
if (next == null)
last = null;
else
next.prev = null;
size--;
// 操作計(jì)數(shù)器自增
modCount++;
return element;
}
unlinkFirst就是個(gè)簡(jiǎn)化版的unlink方法坯墨，因?yàn)橹挥锰幚眍^結(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)next存在就將next作為新的first病往。
同理removeLast也是類似捣染，這里各位看官自行進(jìn)行體會(huì)。
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(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;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
而LinkedList還有個(gè)無(wú)參的remove停巷，這個(gè)是Deque接口定義的耍攘，實(shí)現(xiàn)也就是調(diào)用的removeFirst。
public E remove() {
return removeFirst();
}
6.2.根據(jù)元素移除
根據(jù)元素移除其實(shí)和根據(jù)索引移除沒(méi)有太大差別叠穆，只不過(guò)找到對(duì)應(yīng)節(jié)點(diǎn)的方式發(fā)生了變化少漆。
public boolean remove(Object o) {
// 判斷元素是否為null，因?yàn)長(zhǎng)inkedList支持添加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;
}
可以看到硼被，無(wú)論元素是否為null示损，都是先找到該節(jié)點(diǎn)，然后調(diào)用了unlink方法嚷硫。
因?yàn)橹С蛛p向遍歷的特性检访，LinkedList很人性的提供了前序刪除和后序刪除的方法，即removeFirstOccurrence與removeLastOccurrence仔掸。
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
public boolean removeLastOccurrence(Object o) {
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;
}
這兩個(gè)方法沒(méi)什么玄幻的脆贵，removeLastOccurrence只是反序遍歷了集合。
6.3.批量刪除
在LinkedList類中起暮，并沒(méi)有removeAll方法卖氨，因?yàn)樗磳?duì)其進(jìn)行重寫(xiě)，而是使用了父類AbstractCollection的
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
// 使用迭代器
Iterator<?> it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
removeAll的實(shí)現(xiàn)原理其實(shí)就是迭代刪除负懦，迭代器的獲取方法iterator()在AbstractCollection類中只是個(gè)抽象方法筒捺，AbstractList類有其實(shí)現(xiàn)，但AbstractSequentialList類中覆寫(xiě)該方法纸厉。
public Iterator<E> iterator() {
return listIterator();
}
iterator方法會(huì)調(diào)用listIterator()系吭，這個(gè)方法實(shí)現(xiàn)在AbstractList類中，他調(diào)用了listIterator(int index)方法颗品，但LinkedList重寫(xiě)了該方法肯尺，所以兜兜轉(zhuǎn)轉(zhuǎn)最終還是回到了LinkedList中。
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
這里L(fēng)istItr對(duì)象是LinkedList的內(nèi)部類躯枢。
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
// 期待計(jì)數(shù)器
private int expectedModCount = modCount;
ListItr在初始化的時(shí)候则吟，會(huì)將操作計(jì)數(shù)器modCount賦值給expectedModCount，而之后的每次remove方法锄蹂，都會(huì)校驗(yàn)expectedModCount與modCount是否相等逾滥，否則會(huì)拋出異常。
ListItr的remove方法，每次調(diào)用后寨昙，都將expectedModCount自增讥巡，已達(dá)到和unlink中modCount++的同步，從而使得modCount == expectedModCount 一直成立舔哪，這也是為什么我們循環(huán)刪除LinkedList元素時(shí)需要使用其迭代器的remove方法欢顷。
public void remove() {
// 校驗(yàn)modCount
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
// unlink刪除節(jié)點(diǎn)邏輯，該方法中有modCount++;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
// expectedModCount自增
expectedModCount++;
}
final void checkForComodification() {
// expectedModCount與modCount必須相等
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
