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