寫數(shù)據(jù)結(jié)構(gòu)相關(guān)的代碼這么多年我有一個(gè)很深的體會(huì)單鏈表用起來確實(shí)順手但真要往回找前驅(qū)節(jié)點(diǎn)的時(shí)候只能從頭再遍歷一遍總有種“開過頭了還要倒車”的別扭感。后來用上雙向鏈表兩個(gè)方向都能走很多場(chǎng)景一下子就順了。這篇就圍繞雙向鏈表展開帶你把結(jié)構(gòu)設(shè)計(jì)、插入刪除的指針操作、帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)的差異、逆置思路以及一份能直接跑起來的 C 實(shí)現(xiàn)完整過一遍。不管你是剛學(xué)數(shù)據(jù)結(jié)構(gòu)的學(xué)生還是工作中需要手寫鏈表的工程開發(fā)者這篇文章應(yīng)該都能給你一些參考。1. 雙向鏈表到底解決了什么問題1.1 從單鏈表的痛點(diǎn)說起鏈表的核心價(jià)值說白了就是“用不連續(xù)的內(nèi)存通過指針把節(jié)點(diǎn)串起來”。單鏈表里每個(gè)節(jié)點(diǎn)只存了一個(gè) next 指針指向下一個(gè)節(jié)點(diǎn)你只能從一個(gè)方向往前推進(jìn)。這種結(jié)構(gòu)有個(gè)很尷尬的缺點(diǎn)當(dāng)你想刪除某個(gè)節(jié)點(diǎn)或者想知道某個(gè)節(jié)點(diǎn)的前驅(qū)是誰就必須從頭開始找復(fù)雜度是 O(n)。我當(dāng)時(shí)做學(xué)生管理系統(tǒng)的時(shí)候就吃過這個(gè)虧。用戶要?jiǎng)h除某個(gè)學(xué)號(hào)對(duì)應(yīng)的記錄我的鏈表只存 next刪除操作必須用一個(gè) cur 和一個(gè) prev 同步往前走。稍微走神或者邊界條件沒判斷好指針就亂了。更難受的是如果業(yè)務(wù)上需要“從后往前處理數(shù)據(jù)”單鏈表幾乎沒法做只能先反轉(zhuǎn)整個(gè)鏈表或者用棧來輔助。這些操作不是不行而是每次都要繞路代碼里全是應(yīng)對(duì)“只能前進(jìn)”這種限制而寫的補(bǔ)丁。雙向鏈表的出現(xiàn)等于給每個(gè)節(jié)點(diǎn)補(bǔ)了一個(gè) prev 指針讓每個(gè)節(jié)點(diǎn)都知道“我前面是誰我后面是誰”。刪除時(shí)不用再從頭找前驅(qū)插入時(shí)也能直接拿到前后節(jié)點(diǎn)很多程序能寫得非常自然。1.2 雙向鏈表的結(jié)構(gòu)定義一個(gè)節(jié)點(diǎn)多出的那一根指針雙向鏈表節(jié)點(diǎn)比單鏈表節(jié)點(diǎn)只多了一個(gè)成員指向前驅(qū)節(jié)點(diǎn)的指針。C 語言的結(jié)構(gòu)體寫法大概是這樣的typedef struct DNode { int data; // 數(shù)據(jù)域 struct DNode *prev; // 指向前驅(qū)節(jié)點(diǎn) struct DNode *next; // 指向后繼節(jié)點(diǎn) } DNode;C 里如果你習(xí)慣用 struct 搭配構(gòu)造函數(shù)可以寫成這樣struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} };你也可以用生活里的情景來理解這個(gè)結(jié)構(gòu)一場(chǎng)演唱會(huì)入場(chǎng)觀眾排成一列每個(gè)觀眾手里拿著兩個(gè)對(duì)講機(jī)一個(gè)能聯(lián)系到前面的人一個(gè)能聯(lián)系到后面的人。這時(shí)候不管你是要通知前排的第一個(gè)人還是要通知后排的最后一個(gè)人都能直接對(duì)上話。這個(gè)“知道前面是誰”的能力就是 prev 指針帶來的。如果用文字串一個(gè)三節(jié)點(diǎn)鏈表的話它的形態(tài)是nullptr - A - B - C - nullptrA 的 prev 是空C 的 next 是空中間節(jié)點(diǎn)的指針兩兩互相指向。這樣的好處是從任意一個(gè)節(jié)點(diǎn)出發(fā)向前向后都能走通。1.3 雙向鏈表與單鏈表、循環(huán)鏈表的使用場(chǎng)景對(duì)比雙向鏈表并不是在所有場(chǎng)合都比單鏈表好多一個(gè)指針就多一份內(nèi)存開銷和維護(hù)復(fù)雜度。但如果把它放進(jìn)真實(shí)業(yè)務(wù)場(chǎng)景里看幾個(gè)典型場(chǎng)景很值得對(duì)比一下。對(duì)比維度單鏈表雙向鏈表循環(huán)鏈表內(nèi)存開銷每節(jié)點(diǎn) 1 個(gè)指針每節(jié)點(diǎn) 2 個(gè)指針取決于單/雙向找后繼O(1)O(1)O(1)找前驅(qū)O(n)O(1)尾部找頭 O(1)其他 O(n) 或 O(1) 取決于循環(huán)方向刪除給定節(jié)點(diǎn)通常 O(n)O(1)雙向循環(huán) O(1)實(shí)現(xiàn)復(fù)雜度低中中偏高我個(gè)人的使用經(jīng)驗(yàn)是如果業(yè)務(wù)只需要順序掃描單鏈表完全夠如果涉及頻繁的“按照當(dāng)前位置向前回退”比如瀏覽器歷史記錄、音樂播放器的上一首/下一首、編輯器里的撤銷重做雙向鏈表就特別合適。循環(huán)雙向鏈表在需要快速訪問“尾節(jié)點(diǎn)的下一個(gè)就是頭節(jié)點(diǎn)”這種場(chǎng)景也常見比如分時(shí)操作系統(tǒng)的進(jìn)程輪轉(zhuǎn)就可以用這種結(jié)構(gòu)來模擬環(huán)形隊(duì)列。2. 核心操作拆解從初始化到遍歷2.1 帶頭結(jié)點(diǎn)還是不帶頭結(jié)點(diǎn)我的選擇很多教材里喜歡用帶哨兵頭結(jié)點(diǎn)的鏈表也就是說鏈表的最前面人為放一個(gè)不存儲(chǔ)有效數(shù)據(jù)的節(jié)點(diǎn)它的 next 指向真正的第一個(gè)數(shù)據(jù)節(jié)點(diǎn)。還有一種方式是不帶頭結(jié)點(diǎn)head 指針直接指向第一個(gè)數(shù)據(jù)節(jié)點(diǎn)空鏈表時(shí) head 為 nullptr。這兩種方式?jīng)]有絕對(duì)的好壞但我這里要給你一個(gè)明確的建議學(xué)習(xí)階段先把“不帶頭結(jié)點(diǎn)”吃透寫工程代碼時(shí)再看項(xiàng)目風(fēng)格決定。不帶頭結(jié)點(diǎn)更接近底層的真實(shí)狀態(tài)空表就是 nullptr插入刪除時(shí)的分支判斷都要自己處理。剛開始會(huì)覺得麻煩但你把邊界條件想清楚之后對(duì)指針理解會(huì)深很多。帶頭結(jié)點(diǎn)相當(dāng)于給鏈表加了一個(gè)“緩沖區(qū)”頭插和空表刪除都不需要單獨(dú)處理 head代碼分支會(huì)少一些但要始終記得 head-next 才是真正的數(shù)據(jù)節(jié)點(diǎn)。用不帶頭結(jié)點(diǎn)初始化也就是一行代碼Node* head nullptr;用帶頭結(jié)點(diǎn)初始化則是先 new 一個(gè)哨兵Node* dummy new Node(-1); dummy-next nullptr; dummy-prev nullptr;我覺得初學(xué)者可以先從不帶頭結(jié)點(diǎn)入手把所有邊界問題親手試一遍后續(xù)再切換到帶哨兵的寫法會(huì)非常輕松。2.2 插入操作先連新節(jié)點(diǎn)再斷舊鏈接雙向鏈表的插入最重要的口訣只有一句話先把新節(jié)點(diǎn)的兩個(gè)指針都接好再修改舊節(jié)點(diǎn)的指針。這句話聽起來簡(jiǎn)單但很多人第一次寫的時(shí)候會(huì)翻車。我見過不少同學(xué)在頭插時(shí)先把 head 的 prev 改了然后 new 節(jié)點(diǎn)的 next 還沒指過去鏈表直接斷成兩截。我們分幾種情況來看。頭插在鏈表最前面插入bool pushFront(Node* head, int val) { Node* newNode new Node(val); if (head nullptr) { head newNode; return true; } newNode-next head; newNode-prev nullptr; head-prev newNode; head newNode; return true; }尾插在鏈表最后面插入bool pushBack(Node* head, int val) { Node* newNode new Node(val); if (head nullptr) { head newNode; return true; } Node* cur head; while (cur-next ! nullptr) { cur cur-next; } cur-next newNode; newNode-prev cur; return true; }指定位置插入就稍微復(fù)雜一點(diǎn)比如在第 index 個(gè)位置插入。核心是先通過循環(huán)把指針移動(dòng)到目標(biāo)位置的前一個(gè)節(jié)點(diǎn) cur然后按照固定順序接入bool insertAtIndex(Node* head, int index, int val) { if (index 0) return false; Node* newNode new Node(val); if (index 0) { newNode-next head; newNode-prev nullptr; if (head ! nullptr) head-prev newNode; head newNode; return true; } Node* cur head; for (int i 0; i index - 1 cur ! nullptr; i) { cur cur-next; } if (cur nullptr) return false; newNode-next cur-next; newNode-prev cur; if (cur-next ! nullptr) { cur-next-prev newNode; } cur-next newNode; return true; }為什么一定要先處理 newNode 的 next 和 prev因?yàn)檫@個(gè)時(shí)候 newNode 還獨(dú)立在外面它怎么指都不會(huì)影響原鏈表。一旦你先把 cur-next 改了原鏈表右半段就找不到了你要想再把 newNode 串進(jìn)去就需要額外用一個(gè)臨時(shí)指針保存代碼會(huì)麻煩得多。凡是涉及“插入”的操作先孤立新節(jié)點(diǎn)再拆舊鏈接這是個(gè)通用定律。2.3 刪除操作兩個(gè)方向的指針都要處理刪除比插入更容易踩坑因?yàn)橐尫艃?nèi)存指針一旦處理錯(cuò)要么崩潰要么泄漏。刪除的關(guān)鍵在于先把節(jié)點(diǎn)從鏈中“摘下來”再 delete。分情況來看刪頭節(jié)點(diǎn)bool deleteFront(Node* head) { if (head nullptr) return false; Node* tmp head; head head-next; if (head ! nullptr) head-prev nullptr; delete tmp; return true; }刪任意節(jié)點(diǎn)比如按值刪除第一個(gè)匹配的節(jié)點(diǎn)bool deleteByValue(Node* head, int val) { if (head nullptr) return false; Node* cur head; while (cur ! nullptr cur-data ! val) { cur cur-next; } if (cur nullptr) return false; if (cur head) { head cur-next; if (head ! nullptr) head-prev nullptr; delete cur; return true; } if (cur-prev ! nullptr) cur-prev-next cur-next; if (cur-next ! nullptr) cur-next-prev cur-prev; delete cur; return true; }這里有個(gè)容易忽略的細(xì)節(jié)如果鏈表只有一個(gè)節(jié)點(diǎn)刪除前 head 是 cur刪除后 head 應(yīng)該變成 nullptr。上面代碼處理了 head 的情況所以這個(gè)邊界自然覆蓋到了。另外一個(gè)細(xì)節(jié)是刪除完成后要把 cur 的指針成員也清理一下雖然 delete 之后不一定出問題但習(xí)慣上讓 cur-prev cur-next nullptr 之后再 delete調(diào)試時(shí)可讀性更好。面試時(shí)如果考“給定一個(gè)節(jié)點(diǎn)指針怎么在 O(1) 時(shí)間內(nèi)刪除它”雙向鏈表就非常容易回答直接拿到 node-prev 和 node-next互相接起來再 delete node 就行完全不用從頭遍歷。2.4 遍歷與前驅(qū)訪問遍歷雙向鏈表和單鏈表沒太大區(qū)別正著走一路 next 就行void printList(Node* head) { Node* cur head; while (cur ! nullptr) { std::cout cur-data - ; cur cur-next; } std::cout nullptr std::endl; }但是反向遍歷就很舒服了只需要先走到最后一個(gè)節(jié)點(diǎn)然后一路走 prevvoid printReverse(Node* head) { if (head nullptr) return; Node* cur head; while (cur-next ! nullptr) cur cur-next; while (cur ! nullptr) { std::cout cur-data - ; cur cur-prev; } std::cout nullptr std::endl; }這個(gè)能力在需要“從后往前匯總”的業(yè)務(wù)里特別有用。比如你在做文件版本記錄最新版本在尾部需要從最新往舊版本回溯用雙向鏈表就能直接從尾巴往回遍歷不需要反轉(zhuǎn)鏈表。3. 可運(yùn)行的C實(shí)現(xiàn)手把手寫一份完整代碼3.1 結(jié)構(gòu)體定義與基本工具函數(shù)下面我給出一個(gè)相對(duì)完整的不帶頭結(jié)點(diǎn)雙向鏈表實(shí)現(xiàn)。先建立一個(gè)頭文件風(fēng)格的完整主體方便你直接復(fù)制運(yùn)行#include iostream struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} }; class DoublyLinkedList { private: Node* head; void destroy() { Node* cur head; while (cur ! nullptr) { Node* nextNode cur-next; cur-prev nullptr; cur-next nullptr; delete cur; cur nextNode; } head nullptr; } public: DoublyLinkedList() : head(nullptr) {} ~DoublyLinkedList() { destroy(); } bool empty() const { return head nullptr; } void pushFront(int val) { Node* newNode new Node(val); if (head nullptr) { head newNode; return; } newNode-next head; newNode-prev nullptr; head-prev newNode; head newNode; } void pushBack(int val) { Node* newNode new Node(val); if (head nullptr) { head newNode; return; } Node* cur head; while (cur-next ! nullptr) cur cur-next; cur-next newNode; newNode-prev cur; } bool insertAtIndex(int index, int val) { if (index 0) return false; Node* newNode new Node(val); if (index 0) { pushFront(val); return true; } Node* cur head; int i 0; while (cur ! nullptr i index - 1) { cur cur-next; i; } if (cur nullptr) return false; newNode-next cur-next; newNode-prev cur; if (cur-next ! nullptr) { cur-next-prev newNode; } cur-next newNode; return true; } bool deleteByValue(int val) { if (head nullptr) return false; Node* cur head; while (cur ! nullptr cur-data ! val) cur cur-next; if (cur nullptr) return false; if (cur head) { head cur-next; if (head ! nullptr) head-prev nullptr; } else { if (cur-prev ! nullptr) cur-prev-next cur-next; if (cur-next ! nullptr) cur-next-prev cur-prev; } cur-prev nullptr; cur-next nullptr; delete cur; return true; } void print() const { Node* cur head; while (cur ! nullptr) { std::cout cur-data - ; cur cur-next; } std::cout nullptr std::endl; } void printReverse() const { if (head nullptr) return; Node* cur head; while (cur-next ! nullptr) cur cur-next; while (cur ! nullptr) { std::cout cur-data - ; cur cur-prev; } std::cout nullptr std::endl; } }; int main() { DoublyLinkedList list; list.pushBack(1); list.pushBack(2); list.pushBack(3); list.pushFront(0); list.print(); // 0 - 1 - 2 - 3 - nullptr list.insertAtIndex(2, 99); list.print(); // 0 - 1 - 99 - 2 - 3 - nullptr list.deleteByValue(1); list.print(); // 0 - 99 - 2 - 3 - nullptr list.printReverse(); // 3 - 2 - 99 - 0 - nullptr return 0; }這份代碼里有幾個(gè)細(xì)節(jié)我覺得值得單獨(dú)拿出來說一說。一個(gè)是 destroy 函數(shù)。我看到很多教材在析構(gòu)里直接 while 循環(huán) delete cur然后 cur cur-next。這樣寫順序上其實(shí)是危險(xiǎn)的因?yàn)?delete cur 之后cur-next 已經(jīng)屬于已釋放內(nèi)存再去訪問它是未定義行為。正確做法是先把下一個(gè)節(jié)點(diǎn)指針存下來再釋放當(dāng)前節(jié)點(diǎn)。我在 destroy 里用 nextNode 暫存的辦法就是為了避免懸垂指針。另一個(gè)細(xì)節(jié)是 insertAtIndex 的第 0 位置我直接復(fù)用了 pushFront避免邏輯重復(fù)。很多初學(xué)者會(huì)寫兩套非常相似的頭插邏輯后續(xù)維護(hù)時(shí)容易改了這個(gè)忘了那個(gè)。3.2 指定位置插入的完整實(shí)現(xiàn)與運(yùn)行示例指定位置插入是最能體現(xiàn)“雙指針聰明之處”的一個(gè)操作。前面代碼里給了實(shí)現(xiàn)這里我用一個(gè)具體例子幫你逐步拆解。假設(shè)當(dāng)前鏈表是nullptr - 0 - 1 - 2 - 3 - nullptr我想在 index 等于 2 的位置插入 99也就是期望結(jié)果nullptr - 0 - 1 - 99 - 2 - 3 - nullptr代碼里 cur 要移動(dòng)到 index - 1也就是下標(biāo)為 1 的節(jié)點(diǎn)值為 1。這時(shí)候newNode-next cur-next于是 99 的 next 指向了 2。newNode-prev cur于是 99 的 prev 指向了 1。cur-next-prev newNode于是 2 的 prev 指向了 99。cur-next newNode于是 1 的 next 指向了 99。新節(jié)點(diǎn)進(jìn)來后原來的 1 - 2 鏈接變成了 1 - 99 - 2完美插入。這個(gè)過程中最關(guān)鍵的是第二步和第三步的順序必須保證 99 已經(jīng)“握住了”2再讓 2 回頭指向 99。如果你先把 1-next 改成 99那么 2 就隨著斷開的鏈接一起丟失了后面的步驟就會(huì)出錯(cuò)。index 越界時(shí)比如 index 等于 100for 循環(huán)會(huì)一直走到 cur 為 nullptr這時(shí)候直接返回 false 即可。這個(gè)越界判斷是很多剛寫鏈表的人容易漏掉的漏掉的后果就是空指針訪問程序直接崩。3.3 雙向鏈表的逆置技巧逆置鏈表是熱搜詞里的高頻內(nèi)容雙向鏈表逆置其實(shí)比單鏈表更直觀因?yàn)槊總€(gè)節(jié)點(diǎn)都有兩個(gè)方向的指針逆置的本質(zhì)就是“把每個(gè)節(jié)點(diǎn)的兩個(gè)指針交換方向”然后把頭指針指向原來的尾巴。思路是這樣的從 head 開始遍歷每個(gè)節(jié)點(diǎn)把 node-next 和 node-prev 交換。遍歷結(jié)束后原來鏈表的最后一個(gè)節(jié)點(diǎn)變成新的 head。用代碼實(shí)現(xiàn)void reverse() { if (head nullptr) return; Node* cur head; Node* newHead head; while (cur ! nullptr) { std::swap(cur-next, cur-prev); newHead cur; cur cur-prev; // 交換后原 next 變成了 prev } head newHead; }這里最容易踩的坑在遍歷移動(dòng)那一步。交換 next 和 prev 之后原來 cur 的后繼節(jié)點(diǎn)變成了 cur-prev所以你必須用 cur cur-prev 而不是 cur cur-next。我第一次寫這個(gè)函數(shù)時(shí)交換之后下意識(shí)繼續(xù)走 cur cur-next結(jié)果死循環(huán)后來畫了一下圖才反應(yīng)過來。這就是那種“代碼只有一行邏輯卻要思考五分鐘”的典型例子。如果你想保持泛化性也可以用遞歸逆置但鏈表一長(zhǎng)就容易爆棧實(shí)際工程中我更推薦這個(gè)原地 O(1) 空間的迭代版。3.4 內(nèi)存釋放寫鏈表最容易忽略的環(huán)節(jié)很多教材寫鏈表只講插入刪除不講析構(gòu)導(dǎo)致很多同學(xué)學(xué)完整章后對(duì)“鏈表到底要不要釋放內(nèi)存”完全沒有概念。實(shí)際上鏈表節(jié)點(diǎn)全是 new 出來的不釋放就是內(nèi)存泄漏程序跑久了內(nèi)存會(huì)越來越大。雙向鏈表釋放時(shí)要注意如果節(jié)點(diǎn)里還有指向其他動(dòng)態(tài)分配資源的指針需要先釋放那些資源再釋放節(jié)點(diǎn)本身。節(jié)點(diǎn)本身的內(nèi)存釋放順序建議先斷開 prev 和 next 指針再用 delete 刪除節(jié)點(diǎn)最后再把 cur 指向暫存的下一個(gè)節(jié)點(diǎn)。代碼已經(jīng)在 3.1 節(jié)的 destroy 里體現(xiàn)。我還見過一種非常隱蔽的泄漏刪除節(jié)點(diǎn)時(shí)沒有把 cur-prev 和 cur-next 置空就 delete。表面上看內(nèi)存是釋放了但如果這個(gè) cur 還被其他地方引用而引用它的代碼又在做夢(mèng)那么訪問 cur-next 就是一個(gè)懸垂指針輕則讀到垃圾值重則直接段錯(cuò)誤。所以我個(gè)人習(xí)慣在 delete 之前把節(jié)點(diǎn)的 prev 和 next 都置為 nullptr。這不是 C 規(guī)范要求的但能減少調(diào)試時(shí)的迷惑。4. 常見問題與排查實(shí)錄4.1 經(jīng)典翻車現(xiàn)象一插入后鏈表斷成兩截這是雙向鏈表初學(xué)者最容易遇到的問題?，F(xiàn)象是插入了新節(jié)點(diǎn)但打印鏈表時(shí)發(fā)現(xiàn)只能打到某個(gè)位置后面全部丟失。比如原鏈表 1-2-3在中間插入 4 后輸出變成 1-4后面 2、3 都不見了。原因幾乎總是出在插入順序上。比如你先執(zhí)行了 cur-next newNode那么原鏈表中 cur 的后半段就通過原來的 cur-next 斷開了。此時(shí)如果 newNode 的 next 還沒有指到原來的后半段這部分鏈表就成了孤兒區(qū)。解決辦法就是我在 2.2 節(jié)強(qiáng)調(diào)的先讓 newNode-next 指向 cur-next再改 cur-next。也就是說新節(jié)點(diǎn)必須先“握住舊鏈接的右邊”舊節(jié)點(diǎn)才能“松開手”。排查思路也很簡(jiǎn)單不要盯代碼硬看畫箭頭圖最有效。把 cur、newNode、cur-next 三個(gè)節(jié)點(diǎn)畫出來給每個(gè)指針畫一條線按代碼執(zhí)行順序一步步連線斷點(diǎn)一眼就能看出來。4.2 經(jīng)典翻車現(xiàn)象二空指針訪問導(dǎo)致崩潰空指針崩潰一般出現(xiàn)在三種情況鏈表為空時(shí)執(zhí)行插入或刪除尾插時(shí) cur 跑到 nullptr 卻沒發(fā)現(xiàn)刪除時(shí)沒有判斷 cur-next 是否為空就直接訪問 cur-next-prev。典型代碼長(zhǎng)這樣// 錯(cuò)誤示范 cur-next-prev newNode;如果 cur-next 是 nullptr這行代碼直接崩。正確寫法是先判斷再操作if (cur-next ! nullptr) { cur-next-prev newNode; }還有一種情況是“刪除尾巴節(jié)點(diǎn)”。當(dāng) cur-next 為 nullptr你執(zhí)行 cur-prev-next cur-next也就是把前驅(qū)的 next 設(shè)為 nullptr這沒問題。但如果你不判斷 cur-prev 是否存在刪除頭節(jié)點(diǎn)時(shí)就會(huì)出問題。好在刪除頭節(jié)點(diǎn)我們已經(jīng)有單獨(dú)分支處理這也是為什么我建議刪除操作先判斷 cur head。排查空指針崩潰最好的工具其實(shí)就是調(diào)試器。在崩潰那一行看調(diào)用棧找到是哪個(gè)指針是 nullptr然后往前梳理它的值是什么時(shí)候變成 nullptr 的。鏈表調(diào)試十次有九次都是這么查出來的。4.3 經(jīng)典翻車現(xiàn)象三刪除節(jié)點(diǎn)后鏈表全亂刪除節(jié)點(diǎn)的典型錯(cuò)誤有兩個(gè)方向一是“忘接”刪完一個(gè)節(jié)點(diǎn)后前驅(qū)的 next 和后繼的 prev 沒有正確對(duì)接鏈表斷成兩段二是“接錯(cuò)”比如寫了 cur-prev-next cur-prev把前驅(qū)的 next 指向了自己形成環(huán)。第二個(gè)問題特別危險(xiǎn)因?yàn)樗粫?huì)立刻崩潰而是會(huì)讓遍歷陷入死循環(huán)程序看起來“卡住”。比如打印鏈表時(shí)輸出一直在重復(fù)同一個(gè)節(jié)點(diǎn)那八成就是指針形成了環(huán)。我的排查建議是在 delete 節(jié)點(diǎn)之前先用臨時(shí)節(jié)點(diǎn)把需要保留的信息保存好。刪之前問自己三句話前驅(qū)的 next 應(yīng)該指向哪里后繼的 prev 應(yīng)該指向哪里如果要釋放當(dāng)前節(jié)點(diǎn)我是不是已經(jīng)保存了下一步需要訪問的位置這三句話都想清楚刪除節(jié)點(diǎn)基本不會(huì)出錯(cuò)。另一點(diǎn)刪除節(jié)點(diǎn)和釋放內(nèi)存是兩件事摘鏈和 delete 最好分開寫別在一行里玩花活否則出了問題不容易定位。4.4 面試與考試中的雙向鏈表高頻考點(diǎn)這些年看過的鏈表題和面試題雙向鏈表相關(guān)的考點(diǎn)其實(shí)很集中。最?？嫉氖墙o定一個(gè)節(jié)點(diǎn)指針O(1) 時(shí)間內(nèi)刪除該節(jié)點(diǎn)。你只需要訪問它的 prev 和 next把兩者串起來再刪除當(dāng)前節(jié)點(diǎn)。這就是雙向鏈表比單鏈表“值錢”的核心點(diǎn)。第二個(gè)高頻考點(diǎn)是“雙向鏈表的逆置”?？碱}經(jīng)常會(huì)在末尾加一句“要求原地實(shí)現(xiàn)空間復(fù)雜度 O(1)”那就是要求你用 swap next/prev 的迭代法而不是新建一個(gè)鏈表。平時(shí)在一張紙上手寫幾遍這個(gè)代碼面試時(shí)就能寫得又快又穩(wěn)。第三個(gè)高頻考點(diǎn)是“帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表”。這種結(jié)構(gòu)在 Linux 內(nèi)核鏈表里非常常見它的特點(diǎn)是 head 的 prev 指向尾節(jié)點(diǎn)尾節(jié)點(diǎn)的 next 指向 head遍歷時(shí)既可以正向走一圈回到頭也可以反向走一圈。寫這種鏈表時(shí)最關(guān)鍵的是在插入和刪除時(shí)保持循環(huán)性質(zhì)的完整性也就是所有涉及邊界節(jié)點(diǎn)的地方都要考慮“最后一個(gè)節(jié)點(diǎn)的 next 其實(shí)是 head”而不是 nullptr。我個(gè)人的學(xué)習(xí)建議是把 3.1 節(jié)那份代碼自己默寫一遍然后試著改成帶頭結(jié)點(diǎn)的版本再改成循環(huán)版本。三種形態(tài)都寫一遍你對(duì)鏈表結(jié)構(gòu)的理解就算真正過關(guān)了。最后說一個(gè)很實(shí)在的調(diào)試經(jīng)驗(yàn)鏈表這類指針操作的問題絕大多數(shù)都能靠“在紙上畫方框和箭頭”解決別急著在 IDE 里不停加打印。調(diào)試打印輸出很重要尤其可以寫一個(gè)像 printList 一樣的輔助函數(shù)在每次插入刪除后打一遍全鏈表這樣能直觀看到結(jié)構(gòu)被改成了什么樣。想追蹤當(dāng)前節(jié)點(diǎn)就打印當(dāng)前節(jié)點(diǎn)和前驅(qū)后繼的地址比對(duì)地址是否和你預(yù)想的一致。這個(gè)習(xí)慣我用了很多年可以說幫我在各種指針迷宮里少走了一半彎路。