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