科技改變生活 · 科技引領未來
科技改變生活 · 科技引領未來
作者沉默王二來源公眾號沉默王二一、linkedList的剖白大家好，我是linkedList，和ArrayList是同門師兄弟，但我倆練的內功卻完全不同。師兄練的是動態數組，我練的是鏈表。問大家一個問題，知道我為什么要練鏈表這門內功嗎？舉個
作者沉默王二
來源公眾號沉默王二
一、linkedList 的剖白
大家好，我是 linkedList，和 ArrayList 是同門師兄弟，但我倆練的內功卻完全不同。師兄練的是動態數組，我練的是鏈表。
問大家一個問題，知道我為什么要練鏈表這門內功嗎？
舉個例子來講吧，假如你們手頭要管理一推票據，可能有一張，也可能有一億張。
該怎么辦呢？
申請一個 10G 的大數組等著？那萬一票據只有 100 張呢？
申請一個默認大小的數組，隨著數據量的增大擴容？要知道擴容是需要重新復制數組的，很耗時間。
關鍵是，數組還有一個弊端就是，假如現在有 500 萬張票據，現在要從中間刪除一個票據，就需要把 250 萬張票據往前移動一格。
遇到這種情況的時候，我師兄幾乎情緒崩潰，難受的要命。師父不忍心看到師兄這樣痛苦，于是打我進入師門那一天，就強迫我練鏈表這門內功，一開始我很不理解，害怕師父偏心，不把師門最厲害的內功教我。
直到有一天，我親眼目睹師兄差點因為移動數據而走火入魔，我才明白師父的良苦用心。從此以后，我苦練“鏈表”這門內功，取得了顯著的進步，師父和師兄都夸我有天賦。
鏈表這門內功大致分為三個層次：
但我現在的功力還達不到第三層，不過師父說我有這個潛力，練成神功是早晚的事。
二、linkedList 的內功心法
好了，經過我這么樣的一個剖白后，大家對我應該已經不陌生了。那么接下來，我給大家展示一下我的內功心法。
我的內功心法主要是一個私有的靜態內部類，叫 Node，也就是節點。
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; } } 它由三部分組成：
我畫幅圖給你們展示下吧。
我的內功心法就這么簡單，其實我早已經牢記在心了。但師父叮囑我，每天早上醒來的時候，每天晚上睡覺的時候，一定要默默地背誦一遍。雖然我有些厭煩，但我對師父的教誨從來都是言聽計從。
03、linkedList 的招式
和師兄 ArrayList 一樣，我的招式也無外乎“增刪改查”這 4 種。在此之前，我們都必須得初始化。
linkedList list = new linkedList(); 師兄在初始化的時候，默認大小為 10，也可以指定大小，依據要存儲的元素數量來。我就不需要。
1）招式一：增
可以調用 add 方法添加元素：
list.add("沉默王二"); list.add("沉默王三"); list.add("沉默王四"); add 方法內部其實調用的是 linkLast 方法：
public boolean add(E e) { linkLast(e); return true; } linkLast，顧名思義，就是在鏈表的尾部鏈接：
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++; } 此時還不能稱之為鏈表，因為前后節點都是斷裂的。
此時的鏈表還不完整。
此時的鏈表已經完整了。
我這個增的招式，還可以演化成另外兩個：
addFirst 內部其實調用的是 linkFirst：
public void addFirst(E e) { linkFirst(e); } linkFirst 負責把新的節點設為 first，并將新的 first 的 next 更新為之前的 first。
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++; } addLast 的內核其實和 addFirst 差不多，就交給大家自行理解了。
2）招式二：刪
我這個刪的招式還挺多的：
remove 內部調用的是 removeFirst，所以這兩個招式的功效一樣。
remove(int) 內部其實調用的是 unlink 方法。
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } unlink 方法其實很好理解，就是更新當前節點的 next 和 prev，然后把當前節點上的元素設為 null。
E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node 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) 內部也調用了 unlink 方法，只不過在此之前要先找到元素所在的節點：
public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } 這內部就分為兩種，一種是元素為 null 的時候，必須使用 == 來判斷；一種是元素為非 null 的時候，要使用 equals 來判斷。equals 是不能用來判 null 的，會拋出 NPE 錯誤。
removeFirst 內部調用的是 unlinkFirst 方法：
public E removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } unlinkFirst 負責的就是把第一個節點毀尸滅跡，并且捎帶把后一個節點的 prev 設為 null。
private E unlinkFirst(Node f) { // assert f == first && f != null; final E element = f.item; final Node 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）招式三：改
可以調用 set() 方法來更新元素：
list.set(0, "沉默王五"); 來看一下 set() 方法：
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; } } size >> 1：也就是右移一位，相當于除以 2。對于計算機來說，移位比除法運算效率更高，因為數據在計算機內部都是二進制存儲的。
換句話說，node 方法會對下標進行一個初步判斷，如果靠近前半截，就從下標 0 開始遍歷；如果靠近后半截，就從末尾開始遍歷。
找到指定下標的節點就簡單了，直接把原有節點的元素替換成新的節點就 OK 了，prev 和 next 都不用改動。
4）招式四：查
我這個查的招式可以分為兩種：
indexOf 的內部分為兩種，一種是元素為 null 的時候，必須使用 == 來判斷；一種是元素為非 null 的時候，要使用 equals 來判斷。因為 equals 是不能用來判 null 的，會拋出 NPE 錯誤。
public int indexOf(Object o) { int index = 0; if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } get 方法的內核其實還是 node 方法，這個之前已經說明過了，這里略過。
public E get(int index) { checkElementIndex(index); return node(index).item; } 其實，查這個招式還可以演化為其他的一些，比如說：
四、linkedList 的挑戰
說句實在話，我不是很喜歡和師兄 ArrayList 拿來比較，因為我們各自修煉的內功不同，沒有孰高孰低。
雖然師兄經常喊我一聲師弟，但我們之間其實挺和諧的。但我知道，在外人眼里，同門師兄弟，總要一較高下的。
比如說，我們倆在增刪改查時候的時間復雜度。
也許這就是命運吧，從我進入師門的那天起，這種爭論就一直沒有停息過。
無論外人怎么看待我們，在我眼里，師兄永遠都是一哥，我敬重他，他也愿意保護我。
馬熙明