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