1. 為什么單鏈表操作值得反復(fù)打磨單鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)幾乎每個(gè)學(xué)C語(yǔ)言的人都會(huì)碰到。但我在帶新人和看代碼的過(guò)程中發(fā)現(xiàn)一個(gè)現(xiàn)象很多人能默寫出插入、刪除的代碼卻在實(shí)際寫查找和建表時(shí)頻繁翻車。比如查找時(shí)忘了處理頭節(jié)點(diǎn)為空的情況建表時(shí)用頭插法導(dǎo)致數(shù)據(jù)順序反了或者尾插法忘了維護(hù)尾指針導(dǎo)致每次插入都要遍歷一遍。這些問(wèn)題的根源不在于語(yǔ)法不熟而在于對(duì)單鏈表的內(nèi)存模型和指針操作的本質(zhì)理解不夠透徹。單鏈表的核心就兩件事一是每個(gè)節(jié)點(diǎn)通過(guò)指針串聯(lián)二是頭指針是訪問(wèn)整條鏈的唯一入口。查找和建立這兩個(gè)操作恰好一個(gè)是從入口出發(fā)遍歷一個(gè)是從零開(kāi)始構(gòu)建入口把這兩個(gè)搞明白了單鏈表的其他操作基本就是舉一反三的事。這篇內(nèi)容我會(huì)從實(shí)際編碼的角度出發(fā)把單鏈表的查找和建立操作拆開(kāi)揉碎講清楚。適合已經(jīng)了解C語(yǔ)言基礎(chǔ)語(yǔ)法、但對(duì)指針操作還不夠有信心的讀者也適合想重新梳理鏈表知識(shí)體系的開(kāi)發(fā)者。我會(huì)重點(diǎn)講清楚每一步為什么這么寫、常見(jiàn)的坑在哪里、以及實(shí)際項(xiàng)目中怎么選擇不同的建表方式。2. 單鏈表查找操作的完整拆解2.1 按值查找從遍歷邏輯到邊界處理按值查找的需求很直白給定一個(gè)目標(biāo)值在鏈表中找到第一個(gè)存儲(chǔ)該值的節(jié)點(diǎn)返回它的位置或指針。看起來(lái)簡(jiǎn)單但實(shí)際寫起來(lái)有幾個(gè)關(guān)鍵決策點(diǎn)。先定義節(jié)點(diǎn)結(jié)構(gòu)typedef struct Node { int data; struct Node *next; } Node;查找函數(shù)的基本框架是這樣的Node* findByValue(Node *head, int target) { Node *p head; while (p ! NULL) { if (p-data target) { return p; } p p-next; } return NULL; }這段代碼的邏輯是用一個(gè)游標(biāo)指針p從頭節(jié)點(diǎn)開(kāi)始每次比較當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)域匹配就返回不匹配就移動(dòng)到下一個(gè)節(jié)點(diǎn)直到p變成NULL說(shuō)明找完了也沒(méi)找到。這里有幾個(gè)容易出問(wèn)題的地方。第一循環(huán)條件用p ! NULL而不是p-next ! NULL因?yàn)樽詈笠粋€(gè)節(jié)點(diǎn)本身也需要被檢查。我見(jiàn)過(guò)有人寫成while (p-next ! NULL)結(jié)果最后一個(gè)節(jié)點(diǎn)的數(shù)據(jù)永遠(yuǎn)查不到。第二返回值的選擇上返回節(jié)點(diǎn)指針比返回位置索引更實(shí)用因?yàn)槟玫街羔樅罂梢灾苯訉?duì)節(jié)點(diǎn)做后續(xù)操作比如修改數(shù)據(jù)或刪除節(jié)點(diǎn)。如果確實(shí)需要返回位置索引代碼要改成這樣int findByValuePos(Node *head, int target) { Node *p head; int pos 1; while (p ! NULL) { if (p-data target) { return pos; } p p-next; pos; } return 0; // 0表示未找到位置從1開(kāi)始計(jì)數(shù) }用0表示未找到是一個(gè)約定因?yàn)橛行恢脧?開(kāi)始。這個(gè)約定在實(shí)際項(xiàng)目中很常見(jiàn)但一定要在函數(shù)注釋里寫清楚否則調(diào)用方可能誤以為0是第一個(gè)位置。2.2 按位置查找第k個(gè)節(jié)點(diǎn)怎么找才不出錯(cuò)按位置查找就是找鏈表中第k個(gè)節(jié)點(diǎn)。這個(gè)操作在插入和刪除時(shí)經(jīng)常作為輔助函數(shù)使用。代碼本身不復(fù)雜但邊界條件特別多。Node* findByPosition(Node *head, int k) { if (k 1) return NULL; Node *p head; int count 1; while (p ! NULL count k) { p p-next; count; } return p; // 如果k超出鏈表長(zhǎng)度p最終為NULL }這段代碼的精妙之處在于循環(huán)條件p ! NULL count k。當(dāng)k大于鏈表長(zhǎng)度時(shí)p會(huì)先變成NULL循環(huán)退出返回NULL。當(dāng)k合法時(shí)循環(huán)執(zhí)行k-1次p正好指向第k個(gè)節(jié)點(diǎn)。我剛開(kāi)始寫鏈表的時(shí)候經(jīng)常在這里犯一個(gè)錯(cuò)誤先遍歷計(jì)數(shù)得到鏈表長(zhǎng)度再判斷k是否合法然后再遍歷一次找第k個(gè)。這樣做邏輯上沒(méi)錯(cuò)但遍歷了兩次效率低。更好的做法就是上面這種一次遍歷邊走邊判斷。還有一個(gè)細(xì)節(jié)值得注意count從1開(kāi)始還是從0開(kāi)始。如果從0開(kāi)始循環(huán)條件變成count k-1代碼也能工作但可讀性差一些。我建議統(tǒng)一用從1開(kāi)始的計(jì)數(shù)方式和人類的直覺(jué)一致代碼審查時(shí)不容易看錯(cuò)。2.3 查找操作的性能分析與優(yōu)化思路單鏈表的查找時(shí)間復(fù)雜度是O(n)這是由鏈表的存儲(chǔ)結(jié)構(gòu)決定的。和數(shù)組的隨機(jī)訪問(wèn)O(1)相比鏈表在查找上確實(shí)沒(méi)有優(yōu)勢(shì)。但這不意味著查找操作沒(méi)有優(yōu)化空間。一個(gè)常見(jiàn)的優(yōu)化是將最近訪問(wèn)的節(jié)點(diǎn)移到鏈表頭部。這個(gè)策略基于一個(gè)假設(shè)如果一個(gè)元素被訪問(wèn)了它很可能在不久的將來(lái)被再次訪問(wèn)。實(shí)現(xiàn)方式是在找到目標(biāo)節(jié)點(diǎn)后把它從原位置摘下來(lái)再插入到頭部。這樣下次查找同一個(gè)元素時(shí)只需要O(1)的時(shí)間。Node* findByValueMoveToFront(Node *head, int target) { if (head NULL || head-data target) return head; Node *prev head; Node *cur head-next; while (cur ! NULL) { if (cur-data target) { prev-next cur-next; cur-next head; return cur; // cur成為新的頭節(jié)點(diǎn) } prev cur; cur cur-next; } return head; }這個(gè)優(yōu)化在特定場(chǎng)景下很有效比如實(shí)現(xiàn)一個(gè)簡(jiǎn)單的緩存。但要注意它會(huì)改變鏈表的順序如果業(yè)務(wù)邏輯依賴順序就不能用。另一個(gè)思路是維護(hù)一個(gè)訪問(wèn)頻率的輔助結(jié)構(gòu)但這已經(jīng)超出了單鏈表本身的范圍屬于更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。對(duì)于大多數(shù)日常開(kāi)發(fā)場(chǎng)景老老實(shí)實(shí)用O(n)的遍歷查找就夠了沒(méi)必要過(guò)度設(shè)計(jì)。注意查找操作返回指針后調(diào)用方使用該指針前應(yīng)確認(rèn)鏈表沒(méi)有被其他操作修改。在單線程環(huán)境下這通常不是問(wèn)題但在多線程環(huán)境中需要額外的同步機(jī)制。3. 單鏈表建立操作頭插法與尾插法的選擇3.1 頭插法的實(shí)現(xiàn)細(xì)節(jié)與適用場(chǎng)景頭插法的思路是每次新節(jié)點(diǎn)都插入到鏈表的頭部成為新的頭節(jié)點(diǎn)。代碼非常簡(jiǎn)潔Node* createListHeadInsert(int arr[], int n) { Node *head NULL; for (int i 0; i n; i) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data arr[i]; newNode-next head; head newNode; } return head; }三行核心代碼就完成了插入。newNode的next指向當(dāng)前的頭然后head更新為newNode。整個(gè)過(guò)程不需要判斷鏈表是否為空也不需要遍歷找尾節(jié)點(diǎn)。但頭插法有一個(gè)顯著的特點(diǎn)生成的鏈表順序和輸入順序相反。如果輸入數(shù)組是[1, 2, 3, 4, 5]建出來(lái)的鏈表是5-4-3-2-1。這不是bug而是頭插法的固有特性。頭插法適合什么場(chǎng)景當(dāng)你需要逆序處理數(shù)據(jù)時(shí)頭插法天然就是逆序的不需要額外的反轉(zhuǎn)操作。比如從文件中逐行讀取數(shù)據(jù)要求按相反順序輸出用頭插法建表然后直接遍歷就行了。另一個(gè)場(chǎng)景是當(dāng)你不關(guān)心順序只關(guān)心元素集合時(shí)頭插法是最快的建表方式。3.2 尾插法的實(shí)現(xiàn)與尾指針的維護(hù)尾插法要把新節(jié)點(diǎn)接到鏈表末尾保持輸入順序。如果不做優(yōu)化每次插入都要從頭遍歷到尾時(shí)間復(fù)雜度是O(n2)。優(yōu)化的關(guān)鍵是維護(hù)一個(gè)尾指針Node* createListTailInsert(int arr[], int n) { Node *head NULL; Node *tail NULL; for (int i 0; i n; i) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data arr[i]; newNode-next NULL; if (head NULL) { head newNode; tail newNode; } else { tail-next newNode; tail newNode; } } return head; }這段代碼里head和tail初始都是NULL。第一個(gè)節(jié)點(diǎn)插入時(shí)head和tail同時(shí)指向它。后續(xù)節(jié)點(diǎn)插入時(shí)把tail的next指向新節(jié)點(diǎn)然后tail后移到新節(jié)點(diǎn)。這樣每次插入都是O(1)整體建表是O(n)。我第一次寫尾插法時(shí)犯過(guò)一個(gè)錯(cuò)誤忘了處理第一個(gè)節(jié)點(diǎn)的特殊情況直接寫tail-next newNode結(jié)果tail是NULL導(dǎo)致程序崩潰。后來(lái)我總結(jié)了一個(gè)經(jīng)驗(yàn)凡是涉及頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的操作第一件事就是判斷鏈表是否為空。還有一種更簡(jiǎn)潔的寫法使用帶頭節(jié)點(diǎn)的鏈表。頭節(jié)點(diǎn)是一個(gè)不存儲(chǔ)有效數(shù)據(jù)的哨兵節(jié)點(diǎn)它的存在讓空鏈表和非空鏈表的處理邏輯統(tǒng)一了Node* createListWithDummyHead(int arr[], int n) { Node *dummy (Node*)malloc(sizeof(Node)); dummy-next NULL; Node *tail dummy; for (int i 0; i n; i) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data arr[i]; newNode-next NULL; tail-next newNode; tail newNode; } Node *head dummy-next; free(dummy); return head; }帶頭節(jié)點(diǎn)的寫法在插入和刪除時(shí)特別方便因?yàn)椴恍枰獑为?dú)處理在頭部操作的情況。很多經(jīng)典教材和開(kāi)源項(xiàng)目都采用這種設(shè)計(jì)。3.3 兩種建表方式的對(duì)比與選型建議對(duì)比維度頭插法尾插法時(shí)間復(fù)雜度O(n)O(n)維護(hù)尾指針空間復(fù)雜度O(1)額外空間O(1)額外空間生成順序與輸入相反與輸入相同代碼復(fù)雜度極簡(jiǎn)稍復(fù)雜需處理空表適用場(chǎng)景逆序需求、不關(guān)心順序保持順序、隊(duì)列模擬選型的核心判斷標(biāo)準(zhǔn)就一條你是否需要保持輸入順序。需要就用尾插法不需要就用頭插法。不要為了代碼簡(jiǎn)潔而在需要順序的場(chǎng)景強(qiáng)行用頭插法然后再反轉(zhuǎn)那樣反而多了一次O(n)的操作。另外如果建表后還需要頻繁在尾部插入那維護(hù)尾指針就是必須的。但如果建表后主要在頭部操作尾指針?lè)炊闪司S護(hù)負(fù)擔(dān)每次頭部插入后如果恰好插在尾部還需要更新尾指針。所以數(shù)據(jù)結(jié)構(gòu)的輔助指針要根據(jù)實(shí)際訪問(wèn)模式來(lái)決定。4. 從零手寫完整可運(yùn)行的示例代碼4.1 代碼組織與函數(shù)聲明把查找和建表的操作整合到一個(gè)完整的程序中方便直接編譯運(yùn)行。先看頭文件和函數(shù)聲明#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node* createListTailInsert(int arr[], int n); Node* findByValue(Node *head, int target); int findByValuePos(Node *head, int target); Node* findByPosition(Node *head, int k); void printList(Node *head); void freeList(Node *head);函數(shù)聲明放在前面主函數(shù)放在后面這是C語(yǔ)言的標(biāo)準(zhǔn)組織方式。每個(gè)函數(shù)只做一件事職責(zé)單一方便單獨(dú)測(cè)試和調(diào)試。4.2 主函數(shù)與測(cè)試用例設(shè)計(jì)int main() { int arr[] {10, 20, 30, 40, 50}; int n sizeof(arr) / sizeof(arr[0]); Node *head createListTailInsert(arr, n); printf(鏈表內(nèi)容: ); printList(head); // 測(cè)試按值查找 Node *found findByValue(head, 30); if (found ! NULL) { printf(找到值30節(jié)點(diǎn)地址: %p\n, (void*)found); } else { printf(未找到值30\n); } // 測(cè)試按位置查找 Node *posNode findByPosition(head, 3); if (posNode ! NULL) { printf(第3個(gè)節(jié)點(diǎn)的值: %d\n, posNode-data); } // 測(cè)試查找不存在的值 found findByValue(head, 99); printf(查找99的結(jié)果: %s\n, found NULL ? 未找到 : 找到了); // 測(cè)試越界位置 posNode findByPosition(head, 10); printf(查找第10個(gè)節(jié)點(diǎn)的結(jié)果: %s\n, posNode NULL ? 越界 : 找到了); freeList(head); return 0; }測(cè)試用例覆蓋了正常查找、邊界查找不存在的值、越界位置這些情況。實(shí)際開(kāi)發(fā)中我建議每寫一個(gè)鏈表函數(shù)就立刻寫一個(gè)測(cè)試用例驗(yàn)證不要等所有函數(shù)寫完再統(tǒng)一測(cè)試。鏈表操作涉及大量指針一旦出錯(cuò)很難定位是哪個(gè)函數(shù)的問(wèn)題。4.3 輔助函數(shù)的實(shí)現(xiàn)void printList(Node *head) { Node *p head; while (p ! NULL) { printf(%d, p-data); if (p-next ! NULL) printf( - ); p p-next; } printf(\n); } void freeList(Node *head) { Node *p head; while (p ! NULL) { Node *temp p; p p-next; free(temp); } }printList用于調(diào)試輸出格式是10 - 20 - 30 - 40 - 50。freeList用于釋放內(nèi)存注意先用temp保存當(dāng)前節(jié)點(diǎn)p后移之后再free(temp)順序不能反。如果先f(wàn)ree(p)再訪問(wèn)p-next就是訪問(wèn)已釋放的內(nèi)存屬于未定義行為。提示在開(kāi)發(fā)階段可以在freeList中把free掉的指針置為NULL雖然對(duì)局部變量temp來(lái)說(shuō)意義不大但養(yǎng)成這個(gè)習(xí)慣對(duì)調(diào)試有幫助。5. 那些年我踩過(guò)的指針坑5.1 內(nèi)存泄漏malloc了但沒(méi)free單鏈表最常見(jiàn)的內(nèi)存問(wèn)題就是泄漏。每次malloc創(chuàng)建一個(gè)節(jié)點(diǎn)就必須在某個(gè)時(shí)刻free它。我見(jiàn)過(guò)不少代碼建表、使用都沒(méi)問(wèn)題但程序結(jié)束時(shí)沒(méi)有釋放鏈表導(dǎo)致內(nèi)存泄漏。在短生命周期的小程序中這不算大問(wèn)題但在長(zhǎng)時(shí)間運(yùn)行的服務(wù)中累積的泄漏會(huì)耗盡內(nèi)存。更隱蔽的泄漏發(fā)生在刪除節(jié)點(diǎn)時(shí)。比如刪除一個(gè)節(jié)點(diǎn)正確的做法是先用臨時(shí)指針保存要?jiǎng)h除的節(jié)點(diǎn)調(diào)整前驅(qū)的next指針然后再free臨時(shí)指針。如果直接free再調(diào)整指針就會(huì)丟失后續(xù)節(jié)點(diǎn)的地址造成鏈表斷裂和內(nèi)存泄漏。// 正確的刪除方式 Node* deleteNode(Node *head, int target) { if (head NULL) return NULL; if (head-data target) { Node *temp head; head head-next; free(temp); return head; } Node *prev head; while (prev-next ! NULL prev-next-data ! target) { prev prev-next; } if (prev-next ! NULL) { Node *temp prev-next; prev-next temp-next; free(temp); } return head; }5.2 野指針free之后還在用野指針是另一個(gè)高頻問(wèn)題。free一個(gè)節(jié)點(diǎn)后該節(jié)點(diǎn)的內(nèi)存已經(jīng)歸還給系統(tǒng)但指針變量本身還保存著原來(lái)的地址。如果后續(xù)代碼不小心通過(guò)這個(gè)指針訪問(wèn)內(nèi)存行為是不可預(yù)測(cè)的。Node *p head; free(p); // 此時(shí)p是野指針 p-data 10; // 未定義行為可能崩潰也可能悄悄改掉別的數(shù)據(jù)防御性編程的做法是free之后立刻把指針置為NULLfree(p); p NULL;這樣后續(xù)如果誤用p程序會(huì)立即崩潰在NULL解引用上而不是產(chǎn)生難以追蹤的數(shù)據(jù)損壞。崩潰比靜默錯(cuò)誤好排查得多。5.3 頭指針丟失鏈表建好了但找不到入口頭指針是訪問(wèn)鏈表的唯一入口一旦丟失整條鏈表就變成了無(wú)法訪問(wèn)的內(nèi)存垃圾。頭指針丟失的常見(jiàn)場(chǎng)景是在遍歷過(guò)程中不小心修改了head// 錯(cuò)誤寫法 while (head ! NULL) { printf(%d , head-data); head head-next; // head被修改了 } // 此時(shí)head已經(jīng)是NULL鏈表入口丟失正確的做法是用一個(gè)臨時(shí)指針來(lái)遍歷Node *p head; while (p ! NULL) { printf(%d , p-data); p p-next; } // head保持不變這個(gè)坑我踩過(guò)不止一次特別是在調(diào)試時(shí)隨手寫遍歷代碼忘了保護(hù)head。后來(lái)我養(yǎng)成了一個(gè)習(xí)慣任何需要遍歷鏈表的函數(shù)第一行就定義臨時(shí)指針Node *p head;后續(xù)所有操作都用p絕不碰head。6. 查找與建表在實(shí)際場(chǎng)景中的組合應(yīng)用6.1 用鏈表實(shí)現(xiàn)簡(jiǎn)單的學(xué)生成績(jī)管理假設(shè)需要管理一組學(xué)生成績(jī)支持按學(xué)號(hào)查找和按錄入順序展示。這就是尾插法建表加按值查找的典型組合。typedef struct Student { int id; int score; struct Student *next; } Student; Student* addStudent(Student *head, int id, int score) { Student *newNode (Student*)malloc(sizeof(Student)); newNode-id id; newNode-score score; newNode-next NULL; if (head NULL) return newNode; Student *p head; while (p-next ! NULL) p p-next; p-next newNode; return head; } Student* findStudent(Student *head, int id) { Student *p head; while (p ! NULL) { if (p-id id) return p; p p-next; } return NULL; }這個(gè)例子里addStudent每次都要遍歷到尾部時(shí)間復(fù)雜度O(n)。如果學(xué)生數(shù)量很大且頻繁添加就應(yīng)該維護(hù)一個(gè)尾指針。但在學(xué)生數(shù)量不多比如一個(gè)班幾十人的場(chǎng)景下O(n)的遍歷完全可以接受代碼簡(jiǎn)潔更重要。6.2 從文件讀取數(shù)據(jù)建表并按條件查找實(shí)際項(xiàng)目中數(shù)據(jù)往往來(lái)自文件。用尾插法保持文件中的原始順序然后用查找函數(shù)篩選滿足條件的記錄。Node* loadFromFile(const char *filename) { FILE *fp fopen(filename, r); if (fp NULL) return NULL; Node *head NULL, *tail NULL; int value; while (fscanf(fp, %d, value) 1) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-next NULL; if (head NULL) { head newNode; tail newNode; } else { tail-next newNode; tail newNode; } } fclose(fp); return head; }這段代碼里fscanf的返回值判斷很重要。當(dāng)文件讀完或格式不匹配時(shí)fscanf返回非1的值循環(huán)退出。如果忘了判斷返回值可能會(huì)把無(wú)效數(shù)據(jù)讀入鏈表。6.3 性能考量什么時(shí)候不該用單鏈表單鏈表的查找是O(n)這是它的固有短板。如果你的應(yīng)用場(chǎng)景是頻繁查找、很少插入刪除那數(shù)組或哈希表是更好的選擇。數(shù)組支持O(1)的隨機(jī)訪問(wèn)哈希表平均O(1)的查找。單鏈表的優(yōu)勢(shì)在于頻繁在頭部插入刪除和不需要連續(xù)內(nèi)存。比如實(shí)現(xiàn)一個(gè)棧用單鏈表頭插法push、頭部刪除pop都是O(1)?；蛘邇?nèi)存碎片化嚴(yán)重的嵌入式環(huán)境中鏈表不需要一塊連續(xù)的大內(nèi)存更容易分配成功。選擇數(shù)據(jù)結(jié)構(gòu)時(shí)先分析操作的頻率分布哪種操作最多對(duì)時(shí)間復(fù)雜度要求是什么內(nèi)存是否受限把這些想清楚再動(dòng)手寫代碼比寫完發(fā)現(xiàn)性能不達(dá)標(biāo)再重構(gòu)要省事得多。7. 調(diào)試單鏈表的實(shí)用技巧7.1 用打印語(yǔ)句追蹤指針變化鏈表調(diào)試最有效的方法就是在關(guān)鍵位置打印指針地址和節(jié)點(diǎn)數(shù)據(jù)。比如在插入操作中printf(插入前: head%p, tail%p\n, (void*)head, (void*)tail); // 插入操作 printf(插入后: head%p, tail%p, newNode%p\n, (void*)head, (void*)tail, (void*)newNode);通過(guò)對(duì)比插入前后的指針值可以快速判斷指針是否正確更新。如果head在插入后變了但你不期望它變那就說(shuō)明代碼有問(wèn)題。7.2 畫(huà)圖輔助理解指針指向紙上畫(huà)圖是理解鏈表操作最直觀的方式。每寫一個(gè)操作先畫(huà)出操作前的鏈表狀態(tài)然后一步步畫(huà)出指針的變化過(guò)程。比如頭插法畫(huà)出來(lái)就是新節(jié)點(diǎn)的next指向原h(huán)ead然后head指向新節(jié)點(diǎn)。畫(huà)一遍圖代碼自然就寫出來(lái)了。我到現(xiàn)在遇到復(fù)雜的鏈表操作比如反轉(zhuǎn)、合并、找環(huán)還是會(huì)先在紙上畫(huà)圖理清思路再寫代碼。這個(gè)方法看起來(lái)笨但比在腦子里空想要可靠得多。7.3 使用斷言檢查不變量在函數(shù)的關(guān)鍵位置加入斷言檢查鏈表的不變量是否成立#include assert.h // 在函數(shù)返回前檢查 assert(head NULL || head-data 0); // 假設(shè)數(shù)據(jù)非負(fù)斷言在Debug版本中生效Release版本中會(huì)被移除不影響性能。對(duì)于鏈表這種指針操作密集的代碼斷言可以幫助在開(kāi)發(fā)階段盡早發(fā)現(xiàn)邏輯錯(cuò)誤。8. 從單鏈表到更復(fù)雜結(jié)構(gòu)的延伸單鏈表的查找和建表是基礎(chǔ)中的基礎(chǔ)把這個(gè)搞扎實(shí)了后續(xù)學(xué)習(xí)雙向鏈表、循環(huán)鏈表、鏈?zhǔn)綏！㈡準(zhǔn)疥?duì)列都會(huì)輕松很多。雙向鏈表無(wú)非是多維護(hù)一個(gè)prev指針建表時(shí)多一步設(shè)置prev查找時(shí)可以從兩個(gè)方向進(jìn)行。循環(huán)鏈表就是把尾節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)遍歷時(shí)需要判斷是否回到起點(diǎn)。我的建議是不要急著學(xué)更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)先把單鏈表的每個(gè)操作都手寫三遍以上直到不看參考代碼也能一氣呵成地寫出來(lái)。寫完之后再想想如果數(shù)據(jù)域不是int而是結(jié)構(gòu)體代碼需要改哪里如果鏈表很長(zhǎng)遞歸遍歷會(huì)不會(huì)棧溢出如果要在多線程環(huán)境中使用需要加什么保護(hù)這些問(wèn)題的答案比單純記住代碼本身有價(jià)值得多。我在實(shí)際項(xiàng)目中用鏈表的頻率并不高但鏈表訓(xùn)練出來(lái)的指針操作能力和內(nèi)存管理意識(shí)在寫樹(shù)、圖、哈希表時(shí)都在發(fā)揮作用?；A(chǔ)打牢了上層建筑才穩(wěn)。