相比于數(shù)組的優(yōu)勢：

數(shù)組的存儲需要連續(xù)的的內(nèi)存空間，如果我們申請一個 100MB 大小的數(shù)組，當(dāng)內(nèi)存中沒有連續(xù)的、足夠大的存儲空間時，即便內(nèi)存的剩余總可用空間大于 100MB，仍然會申請失敗。

鏈表則是通過"指針"將一組零散的內(nèi)存塊串聯(lián)起來使用，，所以如果我們申請的是 100MB 大小的鏈表，根本不會有問題。

鏈表常見的三種結(jié)構(gòu)分別為:單鏈表、雙向鏈表、循壞鏈表

單鏈表:

鏈表通過指針將一組零散的內(nèi)存塊串聯(lián)在一起。其中，我們把內(nèi)存塊稱為鏈表的“結(jié)點(diǎn)”。為了將所有的結(jié)點(diǎn)串起來，每個鏈表的結(jié)點(diǎn)除了存儲數(shù)據(jù)之外，還需要記錄鏈上的下一個結(jié)點(diǎn)的地址。如圖所示，我們把這個記錄下個結(jié)點(diǎn)地址的指針叫作后繼指針 next。

image

單鏈表

其中有兩個結(jié)點(diǎn)是比較特殊的，它們分別是第一個結(jié)點(diǎn)和最后一個結(jié)點(diǎn)。我們習(xí)慣性地把第一個結(jié)點(diǎn)叫作頭結(jié)點(diǎn)，把最后一個結(jié)點(diǎn)叫作尾結(jié)點(diǎn)。其中，頭結(jié)點(diǎn)用來記錄鏈表的基地址。有了它，我們就可以遍歷得到整條鏈表。而尾結(jié)點(diǎn)特殊的地方是：指針不是指向下一個結(jié)點(diǎn)，而是指向一個空地址 NULL，表示這是鏈表上最后一個結(jié)點(diǎn)。

單鏈表的插入、刪除、訪問的時間復(fù)雜度與數(shù)組剛好相反，單鏈表的插入、刪除的時間復(fù)雜度為o(1),訪問的時間復(fù)雜度為o(n).

image

插入、刪除操作

循環(huán)鏈表:

循環(huán)鏈表是一種特殊的單鏈表。實(shí)際上，循環(huán)鏈表也很簡單。它跟單鏈表唯一的區(qū)別就在尾結(jié)點(diǎn)。我們知道，單鏈表的尾結(jié)點(diǎn)指針指向空地址，表示這就是最后的結(jié)點(diǎn)了。而循環(huán)鏈表的尾結(jié)點(diǎn)指針是指向鏈表的頭結(jié)點(diǎn)。從我畫的循環(huán)鏈表圖中，你應(yīng)該可以看出來，它像一個環(huán)一樣首尾相連，所以叫作“循環(huán)”鏈表。

image

循環(huán)鏈表

雙向鏈表：

一個結(jié)點(diǎn)指向兩個方向，一個前驅(qū)指針指向前面的結(jié)點(diǎn)，一個后驅(qū)指針指向后面的結(jié)點(diǎn)。

這個雙向鏈表在開發(fā)中，更常用到，因?yàn)樵趩捂湵淼牟迦牒蛣h除中，(首尾不算)還要先遍歷一遍插入和刪除中結(jié)點(diǎn)的前一個結(jié)點(diǎn)，讓其指針在重新指向，時間復(fù)雜度為o(n)，而由于雙向鏈表，有指向前一結(jié)點(diǎn)的指針，就可以在o(1)的復(fù)雜度中，找到前一個結(jié)點(diǎn)從而進(jìn)行指針指向操作。

image

雙向鏈表示意圖

雙向鏈表有種用“空間換時間”的操作，因?yàn)槊總€結(jié)點(diǎn)有兩個指針，所以同樣的數(shù)據(jù)需要更多的內(nèi)存空間，但是在效率上卻更好。

最后一個是雙向循環(huán)鏈表，根據(jù)自己的數(shù)據(jù)特性選擇使用

image

雙向循環(huán)鏈表

鏈表和數(shù)組的比較

從數(shù)據(jù)量來講:

由于數(shù)組的內(nèi)存地址是連續(xù)分配的，而且申請的大小是固定，所以數(shù)組適合一些小的數(shù)據(jù)量。數(shù)組也有動態(tài)擴(kuò)容的ArrayList，但是每當(dāng)要擴(kuò)容的話就要尋找另一個地址，然后把之前的數(shù)據(jù)全部轉(zhuǎn)移到新的分配地址，所以數(shù)據(jù)量越大，這轉(zhuǎn)移的時間成本就越大。

對于鏈表來說，由于它的內(nèi)存地址是可以不連續(xù)通過指針來合成，但是由于每個結(jié)點(diǎn)有指針的存在，會讓存儲成倍上升。而且鏈表的插入、刪除會使內(nèi)存的也頻繁的創(chuàng)建和刪除，在java中會導(dǎo)致GC(垃圾回收)

從內(nèi)存的預(yù)讀來講:

數(shù)組的內(nèi)存是連續(xù)分配的，所以預(yù)讀效果好，鏈表的內(nèi)存地址不是連續(xù)分配的，所以預(yù)讀效果不好。

從隨機(jī)訪問、插入、刪除的時間復(fù)雜度講：

image

復(fù)雜度對比

代碼示例

練習(xí):

單鏈表反轉(zhuǎn)

鏈表中環(huán)的檢測

兩個有序的鏈表合并

刪除鏈表倒數(shù)第 n 個結(jié)點(diǎn)

求鏈表的中間結(jié)點(diǎn)

參考答案