一、LinkedList 的剖白
大家好，我是 LinkedList，和 ArrayList 是同門師兄弟，但我倆練的内功卻完全不同。師兄練的是動态數組，我練的是連結清單。
問大家一個問題，知道我為什麼要練連結清單這門内功嗎？
舉個例子來講吧，假如你們手頭要管理一推票據，可能有一張，也可能有一億張。
該怎麼辦呢？
申請一個 10G 的大數組等着？那萬一票據隻有 100 張呢？
申請一個預設大小的數組，随着資料量的增大擴容？要知道擴容是需要重新複制數組的，很耗時間。
關鍵是，數組還有一個弊端就是，假如現在有 500 萬張票據，現在要從中間删除一個票據，就需要把 250 萬張票據往前移動一格。
遇到這種情況的時候，我師兄幾乎情緒崩潰，難受的要命。師父不忍心看到師兄這樣痛苦，于是打我進入師門那一天，就強迫我練連結清單這門内功，一開始我很不了解，害怕師父偏心，不把師門最厲害的内功教我。
直到有一天，我親眼目睹師兄差點因為移動資料而走火入魔，我才明白師父的良苦用心。從此以後，我苦練“連結清單”這門内功，取得了顯著的進步，師父和師兄都誇我有天賦。
連結清單這門内功大緻分為三個層次：
第一層叫做“單向連結清單”，我隻有一個後指針，指向下一個資料；
第二層叫做“雙向連結清單”，我有兩個指針，後指針指向下一個資料，前指針指向上一個資料。
第三層叫做“二叉樹”，把後指針去掉，換成左右指針。
但我現在的功力還達不到第三層，不過師父說我有這個潛力，練成神功是早晚的事。
先贊後看：《Java 程式員進階之路》專欄在 GitHub 上已經開源了，有 GitHub 賬号的小夥伴，來安排一波 star 呀！看能不能沖一波 trending 榜單，求求各位了。
GitHub 位址：
https://github.com/itwanger/toBeBetterJavaer二、LinkedList 的内功心法
好了，經過我這麼樣的一個剖白後，大家對我應該已經不陌生了。那麼接下來，我給大家展示一下我的内功心法。
我的内功心法主要是一個私有的靜态内部類，叫 Node，也就是節點。
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;
}
} 它由三部分組成：
節點上的元素
下一個節點
上一個節點
我畫幅圖給你們展示下吧。
對于第一個節點來說，prev 為 null；
對于最後一個節點來說，next 為 null；
其餘的節點呢，prev 指向前一個，next 指向後一個。
我的内功心法就這麼簡單，其實我早已經牢記在心了。但師父叮囑我，每天早上醒來的時候，每天晚上睡覺的時候，一定要默默地背誦一遍。雖然我有些厭煩，但我對師父的教誨從來都是言聽計從。
03、LinkedList 的招式
和師兄 ArrayList 一樣，我的招式也無外乎“增删改查”這 4 種。在此之前，我們都必須得初始化。
LinkedList<String> 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<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++;
} 添加第一個元素的時候，first 和 last 都為 null。
然後建立一個節點 newNode，它的 prev 和 next 也為 null。
然後把 last 和 first 都指派為 newNode。
此時還不能稱之為連結清單，因為前後節點都是斷裂的。
添加第二個元素的時候，first 和 last 都指向的是第一個節點。
然後建立一個節點 newNode，它的 prev 指向的是第一個節點，next 為 null。
然後把第一個節點的 next 指派為 newNode。
此時的連結清單還不完整。
添加第三個元素的時候，first 指向的是第一個節點，last 指向的是最後一個節點。
然後建立一個節點 newNode，它的 prev 指向的是第二個節點，next 為 null。
然後把第二個節點的 next 指派為 newNode。
此時的連結清單已經完整了。
我這個增的招式，還可以演化成另外兩個：
addFirst() 方法将元素添加到第一位；
addLast() 方法将元素添加到末尾。