數(shù)組在內(nèi)存中是連續(xù)空間肄鸽，根據(jù)下標(biāo)查找，時(shí)間復(fù)雜度是O(1)
鏈表在內(nèi)存中是非連續(xù)空間油啤，元素遍歷查找要從頭結(jié)點(diǎn)開始典徘。如果要插入、刪除元素益咬，也需要先遍歷鏈表烂斋，在執(zhí)行插入、刪除操作吧础废。確實(shí)可以根據(jù)下標(biāo)進(jìn)行增刪，如何方便了罕模？
鏈表：在內(nèi)存中是零散內(nèi)存卡串聯(lián)起來使用评腺。內(nèi)存卡稱為鏈表的“結(jié)點(diǎn)”，結(jié)點(diǎn)一是存儲(chǔ)數(shù)據(jù)淑掌，二是存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址蒿讥。把記錄下一個(gè)結(jié)點(diǎn)的地址叫做后繼指針 next；
????介紹三種最常見的鏈表結(jié)構(gòu)，它們分別是：單鏈表芋绸、雙向鏈表和循環(huán)鏈表媒殉。
? ? 單鏈表：頭結(jié)點(diǎn)的后繼指針用來記錄鏈表的基地址，有了它摔敛，就能遍歷得到整個(gè)鏈表廷蓉。尾節(jié)點(diǎn)指針不是指向下一個(gè)結(jié)點(diǎn)，而是指向一個(gè)空地址NULL马昙，表示鏈表上最后一個(gè)結(jié)點(diǎn)桃犬。
與數(shù)組一樣，鏈表也支持?jǐn)?shù)據(jù)的查找行楞、插入和刪除操作攒暇。
我們知道，在進(jìn)行數(shù)組的插入子房、刪除操作時(shí)形用，為了保持內(nèi)存數(shù)據(jù)的連續(xù)性，需要做大量的數(shù)據(jù)搬移证杭，所以時(shí)間復(fù)雜度是 O(n)田度。而在鏈表中插入或者刪除一個(gè)數(shù)據(jù)，我們并不需要為了保持內(nèi)存的連續(xù)性而搬移結(jié)點(diǎn)躯砰，因?yàn)殒湵淼拇鎯?chǔ)空間本身就不是連續(xù)的每币。所以，在鏈表中插入和刪除一個(gè)數(shù)據(jù)是非匙列快速的兰怠。//為什么鏈表插入刪除操作數(shù)據(jù)快，要插入刪除不先進(jìn)行遍歷嗎
針對(duì)鏈表的插入和刪除操作李茫，我們只需要考慮相鄰結(jié)點(diǎn)的指針改變揭保，所以對(duì)應(yīng)的時(shí)間復(fù)雜度是 O(1)。
鏈表要想隨機(jī)訪問第 k 個(gè)元素魄宏，就沒有數(shù)組那么高效了秸侣。因?yàn)殒湵碇械臄?shù)據(jù)并非連續(xù)存儲(chǔ)的，所以無法像數(shù)組那樣宠互，根據(jù)首地址和下標(biāo)味榛，通過尋址公式就能直接計(jì)算出對(duì)應(yīng)的內(nèi)存地址，而是需要根據(jù)指針一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)地依次遍歷予跌，直到找到相應(yīng)的結(jié)點(diǎn)搏色。
鏈表隨機(jī)訪問的性能沒有數(shù)組好，需要 O(n) 的時(shí)間復(fù)雜度券册。
循環(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)該可以看出來秽之，它像一個(gè)環(huán)一樣首尾相連当娱，所以叫作“循環(huán)”鏈表。
????雙向鏈表考榨，顧名思義跨细，它支持兩個(gè)方向，每個(gè)結(jié)點(diǎn)不止有一個(gè)后繼指針 next 指向后面的結(jié)點(diǎn)河质，還有一個(gè)前驅(qū)指針 prev 指向前面的結(jié)點(diǎn)冀惭。
? ?
雙向鏈表需要額外的兩個(gè)空間來存儲(chǔ)后繼結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)的地址。所以掀鹅，如果存儲(chǔ)同樣多的數(shù)據(jù)散休，雙向鏈表要比單鏈表占用更多的內(nèi)存空間。雖然兩個(gè)指針比較浪費(fèi)存儲(chǔ)空間乐尊，但可以支持雙向遍歷戚丸，這樣也帶來了雙向鏈表操作的靈活性。
雙向鏈表可解決的問題：
從結(jié)構(gòu)上來看扔嵌，雙向鏈表可以支持 O(1) 時(shí)間復(fù)雜度的情況下找到前驅(qū)結(jié)點(diǎn)限府，正是這樣的特點(diǎn)，也使雙向鏈表在某些情況下的插入痢缎、刪除等操作都要比單鏈表簡單胁勺、高效。
我們先來看刪除操作独旷。
在實(shí)際的軟件開發(fā)中署穗，從鏈表中刪除一個(gè)數(shù)據(jù)無外乎這兩種情況：
刪除結(jié)點(diǎn)中“值等于某個(gè)給定值”的結(jié)點(diǎn)；
刪除給定指針指向的結(jié)點(diǎn)嵌洼。
對(duì)于第一種情況案疲，不管是單鏈表還是雙向鏈表，為了查找到值等于給定值的結(jié)點(diǎn)麻养，都需要從頭結(jié)點(diǎn)開始一個(gè)一個(gè)依次遍歷對(duì)比褐啡，直到找到值等于給定值的結(jié)點(diǎn)，然后再通過我前面講的指針操作將其刪除回溺。
盡管單純的刪除操作時(shí)間復(fù)雜度是 O(1)春贸，但遍歷查找的時(shí)間是主要的耗時(shí)點(diǎn)，對(duì)應(yīng)的時(shí)間復(fù)雜度為 O(n)遗遵。根據(jù)時(shí)間復(fù)雜度分析中的加法法則萍恕，刪除值等于給定值的結(jié)點(diǎn)對(duì)應(yīng)的鏈表操作的總時(shí)間復(fù)雜度為 O(n)。
對(duì)于第二種情況车要，我們已經(jīng)找到了要?jiǎng)h除的結(jié)點(diǎn)允粤，但是刪除某個(gè)結(jié)點(diǎn) q 需要知道其前驅(qū)結(jié)點(diǎn)，而單鏈表并不支持直接獲取前驅(qū)結(jié)點(diǎn)翼岁，所以类垫，為了找到前驅(qū)結(jié)點(diǎn)，我們還是要從頭結(jié)點(diǎn)開始遍歷鏈表琅坡，直到 p->next=q悉患，說明 p 是 q 的前驅(qū)結(jié)點(diǎn)。
但是對(duì)于雙向鏈表來說榆俺，這種情況就比較有優(yōu)勢了售躁。因?yàn)殡p向鏈表中的結(jié)點(diǎn)已經(jīng)保存了前驅(qū)結(jié)點(diǎn)的指針，不需要像單鏈表那樣遍歷茴晋。所以陪捷，針對(duì)第二種情況，單鏈表刪除操作需要 O(n) 的時(shí)間復(fù)雜度诺擅，而雙向鏈表只需要在 O(1) 的時(shí)間復(fù)雜度內(nèi)就搞定了市袖！
同理，如果我們希望在鏈表的某個(gè)指定結(jié)點(diǎn)前面插入一個(gè)結(jié)點(diǎn)烁涌，雙向鏈表比單鏈表有很大的優(yōu)勢苍碟。雙向鏈表可以在 O(1) 時(shí)間復(fù)雜度搞定，而單向鏈表需要 O(n) 的時(shí)間復(fù)雜度烹玉。你可以參照我剛剛講過的刪除操作自己分析一下驰怎。
除了插入、刪除操作有優(yōu)勢之外二打，對(duì)于一個(gè)有序鏈表县忌，雙向鏈表的按值查詢的效率也要比單鏈表高一些。因?yàn)榧绦В覀兛梢杂涗浬洗尾檎业奈恢?p症杏，每次查詢時(shí)，根據(jù)要查找的值與 p 的大小關(guān)系瑞信，決定是往前還是往后查找厉颤，所以平均只需要查找一半的數(shù)據(jù)。
現(xiàn)在凡简，你有沒有覺得雙向鏈表要比單鏈表更加高效呢逼友？這就是為什么在實(shí)際的軟件開發(fā)中精肃，雙向鏈表盡管比較費(fèi)內(nèi)存，但還是比單鏈表的應(yīng)用更加廣泛的原因帜乞。如果你熟悉 Java 語言司抱，你肯定用過 LinkedHashMap 這個(gè)容器。如果你深入研究 LinkedHashMap 的實(shí)現(xiàn)原理黎烈，就會(huì)發(fā)現(xiàn)其中就用到了雙向鏈表這種數(shù)據(jù)結(jié)構(gòu)习柠。
用空間換時(shí)間的設(shè)計(jì)思想
當(dāng)內(nèi)存空間充足的時(shí)候，如果我們更加追求代碼的執(zhí)行速度照棋，我們就可以選擇空間復(fù)雜度相對(duì)較高期虾、但時(shí)間復(fù)雜度相對(duì)很低的算法或者數(shù)據(jù)結(jié)構(gòu)莫换。相反，如果內(nèi)存比較緊缺，比如代碼跑在手機(jī)或者單片機(jī)上晾浴，這個(gè)時(shí)候肥惭，就要反過來用時(shí)間換空間的設(shè)計(jì)思路贯吓。
開篇緩存的例子鳞溉。緩存實(shí)際上就是利用了空間換時(shí)間的設(shè)計(jì)思想。如果我們把數(shù)據(jù)存儲(chǔ)在硬盤上膏执，會(huì)比較節(jié)省內(nèi)存驻售，但每次查找數(shù)據(jù)都要詢問一次硬盤，會(huì)比較慢更米。但如果我們通過緩存技術(shù)欺栗，事先將數(shù)據(jù)加載在內(nèi)存中，雖然會(huì)比較耗費(fèi)內(nèi)存空間征峦，但是每次數(shù)據(jù)查詢的速度就大大提高了迟几。
對(duì)于執(zhí)行較慢的程序，可以通過消耗更多的內(nèi)存（空間換時(shí)間）來進(jìn)行優(yōu)化栏笆；而消耗過多內(nèi)存的程序类腮，可以通過消耗更多的時(shí)間（時(shí)間換空間）來降低內(nèi)存的消耗。
鏈表 VS 數(shù)組性能大比拼
通過前面內(nèi)容的學(xué)習(xí)蛉加，你應(yīng)該已經(jīng)知道蚜枢，數(shù)組和鏈表是兩種截然不同的內(nèi)存組織方式。正是因?yàn)閮?nèi)存存儲(chǔ)的區(qū)別针饥，它們插入厂抽、刪除、隨機(jī)訪問操作的時(shí)間復(fù)雜度正好相反丁眼。
數(shù)組簡單易用筷凤，在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間，可以借助 CPU 的緩存機(jī)制苞七，預(yù)讀數(shù)組中的數(shù)據(jù)藐守，所以訪問效率更高挪丢。而鏈表在內(nèi)存中并不是連續(xù)存儲(chǔ)，所以對(duì) CPU 緩存不友好卢厂，沒辦法有效預(yù)讀吃靠。
數(shù)組與鏈表的區(qū)別
數(shù)組的缺點(diǎn)是大小固定，一經(jīng)聲明就要占用整塊連續(xù)內(nèi)存空間足淆。
如果聲明的數(shù)組過大，系統(tǒng)可能沒有足夠的連續(xù)內(nèi)存空間分配給它礁阁，導(dǎo)致“內(nèi)存不足（out of memory）”巧号。如果聲明的數(shù)組過小，則可能出現(xiàn)不夠用的情況姥闭。這時(shí)只能再申請(qǐng)一個(gè)更大的內(nèi)存空間丹鸿，把原數(shù)組拷貝進(jìn)去，非常費(fèi)時(shí)棚品。
鏈表本身沒有大小的限制靠欢，天然地支持動(dòng)態(tài)擴(kuò)容。
內(nèi)容小結(jié)
今天我們講了一種跟數(shù)組“相反”的數(shù)據(jù)結(jié)構(gòu)铜跑，鏈表门怪。它跟數(shù)組一樣，也是非彻模基礎(chǔ)掷空、非常常用的數(shù)據(jù)結(jié)構(gòu)。不過鏈表要比數(shù)組稍微復(fù)雜囤锉，從普通的單鏈表衍生出來好幾種鏈表結(jié)構(gòu)坦弟，比如雙向鏈表、循環(huán)鏈表官地、雙向循環(huán)鏈表酿傍。
和數(shù)組相比，鏈表更適合插入驱入、刪除操作頻繁的場景赤炒，查詢的時(shí)間復(fù)雜度較高。不過沧侥，在具體軟件開發(fā)中可霎，要對(duì)數(shù)組和鏈表的各種性能進(jìn)行對(duì)比，綜合來選擇使用兩者中的哪一個(gè)宴杀。
課后思考
如何判斷一個(gè)字符串是否是回文字符串的問題
轉(zhuǎn)自：王爭 https://time.geekbang.org/column/article/41013癣朗。
學(xué)習(xí)記錄自用。
