先看再點贊，給自己一點思考的時間，思考過后請毫不猶豫微信搜索【沉默王二】，關注這個長發飄飄卻靠才華茍且的程式員，
本文 GitHub github.com/itwanger 已收錄，里面還有技術大佬整理的面試題，以及二哥的系列文章，
上一篇入坑了 ArrayList，小伙伴們反響不錯，那這篇就繼續入坑 LinkedList，它倆算是親密無間的兄弟，相愛相殺的那種，不離不棄的那種，介紹了這個就必須介紹那個的那種，
明目張膽地告訴大家一個好訊息，我寫了一份 4 萬多字的 Java 小白手冊，小伙伴們可以在「沉默王二」公眾號后臺回復「小白」獲取免費下載鏈接，覺得不錯的話，請隨手轉發給身邊需要的小伙伴，贈人玫瑰，手有余香哈，
最開始學習 Java 的時候，我還挺納悶的，有了 ArrayList，干嘛還要 LinkedList 啊，都是 List，不是很多余嗎？當時真的很傻很天真，不知道有沒有同款小伙伴，搞不懂兩者之間的區別，什么場景下該用 ArrayList，什么場景下該用 LinkedList，傻傻分不清楚，那么這篇文章，可以一腳把這種天真踹走了，
和陣列一樣，LinkedList 也是一種線性資料結構，但它不像陣列一樣在連續的位置上存盤元素，而是通過參考相互鏈接，
LinkedList 中的每一個元素都可以稱之為節點（Node），每一個節點都包含三個專案：其一是元素本身，其二是指向下一個元素的參考地址，其三是指向上一個元素的參考地址，
Node 是 LinkedList 類的一個私有的靜態內部類，其原始碼如下所示：
private static class Node<E> {
E item;
LinkedList.Node<E> next;
LinkedList.Node<E> prev;
Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList 看起來就像下面這個樣子：
第一個節點由于沒有前一個節點，所以 prev 為 null；
最后一個節點由于沒有后一個節點，所以 next 為 null；
這是一個雙向鏈表，每一個節點都由三部分組成，前后節點和值，
那可能有些小伙伴就會和當初的我一樣，好奇地問，“為什么要設計 LinkedList 呢？”如果能給 LinkedList 類的作者打個電話就好了，可惜沒有他的聯系方式，很遺憾，只能靠我來給大家解釋一下了，
第一，陣列的大小是固定的，即便是 ArrayList 可以自動擴容，但依然會有一定的限制：如果宣告的大小不足，則需要擴容；如果宣告的大小遠遠超出了實際的元素個數，又會造成記憶體的浪費，盡管擴容的演算法已經非常優雅，盡管記憶體已經綽綽有余，
第二，陣列的元素需要連續的記憶體位置來存盤其值，這就是 ArrayList 進行洗掉或者插入元素的時候成本很高的真正原因，因為我們必須移動某些元素為新的元素留出空間，比如說：
現在有一個陣列，10、12、15、20、4、5、100，如果需要在 12 的位置上插入一個值為 99 的元素，就必須得把 12 以后的元素往后移動，為 99 這個元素騰出位置，
洗掉是同樣的道理，洗掉之后的所有元素都必須往前移動一次，
LinkedList 就擺脫了這種限制：
第一，LinkedList 允許記憶體進行動態分配，這就意味著記憶體分配是由編譯器在運行時完成的，我們無需在 LinkedList 宣告的時候指定大小，
第二，LinkedList 不需要在連續的位置上存盤元素，因為節點可以通過參考指定下一個節點或者前一個節點，也就是說，LinkedList 在插入和洗掉元素的時候代價很低，因為不需要移動其他元素，只需要更新前一個節點和后一個節點的參考地址即可，
LinkedList 類的層次結構如下圖所示：
LinkedList 是一個繼承自 AbstractSequentialList 的雙向鏈表，因此它也可以被當作堆疊、佇列或雙端佇列進行操作，
LinkedList 實作了 List 介面，所以能對它進行佇列操作，
LinkedList 實作了 Deque 介面，所以能將 LinkedList 當作雙端佇列使用，
明白了 LinkedList 的一些理論知識后，我們來看一下如何使用 LinkedList，
01、如何創建一個 LinkedList
LinkedList<String> list = new LinkedList<>();
和創建 ArrayList 一樣，可以通過上面的陳述句來創建一個字串型別的 LinkedList（通過尖括號來限定 LinkedList 中元素的型別，如果嘗試添加其他型別的元素，將會產生編譯錯誤），
不過，LinkedList 無法在創建的時候像 ArrayList 那樣指定大小，
02、向 LinkedList 中添加一個元素
可以通過 add() 方法向 LinkedList 中添加一個元素：
LinkedList<String> list = new LinkedList<>();
list.add("沉默王二");
list.add("沉默王三");
list.add("沉默王四");
感興趣的小伙伴可以研究一下 add() 方法的原始碼，它在添加元素的時候會呼叫 linkLast() 方法，
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
添加第一個元素的時候，last 為 null，創建新的節點（next 和 prev 都為 null），然后再把新的節點賦值給 last 和 first；當添加第二個元素的時候，last 為第一個節點，創建新的節點（next 為 null，prev 為第一個節點），然后把 last 更新為新的節點，first 保持不變，第一個節點的 next 更新為第二個節點；以此類推，
還可以通過 addFirst() 方法將元素添加到第一位；addLast() 方法將元素添加到末尾；add(int index, E element) 方法將元素添加到指定的位置，
03、更新 LinkedList 中的元素
可以使用 set() 方法來更改 LinkedList 中的元素，需要提供下標和新元素，
list.set(0, "沉默王五");
來看一下 set() 方法的原始碼：
public E set(int index, E element) {
checkElementIndex(index);
LinkedList.Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
該方法會先對指定的下標進行檢查，看是否越界，然后根據下標查找節點：
LinkedList.Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
LinkedList.Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
LinkedList.Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
node() 方法會對下標進行一個初步的判斷，如果靠近末端，則從最后開始遍歷，這樣能夠節省不少遍歷的時間，小伙伴們眼睛要睜大點了，這點要學，
找到節點后，再替換新值并回傳舊值，
04、洗掉 LinkedList 中的元素
可以通過 remove() 方法洗掉指定位置上的元素：
list.remove(1);
該方法會呼叫 unlink() 方法對前后節點進行更新，
E unlink(LinkedList.Node<E> x) {
// assert x != null;
final E element = x.item;
final LinkedList.Node<E> next = x.next;
final LinkedList.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;
}
還可以使用 removeFirst() 和 removeLast() 方法洗掉第一個節點和最后一個節點，
05、查找 LinkedList 中的元素
如果要正序查找一個元素，可以使用 indexOf() 方法；如果要倒序查找一個元素，可以使用 lastIndexOf() 方法，
來看一下 indexOf() 方法的原始碼：
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (LinkedList.Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (LinkedList.Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
基本上和 ArrayList 的大差不差，都需要遍歷，如果要查找的元素為 null，則使用“==”運算子，可以避免拋出空指標例外；否則使用 equals() 方法進行比較，
另外，getFirst() 方法用于獲取第一個元素；getLast() 方法用于獲取最后一個元素；poll() 和 pollFirst() 方法用于洗掉并回傳第一個元素（兩個方法盡管名字不同，但方法體是完全相同的）；pollLast() 方法用于洗掉并回傳最后一個元素；peekFirst() 方法用于回傳但不洗掉第一個元素，
06、最后
如果要我們自己實作一個鏈表的話，上面這些增刪改查的輪子方法是一定要白嫖啊，不對，一定要借鑒啊，
上一篇 ArrayList 中提到過，隨機訪問一個元素的時間復雜度為 O(1)，但 LinkedList 要復雜一些，因為資料增大多少倍，耗時就增大多少倍，因為要回圈遍歷，所以時間復雜度為 O(n)，
至于 LinkedList 在插入、添加、洗掉元素的時候有沒有比 ArrayList 更快，這要取決于資料量的大小，以及元素所在的位置，不過，從理論上來說，由于不需要移動陣列，應該會更快一些，但到底快不快，下一篇帶來答案，小伙伴們敬請期待，
我是沉默王二，一枚有顏值卻靠才華茍且的程式員，關注即可提升學習效率，別忘了三連啊，點贊、收藏、留言，我不挑，奧利給，
注：如果文章有任何問題，歡迎毫不留情地指正，
如果你覺得文章對你有些幫助歡迎微信搜索「沉默王二」第一時間閱讀，回復「小白」更有我肝了 4 萬+字的 Java 小白手冊 2.0 版，本文 GitHub github.com/itwanger 已收錄，歡迎 star，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/140452.html
標籤：Java