鏈表這個(gè)東西我在帶新人或者看開源代碼的時(shí)候幾乎每次都要拿出來(lái)講一遍。你可以說(shuō)它基礎(chǔ)但真要用好里面門道不少。C語(yǔ)言里沒(méi)有現(xiàn)成的容器不像C有STL的listJava有LinkedList你想在C里用鏈表就得從結(jié)構(gòu)體定義開始一步步自己造輪子。這個(gè)過(guò)程說(shuō)難不難但絕對(duì)值得走一遍因?yàn)殒湵聿恢皇菙?shù)據(jù)結(jié)構(gòu)它背后那一套內(nèi)存管理、指針操作的思維是C語(yǔ)言的核心。這篇文章的目標(biāo)很直接讓你看完之后能自己動(dòng)手寫出一個(gè)單鏈表能完成創(chuàng)建、插入、刪除、遍歷、反轉(zhuǎn)這些基本操作并且知道在什么場(chǎng)景下該用鏈表而不是數(shù)組。我會(huì)從最底層的結(jié)構(gòu)體定義開始講配合內(nèi)存視角解釋每一步代碼在干什么最后再聊聊實(shí)際項(xiàng)目中那些避開坑的經(jīng)驗(yàn)。適合剛學(xué)完C語(yǔ)言基礎(chǔ)、準(zhǔn)備進(jìn)階的同學(xué)也適合工作中遇到鏈表相關(guān)代碼但一直沒(méi)捋清楚的開發(fā)者。1. 折騰鏈表之前先想清楚數(shù)組哪里不夠用1.1 數(shù)組的存儲(chǔ)方式?jīng)Q定了它的讀寫特性很多人一開始接觸C語(yǔ)言用的最多的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組。數(shù)組在內(nèi)存里是一段連續(xù)的地址空間每個(gè)元素緊挨著排布。比如你定義int arr[10]那么arr[0]和arr[1]在內(nèi)存里相差4個(gè)字節(jié)假設(shè)int占4字節(jié)。這種連續(xù)存儲(chǔ)帶來(lái)的好處是訪問(wèn)第n個(gè)元素特別快直接算地址arr n*sizeof(int)一步到位時(shí)間復(fù)雜度O(1)。但連續(xù)存儲(chǔ)也帶來(lái)了兩個(gè)繞不開的問(wèn)題。第一個(gè)問(wèn)題創(chuàng)建數(shù)組的時(shí)候必須指定大小C語(yǔ)言里不支持動(dòng)態(tài)擴(kuò)容的數(shù)組。你預(yù)估了100個(gè)元素的容量結(jié)果業(yè)務(wù)發(fā)展了要存200個(gè)那就麻煩了。要么你一開始就開一個(gè)很大的數(shù)組浪費(fèi)內(nèi)存要么你手動(dòng)重新分配一塊更大的空間并把舊數(shù)據(jù)拷過(guò)去非常折騰。第二個(gè)問(wèn)題在數(shù)組中間插入或刪除一個(gè)元素為了保持連續(xù)性你必須把后面所有的元素都往前或往后挪一位。這個(gè)操作的代價(jià)是O(n)數(shù)據(jù)量一旦上來(lái)性能就會(huì)很難看。1.2 鏈表的思路用指針把散落的內(nèi)存串起來(lái)鏈表的思想很簡(jiǎn)單既然連續(xù)內(nèi)存有這些限制那我就不要求內(nèi)存連續(xù)了。每個(gè)節(jié)點(diǎn)各管各的用指針把它們串起來(lái)。也就是說(shuō)每個(gè)節(jié)點(diǎn)除了存數(shù)據(jù)還要存一個(gè)指針指向下一個(gè)節(jié)點(diǎn)。物理上它們可以東一個(gè)西一個(gè)但只要順著指針走就能逐個(gè)訪問(wèn)到所有節(jié)點(diǎn)。這個(gè)設(shè)計(jì)帶來(lái)什么好處首先是存儲(chǔ)空間可以動(dòng)態(tài)申請(qǐng)來(lái)一個(gè)數(shù)據(jù)就創(chuàng)建一個(gè)節(jié)點(diǎn)不會(huì)提前預(yù)判容量。其次是插入和刪除只需要修改指針的指向不需要移動(dòng)數(shù)據(jù)操作的時(shí)間復(fù)雜度是O(1)。當(dāng)然代價(jià)也明顯不能隨機(jī)訪問(wèn)。你想找第n個(gè)節(jié)點(diǎn)必須從頭開始一個(gè)個(gè)往后走復(fù)雜度O(n)而且每個(gè)節(jié)點(diǎn)需要一個(gè)指針變量會(huì)額外匯些內(nèi)存開銷。所以鏈表和數(shù)組不是誰(shuí)完全替代誰(shuí)而是取舍不同。頻繁插入刪除就用鏈表頻繁按下標(biāo)訪問(wèn)就用數(shù)組。我自己的經(jīng)驗(yàn)是很多小的工具代碼用數(shù)組就夠了但一旦涉及數(shù)據(jù)量不確定、頻繁增刪、或者需要在多個(gè)容器之間移動(dòng)數(shù)據(jù)的場(chǎng)景鏈表就會(huì)發(fā)光發(fā)熱。2. 單鏈表手把手實(shí)現(xiàn)搞懂每個(gè)指針在干嘛2.1 節(jié)點(diǎn)的結(jié)構(gòu)體怎么定義C語(yǔ)言里實(shí)現(xiàn)鏈表第一步就是定義節(jié)點(diǎn)的結(jié)構(gòu)體。最簡(jiǎn)單的單鏈表一個(gè)節(jié)點(diǎn)包含一塊數(shù)據(jù)和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。數(shù)據(jù)這塊初學(xué)者先用int就好了后面熟練了可以換成任意類型。typedef struct Node { int data; struct Node* next; } Node;注意這里struct Node* next是一個(gè)自引用指針也就是說(shuō)節(jié)點(diǎn)結(jié)構(gòu)體里存了指向另一個(gè)節(jié)點(diǎn)的地址。用typedef把struct Node重命名為Node后面寫代碼能省不少事。很多新手容易在這里卡住寫typedef struct Node { int data; Node* next; } Node;注意在結(jié)構(gòu)體內(nèi)部還不能直接用Node因?yàn)閠ypedef還沒(méi)生效必須寫成struct Node*。這里有個(gè)細(xì)節(jié)要特別留意next指針就好比一條鏈子上的環(huán)扣。鏈表能不能走下去全靠它串聯(lián)。如果某個(gè)節(jié)點(diǎn)的next指錯(cuò)了或者沒(méi)有置為NULL程序很可能會(huì)出大問(wèn)題。所以我個(gè)人習(xí)慣是每次創(chuàng)建一個(gè)節(jié)點(diǎn)后立刻把next置為NULL不給野指針一點(diǎn)機(jī)會(huì)。2.2 創(chuàng)建節(jié)點(diǎn)和初始化鏈表有了結(jié)構(gòu)體接下來(lái)就是創(chuàng)建鏈表了。創(chuàng)建鏈表有三種常見方式頭插法、尾插法、以及插入到指定位置。先從創(chuàng)建單個(gè)節(jié)點(diǎn)開始。// 創(chuàng)建一個(gè)新節(jié)點(diǎn)返回節(jié)點(diǎn)指針 Node* createNode(int data) { Node* newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(內(nèi)存分配失敗\n); return NULL; } newNode-data data; newNode-next NULL; return newNode; }這里用malloc動(dòng)態(tài)分配內(nèi)存分配完必須檢查返回值是否為NULL。很多教材里會(huì)略過(guò)這個(gè)檢查但實(shí)際工程里內(nèi)存分配失敗是會(huì)發(fā)生的尤其是長(zhǎng)時(shí)間運(yùn)行的程序。檢查一下打印個(gè)錯(cuò)誤日志總比程序莫名其妙崩掉好。接著是初始化一個(gè)空鏈表。鏈表要有個(gè)頭指針指向鏈表的第一個(gè)節(jié)點(diǎn)?？真湵淼脑掝^指針就是NULL。通常我們定義一個(gè)Node* head NULL;就代表一個(gè)空鏈表。還有一種寫法是使用帶虛擬頭節(jié)點(diǎn)的鏈表即head指向一個(gè)不存數(shù)據(jù)的哨兵節(jié)點(diǎn)它的next才真正指向第一個(gè)有效節(jié)點(diǎn)。這種寫法在鏈表為空、插入刪除第一個(gè)節(jié)點(diǎn)時(shí)處理邏輯會(huì)統(tǒng)一很多后面碰到邊界條件你就知道它的好了。2.3 頭插法和尾插法到底用哪個(gè)頭插法顧頭思義新節(jié)點(diǎn)插在鏈表頭部成為新的第一個(gè)節(jié)點(diǎn)時(shí)間復(fù)雜度O(1)。void insertAtHead(Node** head, int data) { Node* newNode createNode(data); newNode-next *head; *head newNode; }這里為什么傳Node** head而不是Node* head這是很多初學(xué)者最容易迷惑的地方。因?yàn)槲覀円薷念^指針本身的值讓它指向新節(jié)點(diǎn)。如果只傳Node* head在函數(shù)內(nèi)部修改head那只是修改了形參的副本外部真正的頭指針不會(huì)變。要想通過(guò)函數(shù)修改變量的值就必須傳地址也就是二級(jí)指針。尾插法新節(jié)點(diǎn)插在鏈表尾部。需要先找到當(dāng)前的最后一個(gè)節(jié)點(diǎn)。void insertAtTail(Node** head, int data) { Node* newNode createNode(data); if (*head NULL) { *head newNode; return; } Node* temp *head; while (temp-next ! NULL) { temp temp-next; } temp-next newNode; }尾插法的時(shí)間復(fù)雜度是O(n)因?yàn)橐闅v到末尾。如果你頻繁尾插且鏈表很長(zhǎng)性能會(huì)受影響。這時(shí)候可以額外維護(hù)一個(gè)尾指針每次插入直接接在尾指針后面再更新尾指針這樣也能做到O(1)。不過(guò)維護(hù)尾指針意味著每次插入刪除都要考慮更新它邏輯上要多操一份心。通常簡(jiǎn)單的演示代碼不會(huì)這么寫但實(shí)際項(xiàng)目里這是很常見的優(yōu)化。我個(gè)人在工程實(shí)現(xiàn)里更常用的其實(shí)是頭插法加后續(xù)處理。因?yàn)轭^插法相當(dāng)于是把鏈表反轉(zhuǎn)了一次順序在需要逆序輸出、或者不要求保持插入順序的場(chǎng)景下頭插法效率高代碼也簡(jiǎn)潔。2.4 遍歷鏈表看看到底存了什么遍歷是最基本的操作從head出發(fā)順著next指針一路走過(guò)去直到遇到NULL。理解了遍歷你就理解了鏈表的讀取邏輯。void printList(Node* head) { Node* temp head; while (temp ! NULL) { printf(%d - , temp-data); temp temp-next; } printf(NULL\n); }這里我用一個(gè)temp指針來(lái)遍歷而不是直接動(dòng)head。為什么因?yàn)閔ead是鏈表的入口一旦丟失后面所有節(jié)點(diǎn)都找不到了。很多新手在遍歷時(shí)直接head head-next;遍歷完發(fā)現(xiàn) head 變成了 NULL鏈表整個(gè)丟了。記住向鏈表中傳入頭指針的函數(shù)如果不是要修改鏈表的頭節(jié)點(diǎn)就不要去更改head的值。如果要修改那就傳二級(jí)指針。另外特別提醒一個(gè)問(wèn)題遍歷時(shí)的循環(huán)條件while (temp ! NULL)和while (temp-next ! NULL)是有區(qū)別的。前者可以訪問(wèn)到最后一個(gè)節(jié)點(diǎn)后者會(huì)在最后一個(gè)節(jié)點(diǎn)就停下來(lái)。在鏈表操作中到底是停在最后一個(gè)節(jié)點(diǎn)還是越過(guò)后一個(gè)節(jié)點(diǎn)當(dāng)終點(diǎn)取決于你要干什么。比如你要找倒數(shù)第二個(gè)節(jié)點(diǎn)用后者你要打印所有節(jié)點(diǎn)用前者。這個(gè)邊界條件寫代碼之前心里先有個(gè)數(shù)。3. 鏈表操作的幾個(gè)重點(diǎn)與難點(diǎn)逐個(gè)突破3.1 按值刪除節(jié)點(diǎn)邊界條件一個(gè)都不能少刪除節(jié)點(diǎn)是鏈表操作里最容易出錯(cuò)的尤其是按值刪除。邏輯上要分三種情況刪的是頭節(jié)點(diǎn)、刪的是中間節(jié)點(diǎn)、刪的是尾節(jié)點(diǎn)。雖然中間和尾可以合在一起處理但新手拆開理解比較容易。Node* deleteByValue(Node* head, int value) { Node* temp head; Node* prev NULL; // 如果頭節(jié)點(diǎn)的值就是要?jiǎng)h的 while (temp ! NULL temp-data value) { head temp-next; free(temp); temp head; } // 刪除后續(xù)匹配的節(jié)點(diǎn) while (temp ! NULL) { while (temp ! NULL temp-data ! value) { prev temp; temp temp-next; } if (temp NULL) { return head; } prev-next temp-next; free(temp); temp prev-next; } return head; }這段代碼刪除了鏈表中所有等于value的節(jié)點(diǎn)而不只是第一個(gè)。這里最核心的變量是prev它記錄當(dāng)前節(jié)點(diǎn)temp的前一個(gè)節(jié)點(diǎn)。刪除temp時(shí)只要讓prev-next跳過(guò)temp指向temp-next就相當(dāng)于把temp從鏈中摘除了。摘除之后free(temp)釋放內(nèi)存然后temp prev-next繼續(xù)往后掃描。這個(gè)地方有個(gè)非常容易踩的坑如果temp是頭節(jié)點(diǎn)此時(shí)prev還是NULL不能執(zhí)行prev-next temp-next因?yàn)閜rev是空指針。所以必須先單獨(dú)處理頭節(jié)點(diǎn)的情況。這就是我在前面提到的帶虛擬頭節(jié)點(diǎn)的鏈表能簡(jiǎn)化的地方——它讓prev永不為NULL代碼邏輯可以統(tǒng)一處理。3.2 反轉(zhuǎn)鏈表筆試面試高頻題本質(zhì)是拆鏈和重連反轉(zhuǎn)鏈表也是一個(gè)特別經(jīng)典的題目。它看起來(lái)很繞但核心就一句話從頭到尾遍歷每訪問(wèn)一個(gè)節(jié)點(diǎn)就把它指向前一個(gè)節(jié)點(diǎn)。Node* reverseList(Node* head) { Node* prev NULL; Node* current head; Node* next NULL; while (current ! NULL) { next current-next; // 先保存下一個(gè)節(jié)點(diǎn) current-next prev; // 反轉(zhuǎn)指針 prev current; // prev 后移 current next; // current 后移 } return prev; // 遍歷結(jié)束prev 就是新的頭節(jié)點(diǎn) }理解這段代碼核心是搞清楚三指針的推進(jìn)過(guò)程。current指向當(dāng)前正在處理的節(jié)點(diǎn)prev指向已經(jīng)處理好的那部分鏈表的頭節(jié)點(diǎn)即當(dāng)前節(jié)點(diǎn)的前一個(gè)next則提前把即將要處理的節(jié)點(diǎn)保存下來(lái)。為什么要保存next因?yàn)閏urrent-next prev這一步會(huì)把當(dāng)前節(jié)點(diǎn)的 next 指針給覆蓋掉如果不提前保存后面就找不到原來(lái)的下一個(gè)節(jié)點(diǎn)了鏈表就斷了。反轉(zhuǎn)這個(gè)操作我用一句話總結(jié)它考驗(yàn)的不是語(yǔ)法而是你能不能在心里畫出三個(gè)指針在鏈上移動(dòng)的過(guò)程。畫不出來(lái)就動(dòng)手比喻比如你有一串珠子你想倒著串每次拿起一個(gè)珠子把它前面的線換到后面。建議新手在紙上畫出幾個(gè)節(jié)點(diǎn)的初始和每步變化圖多畫幾次就通了。3.3 檢測(cè)環(huán)、找中間節(jié)點(diǎn)快慢指針經(jīng)典應(yīng)用除了基本操作鏈表還有一些進(jìn)階技巧最典型的是快慢指針。快指針一次走兩步慢指針一次走一步。兩個(gè)指針一起從頭出發(fā)如果鏈表有環(huán)快慢指針一定會(huì)相遇如果沒(méi)環(huán)快指針會(huì)先走到NULL。int hasCycle(Node* head) { Node* slow head; Node* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (slow fast) { return 1; } } return 0; }循環(huán)條件里為什么是fast ! NULL fast-next ! NULL因?yàn)榭熘羔樢淮巫邇刹饺绻幌却_認(rèn) fast 和 fast-next 都不為空直接訪問(wèn)fast-next-next就會(huì)訪問(wèn)空指針程序直接崩潰。這個(gè)邊界條件的理解要比死記重要得多。還有找鏈表的中間節(jié)點(diǎn)也是快慢指針快指針走兩步慢指針走一步當(dāng)快指針到達(dá)末尾時(shí)慢指針剛好在中間?？炻羔樀乃枷朐诤芏噫湵砗蛿?shù)組類問(wèn)題上都能用到值得花時(shí)間掌握。4. 雙鏈表和循環(huán)鏈表什么時(shí)候值得升級(jí)4.1 雙鏈表的定義和插入刪除優(yōu)化單鏈表只有一個(gè)方向的指針從某個(gè)節(jié)點(diǎn)只能往后走不能回頭。所以如果你想刪除某個(gè)已知節(jié)點(diǎn)卻不知道它的前一個(gè)節(jié)點(diǎn)只能從頭遍歷來(lái)找它的前趨時(shí)間復(fù)雜度O(n)。雙鏈表就是來(lái)解決這個(gè)問(wèn)題的每個(gè)節(jié)點(diǎn)增加一個(gè)prev指針指向前一個(gè)節(jié)點(diǎn)。這樣無(wú)論是向前還是向后遍歷都行了刪除節(jié)點(diǎn)時(shí)也能直接通過(guò)prev找到前一個(gè)節(jié)點(diǎn)。typedef struct DNode { int data; struct DNode* prev; struct DNode* next; } DNode;雙鏈表的插入和刪除寫起來(lái)比單鏈表要多幾條語(yǔ)句因?yàn)橐瑫r(shí)更新兩個(gè)方向的指針。比如在節(jié)點(diǎn)p后面插入新節(jié)點(diǎn)newNodenewNode-next p-next; newNode-prev p; if (p-next ! NULL) { p-next-prev newNode; } p-next newNode;這里一定要注意如果p-next不為空得先把p-next-prev指向新節(jié)點(diǎn)然后再改p-next。順序反了比如先執(zhí)行p-next newNode那p原來(lái)的下一個(gè)節(jié)點(diǎn)就找不到了p-next-prev就操作到新節(jié)點(diǎn)上了鏈表結(jié)構(gòu)直接損壞。雙鏈表的指針操作強(qiáng)烈建議畫圖輔助寫完代碼再對(duì)著圖走一遍檢查有沒(méi)有指針懸空。4.2 循環(huán)鏈表和約瑟夫環(huán)循環(huán)鏈表就是讓尾節(jié)點(diǎn)的next指回頭節(jié)點(diǎn)形成一個(gè)環(huán)。這個(gè)結(jié)構(gòu)在需要循環(huán)處理的場(chǎng)景里很好用比如操作系統(tǒng)進(jìn)程調(diào)度里的時(shí)間片輪轉(zhuǎn)以及約瑟夫環(huán)問(wèn)題。約瑟夫環(huán)問(wèn)題我印象很深當(dāng)時(shí)學(xué)的時(shí)候用循環(huán)鏈表解特別直觀。一群人圍成一圈從某個(gè)位置開始報(bào)數(shù)報(bào)到某個(gè)數(shù)字的人出列然后從下一個(gè)人繼續(xù)報(bào)數(shù)直到所有人出列。用循環(huán)鏈表模擬這個(gè)過(guò)程每次要?jiǎng)h除的就是當(dāng)前報(bào)數(shù)到的那個(gè)節(jié)點(diǎn)刪除后繼續(xù)往下報(bào)數(shù)非常自然。// 約瑟夫環(huán)代碼骨架 Node* josephus(Node* head, int k) { Node* p head; Node* prev NULL; // 先找到尾節(jié)點(diǎn)形成循環(huán)鏈表 // 然后循環(huán)刪除報(bào)數(shù)到 k 的節(jié)點(diǎn) while (p-next ! p) { // 找到第 k 個(gè)節(jié)點(diǎn) for (int i 1; i k; i) { prev p; p p-next; } // 刪除 p 節(jié)點(diǎn) prev-next p-next; printf(出列: %d\n, p-data); free(p); p prev-next; } // 最后剩下的就是幸存者 return p; }這個(gè)代碼看著簡(jiǎn)單但里面有很多邊界細(xì)節(jié)比如如何正確找到尾節(jié)點(diǎn)形成環(huán)尾節(jié)點(diǎn)的 next 本來(lái)指向 NULL改一下指向頭就行以及當(dāng)鏈表只剩下一個(gè)節(jié)點(diǎn)時(shí)p-next p循環(huán)就該結(jié)束。約瑟夫環(huán)是我自己比較推薦用來(lái)練手鏈表的題目它能把插入、刪除、循環(huán)遍歷、邊界判斷全都用上而且邏輯清晰很適合檢驗(yàn)自己有沒(méi)有真的掌握鏈表。4.3 內(nèi)核鏈表和高級(jí)鏈表的啟發(fā)如果你看過(guò)Linux內(nèi)核代碼會(huì)發(fā)現(xiàn)內(nèi)核里的鏈表定義方式跟上面講的完全不一樣。它不是把鏈表節(jié)點(diǎn)嵌入結(jié)構(gòu)體而是反過(guò)來(lái)結(jié)構(gòu)體里嵌一個(gè)鏈表節(jié)點(diǎn)struct list_head。這個(gè)list_head里面只包含next和prev指針通過(guò)container_of宏可以根據(jù)鏈表節(jié)點(diǎn)的地址計(jì)算出宿主結(jié)構(gòu)體的地址從而找到數(shù)據(jù)。struct list_head { struct list_head *next, *prev; }; // 用法自定義結(jié)構(gòu)體里嵌入 list_head struct my_data { int value; struct list_head list; };這種設(shè)計(jì)的妙處在于鏈表操作的代碼是通用的不管你的數(shù)據(jù)是什么類型只要你把list_head嵌進(jìn)去就能用同一套函數(shù)來(lái)管理。你用list_add插入節(jié)點(diǎn)用list_for_each遍歷完全不用為每種數(shù)據(jù)類型寫一套鏈表操作。我第一次看到這套東西的時(shí)候很震撼因?yàn)橹皩W(xué)的都是“鏈表里有數(shù)據(jù)”而內(nèi)核這種是“數(shù)據(jù)里有鏈表”思維完全反過(guò)來(lái)了。后面我做項(xiàng)目如果某個(gè)結(jié)構(gòu)體需要被多個(gè)鏈表同時(shí)管理比如同時(shí)按時(shí)間排序又按優(yōu)先級(jí)排序就會(huì)想到這種嵌入式的做法在每個(gè)結(jié)構(gòu)體里放兩個(gè)list_head分別用于不同的鏈表掛接。這種思路在你理解了基礎(chǔ)鏈表之后再去研究會(huì)打開一個(gè)新世界。5. 鏈表內(nèi)存管理和信息清理最容易泄漏的地方5.1 動(dòng)態(tài)內(nèi)存分配和釋放配對(duì)鏈表節(jié)點(diǎn)用malloc動(dòng)態(tài)申請(qǐng)用完必須釋放否則就會(huì)造成內(nèi)存泄漏。一個(gè)鏈表占用的內(nèi)存如果是幾百幾千個(gè)節(jié)點(diǎn)可能還沒(méi)什么感覺(jué)但在長(zhǎng)期運(yùn)行的服務(wù)器進(jìn)程里頻繁創(chuàng)建銷毀鏈表而不釋放內(nèi)存占用會(huì)一路飆升最終導(dǎo)致程序被系統(tǒng)殺掉或者卡死。釋放整個(gè)鏈表的操作用遞歸寫也可以但更推薦循環(huán)寫法因?yàn)檫f歸深度太深會(huì)有棧溢出的風(fēng)險(xiǎn)。void freeList(Node* head) { Node* temp; while (head ! NULL) { temp head; head head-next; free(temp); } }這個(gè)循環(huán)的寫法很典型先用temp保存當(dāng)前要釋放的節(jié)點(diǎn)然后把head往后移再釋放temp。順序不能顛倒必須先保存下一個(gè)節(jié)點(diǎn)再釋放當(dāng)前節(jié)點(diǎn)否則釋放之后你再訪問(wèn)head-next讀到的就是已經(jīng)釋放的內(nèi)存。5.2 懸空指針問(wèn)題懸空指針英文叫 dangling pointer指的是指針指向的內(nèi)存已經(jīng)被釋放了但指針本身還保存著那個(gè)地址。這時(shí)如果再去訪問(wèn)這個(gè)指針行為是未定義的?？赡芘銮蛇€能讀到舊數(shù)據(jù)也可能程序崩潰還可能把那塊內(nèi)存覆蓋成別的內(nèi)容查起來(lái)非常難。防止懸空指針最好的辦法是在釋放內(nèi)存后立刻把指針置為NULL。比如free(temp); temp NULL;這樣如果后面不小心又訪問(wèn)了這個(gè)指針你至少能通過(guò)檢查temp NULL發(fā)現(xiàn)問(wèn)題而不是對(duì)著一個(gè)野指針瞎調(diào)半宿。這也是我一直強(qiáng)調(diào)的free和 置NULL是兩件事缺一不可。5.3 內(nèi)存泄漏的排查工具程序跑著跑著內(nèi)存越來(lái)越大怎么定位是不是鏈表泄漏了Linux 上用valgrind就很方便。編譯的時(shí)候帶-g選項(xiàng)保留調(diào)試信息然后跑valgrind --leak-checkfull ./your_program它會(huì)把泄漏的內(nèi)存分配位置和大小全部打印出來(lái)。我在做 C 項(xiàng)目的時(shí)候幾乎每跑一個(gè)程序都要用 valgrind 過(guò)一遍能省去很多后面排查的力氣。除了 valgrindAddressSanitizer也很好用。編譯時(shí)加上-fsanitizeaddress在代碼執(zhí)行到越界訪問(wèn)或者釋放后再訪問(wèn)的地方會(huì)立刻報(bào)錯(cuò)定位問(wèn)題比 valgrind 更快。這個(gè)工具在本地開發(fā)、CI 檢查里都很值得配置上。6. 鏈表應(yīng)用場(chǎng)景盤點(diǎn)面試題之外的實(shí)戰(zhàn)價(jià)值6.1 操作系統(tǒng)和底層軟件中的鏈表鏈表離我們不遠(yuǎn)。操作系統(tǒng)內(nèi)部大量使用了鏈表比如進(jìn)程控制塊PCB的管理所有進(jìn)程通過(guò)鏈表串起來(lái)方便遍歷調(diào)度。文件系統(tǒng)里空閑塊的管理也可以用鏈表來(lái)串接。設(shè)備驅(qū)動(dòng)中的緩存、請(qǐng)求隊(duì)列也常見鏈表的影子。C 語(yǔ)言下的很多基礎(chǔ)庫(kù)比如 glib 里的 GList、GQueueepoll 事件的就緒隊(duì)列等本質(zhì)上也是鏈表或者以鏈表作為底層結(jié)構(gòu)。對(duì)做后端開發(fā)或者基礎(chǔ)軟件的人來(lái)說(shuō)鏈表不是面試?yán)锏囊坏李}而是每天都會(huì)碰到的現(xiàn)實(shí)。6.2 業(yè)務(wù)設(shè)計(jì)中鏈表的實(shí)際用法業(yè)務(wù)層面上凡是“不確定數(shù)量、頻繁增刪、有序遍歷”的場(chǎng)景都可以考慮鏈表。比如在線用戶列表用戶隨時(shí)上線和下線用鏈表管理很合適。消息隊(duì)列的實(shí)現(xiàn)如果用數(shù)組的話頭部出隊(duì)要整體移動(dòng)用鏈表則隊(duì)頭出隊(duì)只要改指針。LRU 緩存淘汰算法經(jīng)典實(shí)現(xiàn)之一是“哈希表雙鏈表”雙鏈表用來(lái)記錄訪問(wèn)順序每次訪問(wèn)就把節(jié)點(diǎn)移到鏈表頭部淘汰時(shí)從尾部刪除這個(gè)結(jié)構(gòu)很多語(yǔ)言里的 OrderedDict 就是這么實(shí)現(xiàn)的。還有在游戲開發(fā)里渲染對(duì)象的層級(jí)關(guān)系、碰撞檢測(cè)中動(dòng)態(tài)實(shí)體集合的管理用鏈表往往比用數(shù)組更靈活。當(dāng)然現(xiàn)代游戲引擎有更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)但鏈表思想依然在里面起著基礎(chǔ)作用。6.3 鏈表選型的后半段建議說(shuō)句實(shí)在話也不要神話鏈表。C 語(yǔ)言里沒(méi)有現(xiàn)成的高層容器鏈表因?yàn)閷?shí)現(xiàn)簡(jiǎn)單、不需要依賴第三方庫(kù)成了很多 C 項(xiàng)目的首選。但如果你的需求是頻繁按下標(biāo)訪問(wèn)或者數(shù)據(jù)量小到數(shù)組綽綽有余那直接用數(shù)組、甚至用靜態(tài)數(shù)組配合一個(gè)size變量記錄長(zhǎng)度會(huì)簡(jiǎn)單得多。數(shù)據(jù)量在幾百條以內(nèi)數(shù)組遍歷一次也就是幾微秒沒(méi)必要為了“用鏈表而用鏈表”。還有一點(diǎn)如果你的數(shù)據(jù)需要頻繁增刪但增刪的位置隨機(jī)而且你能快速定位到目標(biāo)位置鏈表的 O(1) 才有意義。如果每次增刪前都要 O(n) 查找位置那總代價(jià)還是 O(n)這時(shí)候用平衡樹、哈希表之類的結(jié)構(gòu)可能更合適。選型這件事永遠(yuǎn)是需求優(yōu)先。7. 常見問(wèn)題排查鏈表代碼寫崩了怎么定位以下是常見問(wèn)題速查表也是我過(guò)去幾年里被問(wèn)過(guò)最多的問(wèn)題癥狀可能原因排查思路程序崩潰 segmentation fault訪問(wèn)了 NULL 指針或野指針檢查循環(huán)條件打印節(jié)點(diǎn)地址確認(rèn)是否有節(jié)點(diǎn)next為NULL但沒(méi)有處理插入后鏈表順序不對(duì)頭插/尾插/指定位置插入邏輯混亂畫圖走一遍代碼確認(rèn)prev-next和temp-next的賦值順序鏈表遍歷之后 head 丟了遍歷時(shí)直接改了 head 值遍歷使用臨時(shí)指針temp head不要?jiǎng)釉?head刪除節(jié)點(diǎn)后鏈表斷了前一個(gè)節(jié)點(diǎn)的 next 沒(méi)有指向被刪節(jié)點(diǎn)的 next用prev-next temp-next;代替prev temp-next;程序運(yùn)行時(shí)間長(zhǎng)了內(nèi)存暴漲動(dòng)態(tài)分配的節(jié)點(diǎn)沒(méi)有 free用 valgrind/ASan 檢查泄漏位置確認(rèn) free 和 malloc 配對(duì)反轉(zhuǎn)鏈表后只剩兩個(gè)節(jié)點(diǎn)三指針中next保存時(shí)機(jī)不對(duì)每步先保存next current-next再修改current-next判斷鏈表是否有環(huán)時(shí)死循環(huán)快慢指針移動(dòng)條件處理不當(dāng)確認(rèn)fast ! NULL fast-next ! NULL這里邊最常見的恐怕還是刪除節(jié)點(diǎn)后鏈表斷裂的問(wèn)題。很多人刪完節(jié)點(diǎn)直接temp temp-next但此時(shí)temp已經(jīng)被free了temp-next訪問(wèn)的是已釋放的內(nèi)存程序崩潰或者在極端情況下修到了別的進(jìn)程的內(nèi)存。所以我說(shuō)寫完刪除節(jié)點(diǎn)的函數(shù)一定要在腦海里或者畫圖走一遍確認(rèn)每個(gè)節(jié)點(diǎn)的指針在刪除前后都指向正確的位置。8. 一次完整的鏈表項(xiàng)目實(shí)踐通訊錄管理系統(tǒng)8.1 需求拆解與結(jié)構(gòu)設(shè)計(jì)講了這么多理論來(lái)一個(gè)完整的實(shí)踐項(xiàng)目把鏈表串起來(lái)用一遍。這個(gè)項(xiàng)目是很多學(xué)校的C語(yǔ)言課程設(shè)計(jì)用鏈表實(shí)現(xiàn)一個(gè)簡(jiǎn)單的通訊錄。功能包括添加聯(lián)系人、刪除聯(lián)系人、查找聯(lián)系人、修改聯(lián)系人和按姓名排序。先定義通訊錄的數(shù)據(jù)結(jié)構(gòu)這里我直接用一個(gè)雙鏈表因?yàn)榻?jīng)常需要向前遍歷按姓名排序時(shí)前后交換節(jié)點(diǎn)方便typedef struct Contact { char name[50]; char phone[20]; struct Contact* prev; struct Contact* next; } Contact;8.2 核心功能的實(shí)現(xiàn)邏輯添加聯(lián)系人時(shí)不從頭插也不從尾插而是按照姓名字典序插入這樣通訊錄天然有序查找和展示都方便。插入的核心邏輯就是在鏈表中找到合適的位置然后進(jìn)行雙向鏈表的指針修改。代碼如下void addContact(Contact** head, const char* name, const char* phone) { Contact* newNode (Contact*)malloc(sizeof(Contact)); strcpy(newNode-name, name); strcpy(newNode-phone, phone); newNode-prev NULL; newNode-next NULL; if (*head NULL) { *head newNode; return; } // 如果新節(jié)點(diǎn)應(yīng)該插在頭節(jié)點(diǎn)前面 if (strcmp(newNode-name, (*head)-name) 0) { newNode-next *head; (*head)-prev newNode; *head newNode; return; } Contact* temp *head; // 找到第一個(gè)比新節(jié)點(diǎn)名字大的節(jié)點(diǎn) while (temp-next ! NULL strcmp(temp-next-name, newNode-name) 0) { temp temp-next; } // 插入到 temp 后面 newNode-next temp-next; if (temp-next ! NULL) { temp-next-prev newNode; } newNode-prev temp; temp-next newNode; }這里strcmp是字符串比較函數(shù)按字典序比較。這個(gè)插入邏輯涵蓋了四種情況鏈表為空、插在頭部、插在中間、插在尾部。判斷條件temp-next ! NULL strcmp(temp-next-name, newNode-name) 0表示只要下一個(gè)節(jié)點(diǎn)存在并且下一個(gè)節(jié)點(diǎn)的名字比新節(jié)點(diǎn)的名字小就繼續(xù)往后走。循環(huán)結(jié)束時(shí)要么temp-next為空新節(jié)點(diǎn)比所有現(xiàn)有節(jié)點(diǎn)名字都大插在尾部要么temp-next-name大于等于新節(jié)點(diǎn)的名字插在中間。8.3 從項(xiàng)目中學(xué)到什么這個(gè)項(xiàng)目雖然簡(jiǎn)單但把鏈表的增刪改查、排序、遍歷、內(nèi)存釋放全部覆蓋了。更重要的是它能幫助你養(yǎng)成“先畫圖再寫代碼”的習(xí)慣。很多初學(xué)者寫鏈表經(jīng)常一個(gè)函數(shù)調(diào)半天就是因?yàn)樾睦餂](méi)有鏈表的內(nèi)存圖。寫鏈表代碼之前先把要操作的節(jié)點(diǎn)和指針變化在紙上畫出來(lái)代碼寫起來(lái)就是照著圖填語(yǔ)句準(zhǔn)確率會(huì)大幅提升。做完這個(gè)項(xiàng)目后你可以試著把它升級(jí)比如改成按電話號(hào)碼查找增加分組管理的功能或者把數(shù)據(jù)持久化到文件里重啟程序還能恢復(fù)。這些擴(kuò)展都會(huì)逼迫你去深入思考鏈表和實(shí)際需求的結(jié)合方式。9. 我對(duì)鏈表學(xué)習(xí)路徑的幾點(diǎn)心得寫代碼這件事光看不寫是永遠(yuǎn)學(xué)不會(huì)的。鏈表尤其如此因?yàn)樗暮诵氖莾?nèi)存和指針的抽象思維這種能力只能通過(guò)親手實(shí)現(xiàn)來(lái)建立。我的建議路徑是先用單鏈表實(shí)現(xiàn)一遍增刪改查再用雙鏈表實(shí)現(xiàn)一遍然后用循環(huán)鏈表解決約瑟夫環(huán)問(wèn)題最后理解和模仿內(nèi)核鏈表的設(shè)計(jì)。每一步都在前一步的基礎(chǔ)上增加新的復(fù)雜度走得比較穩(wěn)。調(diào)試鏈表代碼強(qiáng)烈建議打印大法配合指針地址一起看。比如遍歷時(shí)不僅打印data順便把temp和temp-next的地址也打出來(lái)你能非常直觀地看到鏈表的走向和指針之間的關(guān)系往往一眼就能定位斷鏈的位置。有時(shí)候看代碼看了半天沒(méi)發(fā)現(xiàn)問(wèn)題一打印地址就明白了。最后說(shuō)一句鏈表是理解很多復(fù)雜數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。樹、圖這些更復(fù)雜的結(jié)構(gòu)本質(zhì)上都是鏈表節(jié)點(diǎn)的多向延伸。你把鏈表的指針操作練得滾瓜爛熟了后面學(xué)二叉樹、平衡樹、圖遍歷難度都會(huì)斷崖式下降。這個(gè)基本功值得你花時(shí)間好好打。