鏈表看這一篇真的就夠了！
前言
有的小伙伴說沒有學(xué)過數(shù)據(jù)結(jié)構(gòu)，對鏈表不是特別了解，所以今天我們就來對鏈表進行一個系統(tǒng)的總結(jié)，另外大家如果想提高算法思想的話，我建議還是要系統(tǒng)的學(xué)一下數(shù)據(jù)結(jié)構(gòu)的。閱讀完本文你會有以下收獲1.知道什么是鏈表？2.了解鏈表的幾種類型。3.了解鏈表如何構(gòu)造。4.鏈表的存儲方式5.如何遍歷鏈表6.了解鏈表的操作。7.知道鏈表和數(shù)組的不同點8.掌握鏈表的經(jīng)典題目。鏈表的定義：
定義：鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，他或者為空（null），或者是指向一個結(jié)點（node）的引用，該結(jié)點含有一個泛型的元素和一個指向另一條鏈表的引用。我們來對其解讀一下，鏈表是一種常見且基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是他不是按線性順序存取數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的地址。我們也可以這樣理解，鏈表是通過指針串聯(lián)在一起的線性結(jié)構(gòu)，每一個鏈表結(jié)點由兩部分組成，數(shù)據(jù)域及指針域，鏈表的最后一個結(jié)點指向null。也就是我們所說的空指針。
鏈表的幾種類型
我們先來看一下鏈表的可視化表示方法，以便更好的對其理解。-
用長方形表示對象
-
將實例變量的值寫在長方形中；
-
用指向被引用對象的箭頭表示引用關(guān)系。
單鏈表
一個單向鏈表包含兩個值: 當(dāng)前節(jié)點的值和一個指向下一個節(jié)點的鏈接。我們通過上面說到的可視化表示方法，將單鏈表可視化，如圖所示。
雙向鏈表
上面提到了單鏈表的節(jié)點只能指向節(jié)點的下一個節(jié)點。而雙向鏈表有三個整數(shù)值: 數(shù)值、向后的節(jié)點鏈接、向前的節(jié)點鏈接，所以雙鏈表既能向前查詢也可以向后查詢。還有一個常用的鏈表則為循環(huán)單鏈表，則單鏈表尾部的指針指向頭節(jié)點。例如在 leetcode61旋轉(zhuǎn)鏈表中，我們就是先將鏈表閉合成環(huán)，找到新的打開位置，并定義新的表頭和表尾。
構(gòu)造鏈表
java是面向?qū)ο笳Z言，實現(xiàn)鏈表很容易。我們首先用一個嵌套類來定義節(jié)點的抽象數(shù)據(jù)類型private class Node{
Item item;
Node next;
}
現(xiàn)在我們需要構(gòu)造一條含有one,two,three的鏈表，我們首先為每個元素創(chuàng)造一個節(jié)點
Node first = new Node();
Node second = new Node();
Node third = new Node();
將每個節(jié)點的item域設(shè)為所需的值
first.item = "one";
second.item = "two";
third.item = "three";
然后我們設(shè)置next域來構(gòu)造鏈表
first.next = second;
second.next = third;
注：此時third的next仍為null，即被初始化的值。
鏈表的存儲方式
我們知道了如何構(gòu)造鏈表，我們再來說一下鏈表的存儲方式。
我們都知道數(shù)組在內(nèi)存中是連續(xù)分布的，但是鏈表在內(nèi)存不是連續(xù)分配的。鏈表是通過指針域的指針鏈接內(nèi)存中的各個節(jié)點。
所以鏈表在內(nèi)存中是散亂分布在內(nèi)存中的某地址上，分配機制取決于操作系統(tǒng)的內(nèi)存管理。我們可以根據(jù)下圖來進行理解。
遍歷鏈表
鏈表的遍歷我們通常使用while循環(huán)（for循環(huán)也可以但是代碼不夠簡潔）下面我們來看一下鏈表的遍歷代碼
for:
for(Node x = first;x!=null;x=x.next){
//處理x.item
}
while:
Node x = first; while(x!=null){
//處理x.item
x=x.next;
}
鏈表的幾種操作
添加節(jié)點
添加節(jié)點E，如圖所示
刪除節(jié)點
刪除B節(jié)點，如圖所示
我們只需將A節(jié)點的next指針指向C節(jié)點即可。
有的同學(xué)可能會有這種疑問，B節(jié)點這樣不會留著內(nèi)存里嗎？java含有自己的內(nèi)存回收機制，不用自己手動釋放內(nèi)存了，但是C++,則需要手動釋放。
我們通過上圖知道了刪除和插入都是O(1)操作。
鏈表和數(shù)組的比較
插入/刪除操作(時間復(fù)雜度)
查詢（時間復(fù)雜度）
存儲方式
數(shù)組
O(n)
O(1)
內(nèi)存連續(xù)分布
鏈表
O(1)
O(n)
內(nèi)存散亂分布
鏈表經(jīng)典題目
我們上周做了很多鏈表的題目，全部都是在題庫中精挑細(xì)選出來的，掌握了那些題目不僅能夠掌握了鏈表的基本操作，而且還能學(xué)到很多算法思想，以后我們再遇到鏈表的題目就可以往我們的框架上靠。
鏈表必會題目：
雙指針?biāo)枷?/span>
老鷹：我要抓走倒數(shù)第K個小雞
老鷹：一口氣吃掉一半小雞仔
兜兜轉(zhuǎn)轉(zhuǎn)還是你
遇見
合二為一
刪除節(jié)點
我們長的像是我們的錯嗎？
大家完成了這些題目應(yīng)該就會對鏈表有自己的理解了，對其他鏈表題目也不會一頭霧水了，大家記得打卡呀。
END
來源：袁廚的算法小屋，作者：程序員愛做飯
版權(quán)歸原作者所有，如有侵權(quán)，請聯(lián)系刪除。
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
