LinkedList初探
LinkedList初探
作為Java工程師，LinkedList你可能用的不多，大多你總是在new ArrayList，面試很多時候總是拿LinkedList和ArrayList的做對比，總會問你ArrayList 和 LinkedList 的區別是什么？它倆是不是執行緒安全的？等等，很多時候你的習慣了使用ArrayList，都很少考慮使用LinkedList，你可能都不知道他可以用作記憶體佇列或者堆疊，再接下來的幾節中，你就可以學習到LinkedList的底層各種原始碼的原理，練習之前學習到方法分析原始碼，
首先先讓我們回顧下LinkedList的基礎知識，
LinkedList基本原理以及優缺點
LinkedList基本原理以及優缺點
1）LinkedList基本原理
一句話講，在JDK中，LinkedList底層基于一個雙向鏈表來維護資料，JDK 1.7以前是一個雙向回圈鏈表，
2）LinkedList優缺點
缺點：
- 隨機訪問性能差
優點：
- 頻繁插入和洗掉元素性能很好，容量沒有限制
- 可用作記憶體佇列或者堆疊
- 有順序性
初探LinkedList的脈絡
初探LinkedList的脈絡
你第一步應該做什么呢？對，沒錯，看下LinkedList的原始碼脈絡：
第一張圖中，你可以看到只有三個成員遍歷size、fisrt、last，除了size，其他兩個變數都是Node型別，可以猜測Node應該是它一個內部類，剩下的就是我們常用的建構式、add、get、set、remove等方法了，最后還有一些toArray、addAll、indexOf等方法和ArrayList的API很像，
第二張圖如下：
這張圖里面，可以看到有一些pop、push、poll、offer這些方法，如果你熟悉資料結構的話，這些方法名字很像是佇列資料結構入隊，出隊和堆疊結構的入堆疊、出堆疊常用的方法名，接著就是ListItr、Node兩個內部類了，
當你看過LinkeList原始碼的脈絡后，接下來是不是應該簡單寫一個Demo，從它的入口開始，看下他的核心原始碼呢？
從add方法開始探索LinkedList
從add方法開始探索LinkedList
你應該記得之前我們提到過，看核心原始碼一般是從入口開始，也就常說的自頂而下，
首先你要有個代碼Demo，當你使用LinkedList的時候，一般是不是先創建，之后會呼叫add方法呢？來看下如下代碼清單：
import java.util.LinkedList;
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> hostList = new LinkedList<>();
hostList.add("host1");
hostList.add("host2");
hostList.add("host3");
}
}
這個很簡單的代碼，入口是main函式，第一行就是創建了一個LinkedList，里面的元素都是String型別，使用默認無參的建構式，你點擊建構式，進入原始碼來看看：
/**
* Constructs an empty list.
*/
public LinkedList() {
}
什么都沒干，從注釋上看出來，構造了一個空的LinkedList，之前你可能會注意到有一個size變數，你可以猜到，其實LinkedList沒有大小限制，理論上記憶體足夠，可以無限鏈接下去，上面的代碼執行完成后，之前復習過LinkedList是一個雙向鏈表，所以會形成如下的圖：
接著main函式執行下一行，執行 add方法：
public boolean add(E e) {
linkLast(e);
return true;
}
直接呼叫了linkLast方法，之后回傳true了，
所以需要看下linkLast方法原始碼，終于，看到了重點，這個方法的脈絡，有兩個last和first成員變數，先弄了一個newNode，之后有一個if-else判斷，之后size++就回傳了，看上去好像很簡單，
transient Node<E> first;
transient Node<E> last;
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++;
}
但是這個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;
}
}
你可以畫一個圖來理解下：原來Node就是一個內部類，有一個item元素，Node類本身有一個next和prev是Node物件，
這個結構有沒有很熟悉？如果你對資料結構比較熟悉的話，或者你知道LinkedList的底層資料是雙向鏈表，你就可以連蒙帶猜的想到，這個應該就是LinkedList底層代表雙向鏈表的封裝類，
prev和next是兩個指標，指向了前一個節點和后一個節點，item是一個泛型，應該是存放對應的資料元素的，希望這個資料結構你沒有還給大學老師，
你知道了Node是什么后，再來看下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++;
}
首先執行第一行時，看上去還是不太好理解是什么意思，所以你是不是需要祭出一個方法：畫圖！通過畫圖來梳理下這個方法的脈絡，如下所示：
從圖中可清晰的看出final Node
接著執行第二行：final Node
如圖上圖所示，創建了一個Node物件叫newNode，item元素的值是”host1”,newNode的prev指標和l指向了一個地址，l指向的地址是last，是null，所以prev也是null，
再接著執行下一行，last = newNode,這個很簡單，就是last指向了newNode節點，如下圖所示：
再接著，你可以看到會進入進入if-else判斷,如下圖所示：
實際是讓first指向了newNode，最后進行了size++，linkLast方法就回傳了，最終結果是不是就如下圖所示：
經過這五步圖，你是不是就理解了LinkedList的add方法了？主要做了以下三件事情：
- 使用臨時指標l記錄原最后一元素的位置
- 創建新元素，新元素的prev指標指向原最后一元素
- last指標指向新元素，如果是第一次添加元素fisrt指標也會指向新元素
大家可以想象下，再添加一個元素是不是就還是這個思路呢？記住這個思路，你可以試試自己畫畫圖來感受下！
你就會得到如下的圖：
其實你關鍵要記住的是輔助指標的思路，這樣對你后面如果想首先一個鏈表，或者翻轉一個單向鏈表會提供很好的思路，在集合篇的結尾會讓大家感受到的，
金句甜點
金句甜點
除了今天知識，技能的成長，給大家帶來一個金句甜點，結束我今天的分享：相信比知道更重要，
我給大家講個故事，從前在西方，有一個牧師，他傳教非常成功，為什么呢？因為他百分之百的相信上帝，所以他傳教的時候，總是這么說“上帝說……”，他的信徒越來越多，有一天他突然發現，這些人都沒有見過上帝，都是我跟他們講“上帝說，上帝說…”，那我為什么要講上帝說,從此以后他就改成了 “我自己說…我說…”，所以之后他傳教時候就變成了“我說……，結果信徒越來越少，最后只剩他自己一個人，這個故事你可以學到什么？相信的力量有多大，
其實很多時候我們相信事情會好起來，病會好起來，很多道理，事情，你不能只是知道，而是要相信，相信和知道的區別有多大？就比如知道就像你頭上的帽子，風一吹可能就刮走了，而相信就像是你頭上的頭發，風怎么吹都不會掉的，相信就是根深蒂固，一種信念，會逐漸形成你的觀念，成為了你自己的價值觀，所以很多時候不要只是知道，每天學習成長記會讓自己提升，會讓自己變好，而是你要相信每天看看成長記，一定會讓自己成長，變得越來越好，記住相信比知道更重要，
最后，你可以閱讀完原始碼后，在茶余飯后的時候問問同事或同學， 你也可以分享下，講給他聽聽，
歡迎大家在評論區留言和我交流，
本文由博客群發一文多發等運營工具平臺 OpenWrite 發布
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/320860.html
標籤：其他