嵌入式開發(fā)里有個現(xiàn)象很有意思一說數(shù)據(jù)結(jié)構(gòu)很多做單片機、做驅(qū)動、做板級開發(fā)的朋友第一反應就是“這是面試題吧”“八股文吧”“工程里哪敢用malloc”。但真到了維護一個多設備任務系統(tǒng)、調(diào)一個中斷里的事件隊列時單靠數(shù)組硬扛會難受得想摔開發(fā)板。單向鏈表這個最基礎的數(shù)據(jù)結(jié)構(gòu)在嵌入式場景里比想象中常見得多——RTOS的任務控制塊鏈表、設備動態(tài)注冊表、按鍵歷史記錄、低功耗喚醒事件緩存底層都是它。這篇就從嵌入式實戰(zhàn)視角出發(fā)把單向鏈表的基本操作完整拆一遍代碼可以直接抄坑也替你先踩一遍。1. 嵌入式里為什么繞不開單向鏈表數(shù)組的邊界感太強1.1 數(shù)組不好使的時候鏈表正好頂上來很多人學C語言時接觸的第一個數(shù)據(jù)容器就是數(shù)組連續(xù)內(nèi)存、隨機訪問、下標友好在MCU上跑起來也很快。但數(shù)組有個天然約束容量是編譯期定死的。你要維護一批運行時動態(tài)上下線的傳感器節(jié)點、串口設備、藍牙連接總共會有多少個事先根本不知道。這時候硬用數(shù)組要么開大了浪費RAM要么開小了丟數(shù)據(jù)。鏈表的核心優(yōu)勢就在這里結(jié)點可以隨時申請、隨時釋放插入和刪除不需要搬動其他元素。比如你要維護一個設備注冊表設備上電就往鏈表尾部掛一個結(jié)點設備離線就把它刪掉數(shù)組做同樣的事刪除中間一個元素后面全部要memmove白白消耗CPU周期。還有一個隱藏優(yōu)勢鏈表天然支持“逆序回顧”。頭插法插入的數(shù)據(jù)遍歷時就是從新到舊非常適合按鍵事件、ADC采樣歷史這類“最近發(fā)生的優(yōu)先處理”場景。數(shù)組要實現(xiàn)同樣的邏輯要么移位要么維護一個環(huán)形下標代碼會繞很多。1.2 嵌入式面試八股里鏈表為什么永遠排在第一個看嵌入式軟件工程師的面試題也好“嵌入式八股文”也好鏈表幾乎必考。手寫單鏈表創(chuàng)建、遍歷、反轉(zhuǎn)、找中間結(jié)點、判斷是否有環(huán)反復出現(xiàn)。不是面試官閑得慌是因為鏈表是檢驗指針和內(nèi)存功底的最短路徑。一個候選人鏈表寫不寫得對能暴露出很多東西能不能分清指針和數(shù)據(jù)本身、知不知道修改鏈結(jié)構(gòu)時需要用二級指針或哨兵結(jié)點、刪結(jié)點后會不會順手free并置空、邊界情況下空表、刪頭結(jié)點、刪尾結(jié)點會不會處理。這些能力在調(diào)試實際嵌入式工程時就是排查HardFault和內(nèi)存踩踏的基礎。所以哪怕你項目里從來沒自己寫過鏈表也建議把這塊啃下來。后面看RTOS源碼看到OS_TCB被掛進 ReadyList 鏈表時的那些操作你會有一種“原來如此”的通透感。2. 單鏈表結(jié)構(gòu)體設計與頭結(jié)點選擇先把地基打?qū)?.1 結(jié)點結(jié)構(gòu)體的三種設計思路按需選型單鏈表的結(jié)點最少需要兩部分數(shù)據(jù)域和指針域。放在嵌入式場景里數(shù)據(jù)域往往不是簡單的一個int而是某個硬件采集結(jié)構(gòu)體。最常見的設計是直接用結(jié)構(gòu)體作為數(shù)據(jù)域typedef struct { uint16_t temperature; uint16_t humidity; uint32_t timestamp; } SensorData_t; typedef struct Node { SensorData_t data; struct Node *next; } Node_t;這種寫法的好處是類型安全訪問直觀結(jié)點和業(yè)務數(shù)據(jù)生命周期一致。缺點也很明顯如果SensorData_t很大每次插入都會發(fā)生一次結(jié)構(gòu)體拷貝RAM吃緊的芯片會比較心疼。另一種做法是把數(shù)據(jù)域定義成指針比如void *data或某個固定大小緩沖區(qū)。好處是結(jié)點本身很小拷貝指針的代價幾乎為零壞處是你必須自己管理data指向的那塊內(nèi)存的生命周期稍不留神就會出現(xiàn)野指針。我的建議是數(shù)據(jù)域超過16字節(jié)且結(jié)點數(shù)可控時用結(jié)構(gòu)體副本數(shù)據(jù)域很大且需要頻繁插入刪除時再用指針方案但配套的內(nèi)存分配策略必須提前想好。2.2 頭結(jié)點和頭指針的區(qū)別決定你寫代碼時的心理負擔很多新手會把“頭結(jié)點”和“頭指針”混為一談。頭指針是一個指向鏈表第一個結(jié)點的指針變量head為NULL表示空鏈表。頭結(jié)點則是一個不存儲業(yè)務數(shù)據(jù)的哨兵結(jié)點它固定在鏈表最前面頭指針始終指向它。帶頭結(jié)點的寫法在插入和刪除時會省掉大量“如果是頭結(jié)點怎么辦”的特判。比如說刪除指定值的結(jié)點無頭結(jié)點時如果要刪的是第一個結(jié)點你必須修改頭指針函數(shù)形參得用Node_t **head有頭結(jié)點時頭指針始終不用變統(tǒng)一走“找到前驅(qū)結(jié)點改前驅(qū)的next”這條邏輯。嵌入式內(nèi)存雖然緊張但多花一個結(jié)點空間換代碼邏輯的統(tǒng)一值。哨兵結(jié)點的next指向空就表示空鏈表遍歷時從head-next開始即可。下面所有代碼我都基于帶頭結(jié)點的寫法這也是工程上最常用、最不容易出錯的風格。3. 單向鏈表基本操作完整落地初始化、插入、刪除、查找、銷毀3.1 初始化和創(chuàng)建結(jié)點每個函數(shù)都先做防御判斷先定義鏈表管理結(jié)構(gòu)。如果只帶頭結(jié)點其實只需要一個頭指針就夠但工程里為了方便拿長度通常再維護一個size字段刪除和插入時同步更新避免每次遍歷求長度。typedef struct { Node_t *head; uint32_t size; } LinkedList_t; void LinkedList_Init(LinkedList_t *list) { list-head (Node_t *)malloc(sizeof(Node_t)); if (list-head NULL) { // 打印錯誤日志進入錯誤處理 return; } list-head-next NULL; list-size 0; } Node_t *CreateNode(SensorData_t data) { Node_t *node (Node_t *)malloc(sizeof(Node_t)); if (node NULL) { return NULL; } node-data data; node-next NULL; return node; }注意兩個細節(jié)。第一malloc之后必須判斷返回值嵌入式內(nèi)存池很小分配失敗是常態(tài)而不是異常。第二頭結(jié)點的data域沒有初始化因為我們根本不會訪問它但為了讓調(diào)試器里看起來干凈也可以memset一下。3.2 插入操作頭插、尾插、中間插順序都不能搞反頭插法也就是把新結(jié)點掛在頭結(jié)點后面。這個操作在實現(xiàn)“最近數(shù)據(jù)優(yōu)先”的緩存時最常用int LinkedList_InsertHead(LinkedList_t *list, SensorData_t data) { Node_t *node CreateNode(data); if (node NULL) { return -1; } node-next list-head-next; list-head-next node; list-size; return 0; }三步邏輯新結(jié)點的next指向原來的第一個數(shù)據(jù)結(jié)點頭結(jié)點的next指向新結(jié)點size加一。順序絕對不能反如果先把head-next賦給node再把node賦給head-next那原來的一整條鏈表就丟了這是頭插法最容易翻車的地方。我建議在寫代碼前先在紙上畫三個方框兩根箭頭把兩步連線畫清楚再動手寫基本不會錯。尾插法也就是把新結(jié)點追加到鏈表末尾。最簡單的實現(xiàn)是從頭遍歷到最后一個結(jié)點然后把最后一個結(jié)點的next指向新結(jié)點int LinkedList_InsertTail(LinkedList_t *list, SensorData_t data) { Node_t *node CreateNode(data); if (node NULL) { return -1; } Node_t *cur list-head; while (cur-next ! NULL) { cur cur-next; } cur-next node; list-size; return 0; }這個操作的時間復雜度是O(n)。如果業(yè)務上尾插頻率很高比如定時器事件戳不停往隊列尾巴上掛那最好在LinkedList_t里額外維護一個tail指針尾插直接操作tail-next。但代價是刪除尾結(jié)點時你需要找到倒數(shù)第二個結(jié)點來更新tail等于把復雜度從刪除端轉(zhuǎn)移到了維護端。所以說數(shù)據(jù)結(jié)構(gòu)“優(yōu)化”從來沒有免費的午餐要根據(jù)真實讀寫比例選。指定位置插入核心是找前驅(qū)結(jié)點。插入到第pos個位置實際上先找到第pos-1個結(jié)點然后執(zhí)行int LinkedList_InsertAt(LinkedList_t *list, uint32_t pos, SensorData_t data) { if (pos 0 || pos list-size) { return -1; // 位置從1開始才合法 } Node_t *cur list-head; for (uint32_t i 1; i pos; i) { cur cur-next; } Node_t *node CreateNode(data); if (node NULL) { return -1; } node-next cur-next; cur-next node; list-size; return 0; }插入到pos位置循環(huán)走pos-1次后cur正好落在這個位置的前驅(qū)。這個邊界條件值得多驗證幾次pos1時循環(huán)一次都不走cur就是頭結(jié)點InsertAt退化成頭插possize時循環(huán)size-1次cur是最后一個結(jié)點退化成尾插。3.3 刪除操作前驅(qū)結(jié)點沒找對鏈表就斷了刪除指定位置的結(jié)點和插入類似先找前驅(qū)int LinkedList_DeleteAt(LinkedList_t *list, uint32_t pos, SensorData_t *out_data) { if (pos 0 || pos list-size || list-size 0) { return -1; } Node_t *prev list-head; for (uint32_t i 1; i pos; i) { prev prev-next; } Node_t *del prev-next; if (out_data ! NULL) { *out_data del-data; // 需要數(shù)據(jù)時帶回 } prev-next del-next; free(del); list-size--; return 0; }刪除的關(guān)鍵動作只有兩行prev-next del-next先把要刪的結(jié)點從鏈中摘除然后free(del)釋放內(nèi)存。摘鏈和釋放兩個動作一步都不能少。摘鏈漏了會造成鏈表斷成兩截遍歷會跳到未知地址這個坑很容易把整個系統(tǒng)搞進HardFault。free漏了就是內(nèi)存泄漏嵌入式設備跑幾天后RAM越來越少最后malloc失敗。如果你用的是自己實現(xiàn)的內(nèi)存池而不是mallocfree這一步要換成“把結(jié)點歸還到空閑池”具體怎么做第四部分會展開。按值刪除和按位置刪除邏輯幾乎一樣無非是把“找前驅(qū)”的條件換成cur-data.temperature target這類業(yè)務判斷。需要注意按值刪除一般只刪第一個匹配項如果你要實現(xiàn)“刪除所有匹配項”刪除完一個后不能急著結(jié)束要繼續(xù)往后遍歷遍歷時注意別跳過被刪結(jié)點的next。3.4 查找、遍歷與銷毀別小看這些基礎動作查找指定值的結(jié)點本質(zhì)上就是從頭到尾過一遍Node_t *LinkedList_Find(LinkedList_t *list, uint32_t timestamp) { Node_t *cur list-head-next; while (cur ! NULL) { if (cur-data.timestamp timestamp) { return cur; } cur cur-next; } return NULL; }這個函數(shù)返回的是結(jié)點指針調(diào)用方拿到后可以修改結(jié)點里的數(shù)據(jù)域?qū)崿F(xiàn)“按條件修改”的功能。注意這里返回的是內(nèi)部指針函數(shù)外部不要try-free它除非你明確知道這個結(jié)點是誰分配的、什么時候需要回收。遍歷函數(shù)在調(diào)試時特別有用。嵌入式環(huán)境下沒有方便的STL迭代器最樸素的做法就是打印每個結(jié)點的數(shù)據(jù)void LinkedList_Print(LinkedList_t *list) { Node_t *cur list-head-next; uint32_t index 0; while (cur ! NULL) { printf([%u] timestamp%u temp%u humi%u\r\n, index, cur-data.timestamp, cur-data.temperature, cur-data.humidity); cur cur-next; } }我建議每個鏈表模塊里都留一個類似的輸出函數(shù)調(diào)試時隨時調(diào)用比在調(diào)試器里看鏈表內(nèi)存結(jié)構(gòu)直觀得多。串口打印在極端性能場景下要慎用但開發(fā)階段這個函數(shù)的價值遠大于它的耗時。銷毀整個鏈表注意“先摘后釋放”和“用tmp保存下一個結(jié)點”兩個要點void LinkedList_Destroy(LinkedList_t *list) { Node_t *cur list-head; while (cur ! NULL) { Node_t *tmp cur-next; // 先保存下一個 free(cur); // 再釋放當前 cur tmp; // 走到下一個 } list-head NULL; list-size 0; }如果先釋放cur再用cur-next就訪問了已經(jīng)free的內(nèi)存這是個隱蔽的野指針問題。很多嵌入式系統(tǒng)重啟幾次后隨機崩潰原因常常就藏在這種看似不起眼的循環(huán)里。所以每個循環(huán)里要先用tmp把下一個結(jié)點地址存好再去free當前結(jié)點。3.5 就地反轉(zhuǎn)鏈表考察指針操作基本功的最高頻操作單向鏈表反轉(zhuǎn)面試手寫頻率最高工程上也經(jīng)常用比如要把事件隊列倒序回放時。就地反轉(zhuǎn)的核心是維護三個指針prev、cur、next。void LinkedList_Reverse(LinkedList_t *list) { Node_t *prev NULL; Node_t *cur list-head-next; Node_t *next NULL; while (cur ! NULL) { next cur-next; cur-next prev; prev cur; cur next; } list-head-next prev; // 反轉(zhuǎn)完成后prev就是新的首數(shù)據(jù)結(jié)點 }逐行理解一下第一步next cur-next保存后繼因為下一步要切斷cur-next不提前保存就丟了。第二步cur-next prev讓當前結(jié)點的next指向前一個結(jié)點這就“反轉(zhuǎn)”了一對結(jié)點。第三步prev cur第四步cur next整體向后挪一個位置。循環(huán)結(jié)束后prev指向原鏈表最后一個結(jié)點也就是新鏈表的第一個數(shù)據(jù)結(jié)點把它掛到頭結(jié)點后面收尾。這個算法不需要額外的O(n)內(nèi)存在RAM緊張的MCU上很有意義。寫成代碼是四行但想清楚整個過程需要畫圖。我在看新人代碼時發(fā)現(xiàn)反轉(zhuǎn)寫錯的人往往都是沒畫圖直接開寫寫到一半被指針繞暈。4. 嵌入式環(huán)境的內(nèi)存管理malloc不是不能用但要有替代方案4.1 malloc的碎片問題是真實存在的尤其在長時間運行的設備上桌面程序malloc/free一天幾百萬次問題不大嵌入式設備RAM可能只有幾十KB堆區(qū)本來就小反復分配釋放會產(chǎn)生碎片。碎片攢到一定程度即使總剩余內(nèi)存夠用malloc也找不到一塊連續(xù)空閑區(qū)域返回NULL。設備運行幾天后突然采集數(shù)據(jù)失敗、任務異常查了半天發(fā)現(xiàn)是malloc返回了空指針這種情況并不少見。另外有些小型MCU的庫函數(shù)實現(xiàn)里malloc內(nèi)部如果用了全局鎖在中斷上下文里調(diào)用可能造成死鎖或不確定時延。這也是我建議嵌入式項目里慎重使用裸malloc的原因之一。策略不是“永遠不用”而是“明確邊界”。靜態(tài)初始化階段用一次malloc建好鏈表頭運行過程中結(jié)點頻繁增減也要盡量走內(nèi)存池。4.2 靜態(tài)內(nèi)存池空閑鏈表是嵌入式鏈表的好搭檔一個很實用的做法是啟動時用靜態(tài)數(shù)組預分配固定數(shù)量的結(jié)點再用一個空閑鏈表串起來。需要結(jié)點時從空閑鏈表的頭部摘一個釋放時歸還到空閑鏈表頭部。這樣分配和釋放都是O(1)而且不會產(chǎn)生碎片。#define POOL_SIZE 32 static Node_t node_pool[POOL_SIZE]; static Node_t *free_list NULL; void MemoryPool_Init(void) { free_list node_pool[0]; for (int i 0; i POOL_SIZE - 1; i) { node_pool[i].next node_pool[i 1]; } node_pool[POOL_SIZE - 1].next NULL; } Node_t *Pool_Alloc(void) { if (free_list NULL) { return NULL; // 池空了觸發(fā)錯誤處理 } Node_t *node free_list; free_list free_list-next; return node; } void Pool_Free(Node_t *node) { node-next free_list; free_list node; }注意這個方案里分配出去和歸還的都是Node_t本身next字段復用了兩種語義在空閑鏈表里表示下一個空閑結(jié)點在業(yè)務鏈表里表示業(yè)務后繼。因為這兩種狀態(tài)不會同時出現(xiàn)所以復用完全安全。我維護過一個設備節(jié)點多路采集系統(tǒng)就是用這種池化管理鏈表存儲實測跑接近滿負荷的插入刪除頻率內(nèi)存占用紋絲不動比裸malloc的狀態(tài)穩(wěn)定很多。換到RAM更小的芯片上這個方案的移植也很簡單把池大小改小就行。4.3 中斷上下文里別碰鏈表除非你能證明它沒問題中斷里訪問鏈表最怕的是正在遍歷或插入時被嵌套中斷打斷導致鏈表狀態(tài)不一致。最簡單的規(guī)則是中斷里只做置標志位或投遞事件鏈表操作全部放到主循環(huán)或任務上下文。如果業(yè)務就必須在中斷里操作鏈表那至少做三件事關(guān)閉對應的中斷保護、統(tǒng)一所有鏈表訪問都走同一個臨界區(qū)、把鏈表操作本身寫成交互嵌套安全的版本。在我經(jīng)驗里前兩個能做到的項目已經(jīng)不多第三個幾乎沒有人真正做過。5. 鏈表調(diào)試踩坑記錄與自查清單5.1 野指針、斷鏈、HardFault三種最常見的排查鏈路我在一個傳感器節(jié)點項目里遇到過系統(tǒng)不定期HardFault查了一天才定位到鏈表刪除函數(shù)。癥狀很典型某個設備掉線后觸發(fā)刪除刪除完size減一但刪除時少判斷了一個“刪除的是唯一結(jié)點”的情況導致頭結(jié)點next指向了已經(jīng)被free的地址。之后主循環(huán)再遍歷鏈表拿到一個野地址一訪問就當場HardFault。排查思路分享給大家遇到這種問題別慌按順序來。第一步先看是不是每次都在同一個操作后崩潰把崩潰點附近的鏈表操作全部用LinkedList_Print打出來。第二步重點核對刪除函數(shù)里有沒有執(zhí)行prev-next del-next這是最高頻的斷鏈點。第三步檢查被free掉的結(jié)點的地址后面有沒有被再次讀取可以在free前給data域填一個明顯魔數(shù)比如0xDEADBEEF一旦打印鏈表時看到這個值就說明訪問了已釋放結(jié)點。頭插法順序?qū)懛磳е碌臄噫溡彩歉哳l問題。我見過這樣的代碼先把list-head-next賦給了node-next然后又把node賦值給list-head-next看起來沒問題但有些人會把這兩行寫反先讓head指向node再讓node指向head原來的next結(jié)果head的next變成了node自己鏈表從第二個結(jié)點開始全部丟失。這種斷鏈問題最惡心的地方在于頭兩個結(jié)點打印完全正常到第三個結(jié)點就訪問非法內(nèi)存。調(diào)試時可以先插入五個結(jié)點打印完整鏈表確認五個都在再排查后續(xù)問題。5.2 嵌入式鏈表的自查清單每次提交代碼前掃一遍我已經(jīng)把這個清單刻在腦子里每次寫完鏈表相關(guān)代碼都逐條過一遍分享給大家。初始化了嗎鏈表頭是從堆里分配還是靜態(tài)分配分配失敗有沒有處理頭結(jié)點到底存不存在所有遍歷和插入刪除起始位置是head還是head-next插入操作是先接新結(jié)點的next再接前驅(qū)的next嗎順序反了沒有刪除操作找到前驅(qū)了嗎被刪結(jié)點的next有沒有讓前驅(qū)繼承free之后還有沒有指針指向這塊內(nèi)存要不要置NULL鏈表長度size在插入和刪除后有沒有同步更新邊界情況全覆蓋了嗎空鏈表插入、刪除唯一結(jié)點、插入到首位置、刪除尾結(jié)點這四種情況測試過沒有中斷或回調(diào)函數(shù)里有沒有動鏈表如果需要動臨界保護開了嗎另外還建議在開發(fā)階段給鏈表的所有公開接口加上參數(shù)斷言比如assert(list ! NULL)、assert(node ! NULL)把錯誤暴露在最早的位置而不是炸在一個莫名其妙的HardFault里。嵌入式調(diào)試器雖然也能看內(nèi)存但通過斷言把問題“按在”出錯的那行代碼上省下的時間遠比多寫幾行斷言多。#include assert.h int LinkedList_InsertHead(LinkedList_t *list, SensorData_t data) { assert(list ! NULL); assert(list-head ! NULL); // 其余邏輯不變 }我在實際項目里因為這個斷言曾經(jīng)在deinit順序搞反時把空指針問題直接擋在了入口處日志里只打了一行assert失敗三分鐘就定位了問題。沒有它可能又要浪費小半天。寫到這里其實想說的是單向鏈表本身并不復雜復雜的是它牽出來的指針思維、內(nèi)存邊界和防御性編程習慣。這些能力在嵌入式開發(fā)的日常里比“會調(diào)庫”值錢得多。把鏈表吃透之后再看RTOS的任務鏈表、看驅(qū)動模型里的對象注冊表、甚至看內(nèi)核事件鏈表的實現(xiàn)你會發(fā)現(xiàn)它們骨子里都是同一套動作先畫圖、再處理next指針、最后管好內(nèi)存。希望這篇能幫你把這一環(huán)徹底打通。