數(shù)據(jù)結(jié)構(gòu)與算法之美 - 學(xué)習(xí)筆記

鏈表（Linked list）

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中指針鏈接次序?qū)崿F(xiàn)的

常見(jiàn)緩存淘汰策略有三種：

緩存大小有限，當(dāng)緩存被用滿(mǎn)時(shí)，哪些數(shù)據(jù)應(yīng)該被清理出去，哪些數(shù)據(jù)應(yīng)該被保留？就需要緩存淘汰策略決定

1. 先進(jìn)先出 FIFO（first in，first out）
2. 最少使用策略 LFU（least frequently used）
3. 最近最少使用策略 LRU（least recently used）

而鏈表的經(jīng)典應(yīng)用場(chǎng)景，便是 LRU 緩存淘汰算法

與數(shù)組的區(qū)別

相比數(shù)組，鏈表是稍微復(fù)雜一點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。

從底層存儲(chǔ)結(jié)構(gòu)來(lái)看：

數(shù)組需要一塊連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)，對(duì)內(nèi)存的要求比較高。可能出現(xiàn)的問(wèn)題就是：內(nèi)存總的剩余空間足夠，但是申請(qǐng)容量較大的數(shù)組時(shí)申請(qǐng)失敗;

鏈表恰恰相反，它不需要一塊連續(xù)的內(nèi)存空間，通過(guò)‘指針’將一組零散的內(nèi)存塊串聯(lián)起來(lái)使用。與數(shù)組不同，只要內(nèi)存剩余空間足夠，無(wú)論是否連續(xù)，用鏈表來(lái)申請(qǐng)空間一定會(huì)成功。但它的內(nèi)存空間比數(shù)組大了將近一倍，因?yàn)殒湵碇械拿總€(gè)結(jié)點(diǎn)不僅要存儲(chǔ)數(shù)據(jù)，還要存儲(chǔ)地址。

從使用場(chǎng)景來(lái)看：

鏈表適合插入、刪除，時(shí)間復(fù)雜度為 O(1);

數(shù)組適合查找，支持隨機(jī)訪問(wèn)，根據(jù)下標(biāo)隨機(jī)訪問(wèn)的時(shí)間復(fù)雜度為 O(1)。

常見(jiàn)的鏈表結(jié)構(gòu)：?jiǎn)捂湵?、雙鏈表、循環(huán)鏈表

單鏈表

單鏈表中的每個(gè)結(jié)點(diǎn)都必須具備兩個(gè)功能：存儲(chǔ)數(shù)據(jù)，記錄下一個(gè)結(jié)點(diǎn)的地址

把第一個(gè)結(jié)點(diǎn)叫做頭結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)叫做尾結(jié)點(diǎn)

尾結(jié)點(diǎn)的特點(diǎn):尾結(jié)點(diǎn)的后續(xù)指針 next 指向的不再是下一個(gè)結(jié)點(diǎn)。而是指向一個(gè)空地址 null

這樣做的好處是：防止尾結(jié)點(diǎn)的后續(xù)指針 next 成為一個(gè)野指針，導(dǎo)致遍歷停不下來(lái)，或者出現(xiàn)一堆本不屬于該鏈表的垃圾數(shù)據(jù)等

循環(huán)鏈表

循環(huán)鏈表是一種特殊的單鏈表

單鏈表的尾結(jié)點(diǎn)指針指向 null，循環(huán)鏈表的尾結(jié)點(diǎn)指針指向頭結(jié)點(diǎn)。所以循環(huán)鏈表也叫做單循環(huán)鏈表

當(dāng)要處理的數(shù)據(jù)具有循環(huán)結(jié)構(gòu)特點(diǎn)時(shí)，就特別適合采用循環(huán)鏈表。如，約瑟夫問(wèn)題/丟手絹問(wèn)題：N 個(gè)人圍成一個(gè)圈，從第一個(gè)開(kāi)始報(bào)數(shù)，第 M 個(gè)將被殺掉，最后剩下一人，其余都被殺掉

雙向鏈表

與單鏈表的區(qū)別：?jiǎn)捂湵淼慕Y(jié)點(diǎn)只有兩個(gè)域，數(shù)據(jù)域、存儲(chǔ)后續(xù)結(jié)點(diǎn)的指針域。雙向鏈表有三個(gè)域，數(shù)據(jù)域、存儲(chǔ)后續(xù)結(jié)點(diǎn)的指針域（next）、存儲(chǔ)前驅(qū)結(jié)點(diǎn)地址的指針域（prev）

結(jié)構(gòu)上來(lái)看，雙向鏈表支持 O(1)時(shí)間復(fù)雜度的情況下找到前驅(qū)結(jié)點(diǎn)，正是這樣的特點(diǎn)，雙向鏈表在某些情況下的插入、刪除等操作都比單鏈表簡(jiǎn)單、高效

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

當(dāng)內(nèi)存空間充足的時(shí)候，如果更加追求代碼的執(zhí)行速度，可以選擇空間復(fù)雜度相對(duì)較高、但時(shí)間復(fù)雜度相對(duì)很低的算法或者數(shù)據(jù)結(jié)構(gòu)。相反，如果內(nèi)存比較緊缺，比如代碼跑在手機(jī)或者單片機(jī)上，就要用時(shí)間換空間的設(shè)計(jì)思路

寫(xiě)出正確鏈表代碼技巧

理解指針或引用的含義

將某個(gè)變量賦值給指針，實(shí)際上就是將這個(gè)變量的地址賦值給指針（指針存儲(chǔ)的是變量的內(nèi)存地址）

警惕指針丟失和內(nèi)存泄露

內(nèi)存泄露：
申請(qǐng)內(nèi)存空間進(jìn)行使用，用完之后忘記歸還，并且申請(qǐng)的那塊內(nèi)存空間自己也訪問(wèn)不了（可能是將地址弄丟了），而系統(tǒng)也沒(méi)辦法把他分給需要的程序

內(nèi)存溢出：
1.要求分配的內(nèi)存超出系統(tǒng)能夠給與的，系統(tǒng)不能滿(mǎn)足，于是產(chǎn)生溢出。
2.申請(qǐng) int 大小的內(nèi)存，但存放 long 大小的數(shù)據(jù)，導(dǎo)致內(nèi)存不夠用，也會(huì)產(chǎn)生內(nèi)存溢出

示例：在ab結(jié)點(diǎn)之間插入x

p->next = x;  // 將p的next指針指向x結(jié)點(diǎn)；
x->next = p->next;  // 將x的結(jié)點(diǎn)的next指針指向b結(jié)點(diǎn)；

p->next 指針在完成第一步操作之后，已經(jīng)不再指向結(jié)點(diǎn) b 了，而是指向結(jié)點(diǎn) x。第 2 行代碼相當(dāng)于將 x 賦值給 x->next，自己指向自己。因此，整個(gè)鏈表也就斷成了兩半，從結(jié)點(diǎn) b 往后的所有結(jié)點(diǎn)都無(wú)法訪問(wèn)到了

在插入結(jié)點(diǎn)時(shí)，要注意操作順序。防止丟失指針，導(dǎo)致內(nèi)存泄露。示例代碼順序顛倒即正確

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

如果我們引入哨兵結(jié)點(diǎn)，在任何時(shí)候，不管鏈表是不是空，head 指針都會(huì)一直指向這個(gè)哨兵結(jié)點(diǎn)。我們也把這種有哨兵結(jié)點(diǎn)的鏈表叫帶頭鏈表。相反，沒(méi)有哨兵結(jié)點(diǎn)的鏈表就叫作不帶頭鏈表

哨兵結(jié)點(diǎn)是不存儲(chǔ)數(shù)據(jù)的。因?yàn)樯诒Y(jié)點(diǎn)一直存在，所以插入第一個(gè)結(jié)點(diǎn)和插入其他結(jié)點(diǎn)，刪除最后一個(gè)結(jié)點(diǎn)和刪除其他結(jié)點(diǎn)，都可以統(tǒng)一為相同的代碼實(shí)現(xiàn)邏輯了

重點(diǎn)留意邊界條件處理

判斷鏈表代碼是否正確的邊界條件：

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

舉例畫(huà)圖，賦值思考

多寫(xiě)多練，沒(méi)有捷徑

五個(gè)常見(jiàn)的鏈表操作

序號(hào)對(duì)應(yīng) Leetcode 上題序

1. 單鏈表反轉(zhuǎn) 206
2. 鏈表中環(huán)的檢測(cè) 141
3. 兩個(gè)有序的鏈表合并 21
4. 刪除鏈表倒數(shù)第 n 個(gè)結(jié)點(diǎn) 19
5. 求鏈表的中間結(jié)點(diǎn) 876

這里簡(jiǎn)述一下我的解題方式，具體代碼實(shí)現(xiàn)移步下篇

單鏈表反轉(zhuǎn)：

創(chuàng)建三個(gè)指針，prev 指向前一個(gè)結(jié)點(diǎn)（反轉(zhuǎn)鏈表頭）、cur 當(dāng)前待反轉(zhuǎn)結(jié)點(diǎn)、next 待反轉(zhuǎn)下一個(gè)結(jié)點(diǎn)，主要作用為存儲(chǔ)指針，避免造成內(nèi)存泄露

遍歷鏈表，next 存儲(chǔ)下一個(gè)結(jié)點(diǎn)、更改 cur 指針指向、更改前結(jié)點(diǎn)、更新當(dāng)前待反轉(zhuǎn)結(jié)點(diǎn)

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

遍歷鏈表，給每個(gè)結(jié)點(diǎn)做標(biāo)記，當(dāng)標(biāo)記結(jié)點(diǎn)在下一次出現(xiàn)，則有環(huán)

兩個(gè)有序的鏈表合并：

創(chuàng)建兩個(gè)指針，新鏈表（存儲(chǔ)合并鏈表），不斷比較兩個(gè)排序鏈表頭結(jié)點(diǎn)，將較小結(jié)點(diǎn)放入合并鏈表中，移動(dòng)被放入結(jié)點(diǎn)的鏈表指針

當(dāng)兩個(gè)鏈表中指針存在指向 null 時(shí)，將另一個(gè)鏈表接到排列完成的鏈表之后，排列結(jié)束

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

創(chuàng)建兩個(gè)指針，快指針走 n+1 步后，慢指針開(kāi)始走，直至快指針走到底

此時(shí)，慢指針位置為倒數(shù)第 n+1 個(gè)結(jié)點(diǎn)，操作這個(gè)結(jié)點(diǎn)的 next 指向下下個(gè)結(jié)點(diǎn)

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

創(chuàng)建兩個(gè)指針，快指針每次走兩步，慢指針每次走一步，當(dāng)快指針走到底時(shí)，慢指針位置為中間結(jié)點(diǎn)位置