某團(tuán)技術(shù)拷問：LinkedList 源碼看過嗎？
特此聲明：《Java 程序員進(jìn)階之路》專欄在 GitHub 上已經(jīng)開源了，有 GitHub 賬號(hào)的小伙伴，來給二哥安排一下 star 呀！看能不能沖一波 trending 榜單，求求各位了。
GitHub 地址：https://github.com/itwanger/toBeBetterJavaer
在線閱讀地址：https://itwanger.gitee.io/tobebetterjavaer
文末附最新版 PDF 的下載方式，想要的小伙伴可以立刻馬上拖到文末獲取呀，順手把點(diǎn)贊+在看悄悄地安排一下就可以了。
一、LinkedList 的剖白
大家好，我是 LinkedList，和 ArrayList 是同門師兄弟，但我倆練的內(nèi)功卻完全不同。師兄練的是動(dòng)態(tài)數(shù)組，我練的是鏈表。
問大家一個(gè)問題，知道我為什么要練鏈表這門內(nèi)功嗎？
舉個(gè)例子來講吧，假如你們手頭要管理一推票據(jù)，可能有一張，也可能有一億張。
該怎么辦呢？
申請(qǐng)一個(gè) 10G 的大數(shù)組等著？那萬一票據(jù)只有 100 張呢？
申請(qǐng)一個(gè)默認(rèn)大小的數(shù)組，隨著數(shù)據(jù)量的增大擴(kuò)容？要知道擴(kuò)容是需要重新復(fù)制數(shù)組的，很耗時(shí)間。
關(guān)鍵是，數(shù)組還有一個(gè)弊端就是，假如現(xiàn)在有 500 萬張票據(jù)，現(xiàn)在要從中間刪除一個(gè)票據(jù)，就需要把 250 萬張票據(jù)往前移動(dòng)一格。
遇到這種情況的時(shí)候，我?guī)熜謳缀跚榫w崩潰，難受的要命。師父不忍心看到師兄這樣痛苦，于是打我進(jìn)入師門那一天，就強(qiáng)迫我練鏈表這門內(nèi)功，一開始我很不理解，害怕師父偏心，不把師門最厲害的內(nèi)功教我。
直到有一天，我親眼目睹師兄差點(diǎn)因?yàn)橐苿?dòng)數(shù)據(jù)而走火入魔，我才明白師父的良苦用心。從此以后，我苦練“鏈表”這門內(nèi)功，取得了顯著的進(jìn)步，師父和師兄都夸我有天賦。
鏈表這門內(nèi)功大致分為三個(gè)層次：
第一層叫做“單向鏈表”，我只有一個(gè)后指針，指向下一個(gè)數(shù)據(jù)； 第二層叫做“雙向鏈表”，我有兩個(gè)指針，后指針指向下一個(gè)數(shù)據(jù)，前指針指向上一個(gè)數(shù)據(jù)。 第三層叫做“二叉樹”，把后指針去掉，換成左右指針。
但我現(xiàn)在的功力還達(dá)不到第三層，不過師父說我有這個(gè)潛力，練成神功是早晚的事。
二、LinkedList 的內(nèi)功心法
好了，經(jīng)過我這么樣的一個(gè)剖白后，大家對(duì)我應(yīng)該已經(jīng)不陌生了。那么接下來，我給大家展示一下我的內(nèi)功心法。
我的內(nèi)功心法主要是一個(gè)私有的靜態(tài)內(nèi)部類，叫 Node，也就是節(jié)點(diǎn)。
private 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;
}
}
它由三部分組成：
節(jié)點(diǎn)上的元素 下一個(gè)節(jié)點(diǎn) 上一個(gè)節(jié)點(diǎn)
我畫幅圖給你們展示下吧。
對(duì)于第一個(gè)節(jié)點(diǎn)來說，prev 為 null； 對(duì)于最后一個(gè)節(jié)點(diǎn)來說，next 為 null； 其余的節(jié)點(diǎn)呢，prev 指向前一個(gè)，next 指向后一個(gè)。
我的內(nèi)功心法就這么簡單，其實(shí)我早已經(jīng)牢記在心了。但師父叮囑我，每天早上醒來的時(shí)候，每天晚上睡覺的時(shí)候，一定要默默地背誦一遍。雖然我有些厭煩，但我對(duì)師父的教誨從來都是言聽計(jì)從。
03、LinkedList 的招式
和師兄 ArrayList 一樣，我的招式也無外乎“增刪改查”這 4 種。在此之前，我們都必須得初始化。
LinkedList<String> list = new LinkedList();
師兄在初始化的時(shí)候，默認(rèn)大小為 10，也可以指定大小，依據(jù)要存儲(chǔ)的元素?cái)?shù)量來。我就不需要。
1）招式一：增
可以調(diào)用 add 方法添加元素：
list.add("沉默王二");
list.add("沉默王三");
list.add("沉默王四");
add 方法內(nèi)部其實(shí)調(diào)用的是 linkLast 方法：
public boolean add(E e) {
linkLast(e);
return true;
}
linkLast，顧名思義，就是在鏈表的尾部鏈接：
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
添加第一個(gè)元素的時(shí)候，first 和 last 都為 null。 然后新建一個(gè)節(jié)點(diǎn) newNode，它的 prev 和 next 也為 null。 然后把 last 和 first 都賦值為 newNode。
此時(shí)還不能稱之為鏈表，因?yàn)榍昂蠊?jié)點(diǎn)都是斷裂的。
添加第二個(gè)元素的時(shí)候，first 和 last 都指向的是第一個(gè)節(jié)點(diǎn)。 然后新建一個(gè)節(jié)點(diǎn) newNode，它的 prev 指向的是第一個(gè)節(jié)點(diǎn)，next 為 null。 然后把第一個(gè)節(jié)點(diǎn)的 next 賦值為 newNode。
此時(shí)的鏈表還不完整。
添加第三個(gè)元素的時(shí)候，first 指向的是第一個(gè)節(jié)點(diǎn)，last 指向的是最后一個(gè)節(jié)點(diǎn)。 然后新建一個(gè)節(jié)點(diǎn) newNode，它的 prev 指向的是第二個(gè)節(jié)點(diǎn)，next 為 null。 然后把第二個(gè)節(jié)點(diǎn)的 next 賦值為 newNode。
此時(shí)的鏈表已經(jīng)完整了。
我這個(gè)增的招式，還可以演化成另外兩個(gè)：
addFirst()方法將元素添加到第一位；addLast()方法將元素添加到末尾。
addFirst 內(nèi)部其實(shí)調(diào)用的是 linkFirst：
public void addFirst(E e) {
linkFirst(e);
}
linkFirst 負(fù)責(zé)把新的節(jié)點(diǎn)設(shè)為 first，并將新的 first 的 next 更新為之前的 first。
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++;
}
addLast 的內(nèi)核其實(shí)和 addFirst 差不多，就交給大家自行理解了。
2）招式二：刪
我這個(gè)刪的招式還挺多的：
remove()：刪除第一個(gè)節(jié)點(diǎn)remove(int)：刪除指定位置的節(jié)點(diǎn)remove(Object)：刪除指定元素的節(jié)點(diǎn)removeFirst()：刪除第一個(gè)節(jié)點(diǎn)removeLast()：刪除最后一個(gè)節(jié)點(diǎn)
remove 內(nèi)部調(diào)用的是 removeFirst，所以這兩個(gè)招式的功效一樣。
remove(int) 內(nèi)部其實(shí)調(diào)用的是 unlink 方法。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
unlink 方法其實(shí)很好理解，就是更新當(dāng)前節(jié)點(diǎn)的 next 和 prev，然后把當(dāng)前節(jié)點(diǎn)上的元素設(shè)為 null。
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;
size--;
modCount++;
return element;
}
remove(Object) 內(nèi)部也調(diào)用了 unlink 方法，只不過在此之前要先找到元素所在的節(jié)點(diǎn)：
public boolean remove(Object o) {
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;
}
這內(nèi)部就分為兩種，一種是元素為 null 的時(shí)候，必須使用 == 來判斷；一種是元素為非 null 的時(shí)候，要使用 equals 來判斷。equals 是不能用來判 null 的，會(huì)拋出 NPE 錯(cuò)誤。
removeFirst 內(nèi)部調(diào)用的是 unlinkFirst 方法：
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
unlinkFirst 負(fù)責(zé)的就是把第一個(gè)節(jié)點(diǎn)毀尸滅跡，并且捎帶把后一個(gè)節(jié)點(diǎn)的 prev 設(shè)為 null。
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--;
modCount++;
return element;
}
3）招式三：改
可以調(diào)用 set() 方法來更新元素：
list.set(0, "沉默王五");
來看一下 set() 方法：
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
首先對(duì)指定的下標(biāo)進(jìn)行檢查，看是否越界；然后根據(jù)下標(biāo)查找原有的節(jié)點(diǎn)：
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;
}
}
size >> 1：也就是右移一位，相當(dāng)于除以 2。對(duì)于計(jì)算機(jī)來說，移位比除法運(yùn)算效率更高，因?yàn)閿?shù)據(jù)在計(jì)算機(jī)內(nèi)部都是二進(jìn)制存儲(chǔ)的。
換句話說，node 方法會(huì)對(duì)下標(biāo)進(jìn)行一個(gè)初步判斷，如果靠近前半截，就從下標(biāo) 0 開始遍歷；如果靠近后半截，就從末尾開始遍歷。
找到指定下標(biāo)的節(jié)點(diǎn)就簡單了，直接把原有節(jié)點(diǎn)的元素替換成新的節(jié)點(diǎn)就 OK 了，prev 和 next 都不用改動(dòng)。
4）招式四：查
我這個(gè)查的招式可以分為兩種：
indexOf(Object)：查找某個(gè)元素所在的位置 get(int)：查找某個(gè)位置上的元素
indexOf 的內(nèi)部分為兩種，一種是元素為 null 的時(shí)候，必須使用 == 來判斷；一種是元素為非 null 的時(shí)候，要使用 equals 來判斷。因?yàn)?equals 是不能用來判 null 的，會(huì)拋出 NPE 錯(cuò)誤。
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
get 方法的內(nèi)核其實(shí)還是 node 方法，這個(gè)之前已經(jīng)說明過了，這里略過。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
其實(shí)，查這個(gè)招式還可以演化為其他的一些，比如說：
getFirst()方法用于獲取第一個(gè)元素；getLast()方法用于獲取最后一個(gè)元素；poll()和pollFirst()方法用于刪除并返回第一個(gè)元素（兩個(gè)方法盡管名字不同，但方法體是完全相同的）；pollLast()方法用于刪除并返回最后一個(gè)元素；peekFirst()方法用于返回但不刪除第一個(gè)元素。
四、LinkedList 的挑戰(zhàn)
說句實(shí)在話，我不是很喜歡和師兄 ArrayList 拿來比較，因?yàn)槲覀兏髯孕逕挼膬?nèi)功不同，沒有孰高孰低。
雖然師兄經(jīng)常喊我一聲師弟，但我們之間其實(shí)挺和諧的。但我知道，在外人眼里，同門師兄弟，總要一較高下的。
比如說，我們倆在增刪改查時(shí)候的時(shí)間復(fù)雜度。
也許這就是命運(yùn)吧，從我進(jìn)入師門的那天起，這種爭論就一直沒有停息過。
無論外人怎么看待我們，在我眼里，師兄永遠(yuǎn)都是一哥，我敬重他，他也愿意保護(hù)我。
好了，LinkedList 這篇就到這了。
如果大家有閑情逸致的話，建議手撕一下鏈表，可以從單向鏈表開始撕起。
點(diǎn)擊下方的名片，回復(fù)關(guān)鍵字「03」 就可以獲取《Java 程序員進(jìn)階之路》的 PDF 版了。
希望大家能點(diǎn)贊+在看下，給二哥注入一點(diǎn)點(diǎn)更新的動(dòng)力。我也會(huì)不斷地提升品質(zhì)，給大家?guī)砀埠说募夹g(shù)文章，筆芯~