鏈表這塊內(nèi)容我見過太多人卡在“靜態(tài)數(shù)組能跑一到動態(tài)就懵”的階段。教材上把malloc和指針操作講得云里霧里真正上手寫的時(shí)候不是忘了給next賦值就是把頭指針弄丟導(dǎo)致整個(gè)鏈表找不回來。這篇就專門聊動態(tài)創(chuàng)建鏈表這件事重點(diǎn)拆解頭插法和尾插法這兩種最基礎(chǔ)的構(gòu)建方式把每一步的內(nèi)存變化、指針走向、以及實(shí)際寫代碼時(shí)最容易翻車的地方都攤開來講。如果你已經(jīng)會用struct定義節(jié)點(diǎn)也能看懂基本的指針運(yùn)算但一到“動態(tài)”兩個(gè)字就心里沒底那這篇就是寫給你的。1. 為什么靜態(tài)鏈表不夠用非得動態(tài)創(chuàng)建先把這個(gè)“為什么”說清楚不然后面寫代碼就是死記硬背。1.1 靜態(tài)鏈表的本質(zhì)是“數(shù)組套馬甲”很多教材講鏈表之前會先給一個(gè)用數(shù)組模擬的版本大概長這樣struct Node { int data; int next; // 存的是數(shù)組下標(biāo)不是指針 }; struct Node nodes[100];這種寫法叫靜態(tài)鏈表它的“鏈”是靠數(shù)組下標(biāo)串起來的。你仔細(xì)想一下這玩意兒的本質(zhì)還是數(shù)組只不過把“下一個(gè)元素”從i1換成了nodes[i].next。它有幾個(gè)硬傷容量寫死nodes[100]就是100個(gè)想存第101個(gè)就得改代碼重新編譯。內(nèi)存浪費(fèi)不管實(shí)際用幾個(gè)100個(gè)節(jié)點(diǎn)的空間一開始就占住了。插入刪除依然要搬數(shù)據(jù)雖然比純數(shù)組好一點(diǎn)但空閑位置的維護(hù)很別扭。所以靜態(tài)鏈表只適合那種“我知道最多就這么多而且不咋增刪”的場景。真正要靈活增刪必須讓節(jié)點(diǎn)在運(yùn)行時(shí)按需申請。1.2 動態(tài)創(chuàng)建的核心就一句話用的時(shí)候再要內(nèi)存動態(tài)鏈表的關(guān)鍵在于每個(gè)節(jié)點(diǎn)不是提前擺好的而是程序跑起來之后需要一個(gè)新的就往堆區(qū)要一塊。C語言里干這件事的函數(shù)就是malloc。struct Node *p (struct Node *)malloc(sizeof(struct Node));這行代碼干了三件事向系統(tǒng)申請一塊大小剛好夠放一個(gè)struct Node的內(nèi)存、返回這塊內(nèi)存的首地址、把這個(gè)地址強(qiáng)制轉(zhuǎn)換成struct Node *類型賦給p。從此p就指向了一個(gè)嶄新的、還沒填數(shù)據(jù)的節(jié)點(diǎn)。注意malloc返回的是void *在C里其實(shí)可以隱式轉(zhuǎn)換但顯式寫上(struct Node *)可讀性更好也能避免一些老編譯器報(bào)警告。理解了這一點(diǎn)動態(tài)創(chuàng)建鏈表就變成了一個(gè)循環(huán)每次循環(huán)要一塊內(nèi)存、填數(shù)據(jù)、然后把這塊內(nèi)存“掛”到已有的鏈上。掛的方式不同就分出了頭插法和尾插法。2. 頭插法每次新節(jié)點(diǎn)都懟到最前面頭插法的邏輯特別直白來一個(gè)新節(jié)點(diǎn)就讓它成為新的第一個(gè)節(jié)點(diǎn)。2.1 頭插法的指針操作拆解假設(shè)我們已經(jīng)有了一條鏈頭指針是head指向節(jié)點(diǎn)A。現(xiàn)在來了一個(gè)新節(jié)點(diǎn)newNode要插到最前面。操作順序是這樣的讓newNode-next指向原來的第一個(gè)節(jié)點(diǎn)也就是head指向的A。把head改成指向newNode。用代碼表示newNode-next head; head newNode;就這兩行。順序不能反。如果你先寫head newNode那原來的A就徹底找不到了因?yàn)闆]有任何指針還指著它內(nèi)存泄漏就這么來的。我用一個(gè)具體例子走一遍。假設(shè)依次插入數(shù)據(jù)1、2、3初始head NULL插入1newNode1-next NULL; head newNode1;鏈1 - NULL插入2newNode2-next newNode1; head newNode2;鏈2 - 1 - NULL插入3newNode3-next newNode2; head newNode3;鏈3 - 2 - 1 - NULL你看最后鏈表的順序和插入順序是反的。這是頭插法最顯著的特征也是它最大的“坑”——很多人插完發(fā)現(xiàn)打印出來是倒的還以為自己寫錯(cuò)了。2.2 完整的頭插法建鏈代碼#include stdio.h #include stdlib.h struct Node { int data; struct Node *next; }; struct Node *createListByHeadInsert(int arr[], int n) { struct Node *head NULL; for (int i 0; i n; i) { struct Node *newNode (struct Node *)malloc(sizeof(struct Node)); if (newNode NULL) { printf(內(nèi)存申請失敗\n); return head; } newNode-data arr[i]; newNode-next head; // 新節(jié)點(diǎn)指向當(dāng)前頭 head newNode; // 頭指針前移 } return head; }這段代碼里有個(gè)細(xì)節(jié)值得說malloc之后一定要判空。雖然在小程序里幾乎不會失敗但這是習(xí)慣問題。真到了嵌入式或者內(nèi)存緊張的環(huán)境不判空就是等著程序跑飛。2.3 頭插法什么時(shí)候用頭插法不是“劣質(zhì)版尾插法”它有自己合適的場景需要逆序比如你把一個(gè)數(shù)組正序讀進(jìn)來但后續(xù)處理需要逆序那頭插法一步到位省得再寫反轉(zhuǎn)。實(shí)現(xiàn)棧棧是后進(jìn)先出頭插法每次新元素都在最前面取的時(shí)候也從最前面取天然就是棧。插入操作頻繁且不關(guān)心順序只要求元素在鏈里順序無所謂頭插法O(1)的插入效率很香。但如果你需要保持插入順序那頭插法就是給自己找麻煩。3. 尾插法保持插入順序的正統(tǒng)做法尾插法要解決的核心問題是新節(jié)點(diǎn)掛到鏈表的末尾這樣最終順序和插入順序一致。3.1 尾插法的關(guān)鍵得有個(gè)指針一直盯著尾巴頭插法只需要一個(gè)head因?yàn)樾鹿?jié)點(diǎn)永遠(yuǎn)插在head前面。尾插法不行你得知道當(dāng)前最后一個(gè)節(jié)點(diǎn)是誰才能把新節(jié)點(diǎn)接上去。所以需要一個(gè)tail指針?；静僮鱰ail-next newNode; tail newNode; newNode-next NULL;這里newNode-next NULL特別重要。新節(jié)點(diǎn)是新的尾巴它的next必須是NULL否則鏈表的結(jié)尾就是未定義的遍歷的時(shí)候會跑到不知道什么地方去。3.2 處理空鏈表的邊界情況尾插法最容易出錯(cuò)的地方是第一條節(jié)點(diǎn)。當(dāng)head NULL時(shí)tail也是NULL你直接寫tail-next newNode就是對空指針解引用程序直接崩。正確的處理if (head NULL) { head newNode; tail newNode; } else { tail-next newNode; tail newNode; }這個(gè)分支判斷不能省。我見過不少人在紙上推演覺得沒問題一上機(jī)就段錯(cuò)誤就是栽在這里。3.3 完整的尾插法建鏈代碼struct Node *createListByTailInsert(int arr[], int n) { struct Node *head NULL; struct Node *tail NULL; for (int i 0; i n; i) { struct Node *newNode (struct Node *)malloc(sizeof(struct Node)); if (newNode NULL) { printf(內(nèi)存申請失敗\n); return head; } newNode-data arr[i]; newNode-next NULL; if (head NULL) { head newNode; tail newNode; } else { tail-next newNode; tail newNode; } } return head; }跑一遍數(shù)據(jù)1、2、3插入1head和tail都指向節(jié)點(diǎn)11 - NULL插入2tail-next指向節(jié)點(diǎn)2tail移到節(jié)點(diǎn)21 - 2 - NULL插入3tail-next指向節(jié)點(diǎn)3tail移到節(jié)點(diǎn)31 - 2 - 3 - NULL順序和插入順序一致符合大多數(shù)人的直覺。3.4 帶虛擬頭節(jié)點(diǎn)的尾插法上面那個(gè)if-else分支每次都要判斷寫多了也煩。有個(gè)更優(yōu)雅的寫法是引入一個(gè)“虛擬頭節(jié)點(diǎn)”也叫哨兵節(jié)點(diǎn)它不存實(shí)際數(shù)據(jù)只用來占位。struct Node *createListWithDummy(int arr[], int n) { struct Node *dummy (struct Node *)malloc(sizeof(struct Node)); dummy-next NULL; struct Node *tail dummy; for (int i 0; i n; i) { struct Node *newNode (struct Node *)malloc(sizeof(struct Node)); newNode-data arr[i]; newNode-next NULL; tail-next newNode; tail newNode; } struct Node *head dummy-next; free(dummy); return head; }這樣循環(huán)里就沒有分支了邏輯更統(tǒng)一。代價(jià)是多申請了一個(gè)節(jié)點(diǎn)又釋放掉以及最后要記得把dummy釋放掉不然就泄漏了。這個(gè)技巧在面試?yán)锿臃值粘懘a用不用看個(gè)人習(xí)慣。4. 頭插和尾插的對比以及選型建議兩種方法沒有絕對的好壞關(guān)鍵看你要什么。對比維度頭插法尾插法指針數(shù)量只需head需要head和tail插入時(shí)間復(fù)雜度O(1)O(1)最終順序與插入順序相反與插入順序一致邊界處理無需特判空鏈表需特判空鏈表或用虛擬頭節(jié)點(diǎn)典型用途棧、逆序場景隊(duì)列、保持順序的場景選型其實(shí)就一句話要順序用尾插要逆序用頭插。如果你既想要順序又覺得尾插的邊界判斷煩那就用虛擬頭節(jié)點(diǎn)版本。還有個(gè)實(shí)際經(jīng)驗(yàn)在單鏈表中尾插法如果每次都要從頭遍歷找尾巴那插入就變成O(n)了。所以尾插法一定要維護(hù)tail指針別偷懶每次從頭找。我見過有人寫尾插不維護(hù)tail循環(huán)里套一個(gè)while找尾巴數(shù)據(jù)量一大直接慢得沒法看。5. 動態(tài)創(chuàng)建鏈表時(shí)最容易踩的五個(gè)坑這部分是我自己踩過、也看別人踩過的真實(shí)問題按出現(xiàn)頻率排序。5.1 忘記給新節(jié)點(diǎn)的next賦值malloc出來的內(nèi)存不會自動清零里面是垃圾值。如果你不顯式給newNode-next賦值它就指向一個(gè)隨機(jī)地址。遍歷的時(shí)候跑到這個(gè)地址輕則打印亂碼重則段錯(cuò)誤。頭插法里newNode-next head順帶就賦值了但尾插法里如果忘了newNode-next NULL新尾巴的next就是垃圾鏈表沒有正確的結(jié)尾。5.2 頭指針被覆蓋導(dǎo)致鏈表丟失這個(gè)在頭插法里最常見。有人寫head newNode; newNode-next head; // 錯(cuò)誤這樣newNode-next指向的是自己形成自環(huán)而且原來的鏈全丟了。正確順序永遠(yuǎn)是先接后斷先把新節(jié)點(diǎn)接到鏈上再移動頭指針。5.3 尾插法空鏈表時(shí)解引用空指針前面說過了head NULL時(shí)tail也是NULL直接tail-next就是崩。這個(gè)坑的隱蔽性在于如果你測試數(shù)據(jù)從第二條開始插可能碰巧不崩但第一條就崩。5.4 malloc之后不檢查返回值小練習(xí)里不檢查沒事但養(yǎng)成習(xí)慣很重要。真到了內(nèi)存受限的環(huán)境malloc返回NULL你不處理后面就是空指針解引用。5.5 忘記釋放內(nèi)存動態(tài)創(chuàng)建的反面就是動態(tài)釋放。鏈表用完之后要逐個(gè)free不然就是內(nèi)存泄漏。釋放的時(shí)候要先把下一個(gè)節(jié)點(diǎn)存起來再釋放當(dāng)前節(jié)點(diǎn)struct Node *p head; while (p ! NULL) { struct Node *temp p-next; free(p); p temp; }如果你先free(p)再去訪問p-next那就是訪問已釋放內(nèi)存行為未定義。這個(gè)順序不能錯(cuò)。6. 從建鏈到遍歷一個(gè)能直接跑的完整示例把前面的東西串起來給一個(gè)完整的、能編譯運(yùn)行的例子。這個(gè)例子同時(shí)演示頭插和尾插并打印結(jié)果對比。#include stdio.h #include stdlib.h struct Node { int data; struct Node *next; }; struct Node *headInsert(int arr[], int n) { struct Node *head NULL; for (int i 0; i n; i) { struct Node *node (struct Node *)malloc(sizeof(struct Node)); if (!node) return head; node-data arr[i]; node-next head; head node; } return head; } struct Node *tailInsert(int arr[], int n) { struct Node *head NULL, *tail NULL; for (int i 0; i n; i) { struct Node *node (struct Node *)malloc(sizeof(struct Node)); if (!node) return head; node-data arr[i]; node-next NULL; if (head NULL) { head tail node; } else { tail-next node; tail node; } } return head; } void printList(struct Node *head) { while (head) { printf(%d , head-data); head head-next; } printf(\n); } void freeList(struct Node *head) { while (head) { struct Node *temp head-next; free(head); head temp; } } int main() { int arr[] {1, 2, 3, 4, 5}; int n 5; struct Node *h1 headInsert(arr, n); printf(頭插法結(jié)果: ); printList(h1); freeList(h1); struct Node *h2 tailInsert(arr, n); printf(尾插法結(jié)果: ); printList(h2); freeList(h2); return 0; }運(yùn)行結(jié)果頭插法結(jié)果: 5 4 3 2 1 尾插法結(jié)果: 1 2 3 4 5這個(gè)對比很直觀。頭插法把數(shù)組倒過來了尾插法保持了原順序。7. 幾個(gè)能讓你少走彎路的實(shí)操心得最后分享幾個(gè)我在實(shí)際寫鏈表時(shí)總結(jié)的小經(jīng)驗(yàn)都是教材上不太會專門講的。畫圖比空想管用。指針操作光在腦子里想很容易亂拿張紙畫幾個(gè)方框和箭頭把每一步的指向標(biāo)出來比盯著代碼看半天強(qiáng)得多。尤其是頭插法那兩行代碼的順序畫一遍圖就再也不會記反了。先寫遍歷再寫插入。建鏈之前先把遍歷函數(shù)寫好這樣每插入一個(gè)節(jié)點(diǎn)就能立刻驗(yàn)證鏈對不對。很多人一口氣寫完建鏈直接跑結(jié)果錯(cuò)了不知道錯(cuò)在哪一步。分步驗(yàn)證能省大量調(diào)試時(shí)間。用調(diào)試器看指針值。如果條件允許在malloc之后和指針賦值之后打斷點(diǎn)看head、tail、newNode的實(shí)際地址和next的指向。比printf打印地址更直觀也更快定位問題。邊界數(shù)據(jù)一定要測?？諗?shù)組n0、只有一個(gè)元素n1這兩種情況必須測。很多bug只在邊界出現(xiàn)正常數(shù)據(jù)跑得歡一到邊界就崩。命名要能看出角色。head、tail、newNode、temp這些名字不是隨便起的一看就知道是干嘛的。別用p1、p2、p3過兩天自己都忘了哪個(gè)是哪個(gè)。鏈表這東西看懂了和寫對了之間隔著一條河而動態(tài)創(chuàng)建就是那條河上最窄的橋。頭插法和尾插法各練上三五遍把指針順序和邊界情況都摸熟后面學(xué)鏈表的插入、刪除、反轉(zhuǎn)就是順?biāo)浦鄣氖隆?