數(shù)組需要一塊連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)，對(duì)內(nèi)存的要求比較高。如果我們申請(qǐng)一個(gè) 100MB 大小的數(shù)組，當(dāng)內(nèi)存中沒(méi)有連續(xù)的、足夠大的存儲(chǔ)空間時(shí)，即便內(nèi)存的剩余總可用空間大于 100MB，仍然會(huì)申請(qǐng)失敗。
而鏈表恰恰相反，它并不需要一塊連續(xù)的內(nèi)存空間，它通過(guò)“指針”將一組零散的內(nèi)存塊串聯(lián)起來(lái)使用，所以如果我們申請(qǐng)的是 100MB 大小的鏈表，根本不會(huì)有問(wèn)題。

三種最常見的鏈表結(jié)構(gòu)，它們分別是：?jiǎn)捂湵?、雙向鏈表和循環(huán)鏈表。

單鏈表

我們把內(nèi)存塊稱為鏈表的“結(jié)點(diǎn)”。為了將所有的結(jié)點(diǎn)串起來(lái)，每個(gè)鏈表的結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)之外，還需要記錄鏈上的下一個(gè)結(jié)點(diǎn)的地址。記錄下個(gè)結(jié)點(diǎn)地址的指針叫作后繼指針 next。

頭結(jié)點(diǎn)用來(lái)記錄鏈表的基地址。有了它，我們就可以遍歷得到整條鏈表。而尾結(jié)點(diǎn)特殊的地方是：指針不是指向下一個(gè)結(jié)點(diǎn)，而是指向一個(gè)空地址 NULL，表示這是鏈表上最后一個(gè)結(jié)點(diǎn)。
鏈表的插入和刪除是快速的：

循環(huán)鏈表

循環(huán)鏈表是一種特殊的單鏈表。循環(huán)鏈表的尾結(jié)點(diǎn)指針是指向鏈表的頭結(jié)點(diǎn)。

雙向鏈表

雙向鏈表，顧名思義，它支持兩個(gè)方向，每個(gè)結(jié)點(diǎn)不止有一個(gè)后繼指針 next 指向后面的結(jié)點(diǎn)，還有一個(gè)前驅(qū)指針 prev 指向前面的結(jié)點(diǎn)。

雙向鏈表適合解決哪種問(wèn)題呢

雙向鏈表在某些情況下的插入、刪除等操作都要比單鏈表簡(jiǎn)單、高效。

刪除

• 刪除結(jié)點(diǎn)中“值等于某個(gè)給定值”的結(jié)點(diǎn)；
• 刪除給定指針指向的結(jié)點(diǎn)。

對(duì)于第一種情況，不管是單鏈表還是雙向鏈表，為了查找到值等于給定值的結(jié)點(diǎn)，都需要從頭結(jié)點(diǎn)開始一個(gè)一個(gè)依次遍歷對(duì)比，直到找到值等于給定值的結(jié)點(diǎ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，說(shuō)明 p 是 q 的前驅(qū)結(jié)點(diǎn)。但是對(duì)于雙向鏈表來(lái)說(shuō)，這種情況就比較有優(yōu)勢(shì)了。因?yàn)殡p向鏈表中的結(jié)點(diǎn)已經(jīng)保存了前驅(qū)結(jié)點(diǎn)的指針，不需要像單鏈表那樣遍歷。所以，針對(duì)第二種情況，單鏈表刪除操作需要 O(n) 的時(shí)間復(fù)雜度，而雙向鏈表只需要在 O(1) 的時(shí)間復(fù)雜度內(nèi)就搞定了！

對(duì)于一個(gè)有序鏈表，雙向鏈表的按值查詢的效率也要比單鏈表高一些。因?yàn)椋覀兛梢杂涗浬洗尾檎业奈恢?p，每次查詢時(shí)，根據(jù)要查找的值與 p 的大小關(guān)系，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)。

用空間換時(shí)間的設(shè)計(jì)思想

如果我們更加追求代碼的執(zhí)行速度，我們就可以選擇空間復(fù)雜度相對(duì)較高、但時(shí)間復(fù)雜度相對(duì)很低的算法或者數(shù)據(jù)結(jié)構(gòu)。相反，如果內(nèi)存比較緊缺，比如代碼跑在手機(jī)或者單片機(jī)上，這個(gè)時(shí)候，就要反過(guò)來(lái)用時(shí)間換空間的設(shè)計(jì)思路。
對(duì)于執(zhí)行較慢的程序，可以通過(guò)消耗更多的內(nèi)存（空間換時(shí)間）來(lái)進(jìn)行優(yōu)化；而消耗過(guò)多內(nèi)存的程序，可以通過(guò)消耗更多的時(shí)間（時(shí)間換空間）來(lái)降低內(nèi)存的消耗。

鏈表 VS 數(shù)組性能大比拼

數(shù)組簡(jiǎn)單易用，在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間，可以借助 CPU 的緩存機(jī)制，預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問(wèn)效率更高。而鏈表在內(nèi)存中并不是連續(xù)存儲(chǔ)，所以對(duì) CPU 緩存不友好，沒(méi)辦法有效預(yù)讀。
數(shù)組的缺點(diǎn)是大小固定，一經(jīng)聲明就要占用整塊連續(xù)內(nèi)存空間。如果聲明的數(shù)組過(guò)大，系統(tǒng)可能沒(méi)有足夠的連續(xù)內(nèi)存空間分配給它，導(dǎo)致“內(nèi)存不足（out of memory）”。如果聲明的數(shù)組過(guò)小，則可能出現(xiàn)不夠用的情況。這時(shí)只能再申請(qǐng)一個(gè)更大的內(nèi)存空間，把原數(shù)組拷貝進(jìn)去，非常費(fèi)時(shí)。鏈表本身沒(méi)有大小的限制，天然地支持動(dòng)態(tài)擴(kuò)容，我覺得這也是它與數(shù)組最大的區(qū)別。

如何輕松寫出正確的鏈表代碼？

技巧一：理解指針或引用的含義

不管是“指針”還是“引用”，實(shí)際上，它們的意思都是一樣的，都是存儲(chǔ)所指對(duì)象的內(nèi)存地址。
將某個(gè)變量賦值給指針，實(shí)際上就是將這個(gè)變量的地址賦值給指針，或者反過(guò)來(lái)說(shuō)，指針中存儲(chǔ)了這個(gè)變量的內(nèi)存地址，指向了這個(gè)變量，通過(guò)指針就能找到這個(gè)變量。

技巧二：警惕指針丟失和內(nèi)存泄漏

技巧三：利用哨兵簡(jiǎn)化實(shí)現(xiàn)難度

針對(duì)鏈表的插入、刪除操作，需要對(duì)插入第一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)的情況進(jìn)行特殊處理。
head=null 表示鏈表中沒(méi)有結(jié)點(diǎn)了。其中 head 表示頭結(jié)點(diǎn)指針，指向鏈表中的第一個(gè)結(jié)點(diǎn)。如果我們引入哨兵結(jié)點(diǎn)，在任何時(shí)候，不管鏈表是不是空，head 指針都會(huì)一直指向這個(gè)哨兵結(jié)點(diǎn)。我們也把這種有哨兵結(jié)點(diǎn)的鏈表叫帶頭鏈表。相反，沒(méi)有哨兵結(jié)點(diǎn)的鏈表就叫作不帶頭鏈表。

技巧四：重點(diǎn)留意邊界條件處理

經(jīng)常用來(lái)檢查鏈表代碼是否正確的邊界條件有這樣幾個(gè)：

• 如果鏈表為空時(shí)，代碼是否能正常工作？
• 如果鏈表只包含一個(gè)結(jié)點(diǎn)時(shí)，代碼是否能正常工作？
• 如果鏈表只包含兩個(gè)結(jié)點(diǎn)時(shí)，代碼是否能正常工作？
• 代碼邏輯在處理頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的時(shí)候，是否能正常工作？

技巧五：舉例畫圖，輔助思考

技巧六：多寫多練，沒(méi)有捷徑

• 單鏈表反轉(zhuǎn)
• 鏈表中環(huán)的檢測(cè)
• 兩個(gè)有序的鏈表合并
• 刪除鏈表倒數(shù)第 n 個(gè)結(jié)點(diǎn)
• 求鏈表的中間結(jié)點(diǎn)
  leetcode對(duì)應(yīng)練習(xí)題 206，141，21，19，876