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