想象一下，你正在開發一個簡單的遊戲，需要存儲玩家的角色列表，比如從1號玩家到100號玩家。如果用數組來存，刪除中間某個玩家時，後面的所有玩家都要往前挪位置，很麻煩。這時候，鏈表就派上用場了——每個玩家的信息（數據）旁邊只需要記住下一個玩家是誰（指針），不需要連續的內存空間，插入刪除只需要改幾個指針，就像調整糖葫蘆的竹籤一樣方便。
什麼是鏈表？¶
鏈表是一種線性數據結構，每個元素（稱爲“節點”）由兩部分組成：數據域（存具體信息）和指針域（存下一個/前一個節點的地址）。和數組不同，鏈表的節點在內存中不是連續的，就像散落的珠子用線串起來，線就是指針。
單鏈表：只能“單向”走的糖葫蘆串¶
單鏈表是最簡單的鏈表，每個節點只有一個指針，指向下一個節點。我們可以把它想象成一串糖葫蘆，每顆山楂（節點）只知道下一顆山楂在哪裏，不知道上一顆。
單鏈表的節點結構：¶
數據 | 指針 → 下一個節點
比如，存儲“玩家1→玩家2→玩家3”的單鏈表：
玩家1數據 | → 玩家2
玩家2數據 | → 玩家3
玩家3數據 | → null（表示結束）
單鏈表怎麼用？¶
- 遍歷：只能從第一個節點（頭節點）開始，順着指針一直走到最後一個節點（next爲null）。比如查第5個玩家，必須從頭開始數到第5個。
- 插入/刪除：要在中間插入一個節點，得先找到“目標節點的前一個節點”，然後修改指針。比如在玩家2和玩家3之間插入玩家4：
1. 先找到玩家2（原鏈表：玩家1→玩家2→玩家3）
2. 新建玩家4節點，讓玩家4的指針指向玩家3
3. 把玩家2的指針從指向玩家3，改爲指向玩家4
這樣就完成了插入，不需要移動其他節點。
但如果要刪除玩家3，必須先找到玩家2（前驅節點），把玩家2的指針直接指向玩家3的下一個節點（null）。
雙鏈表：能“前後”走的糖葫蘆串¶
雙鏈表比單鏈表多了一個指針，每個節點不僅知道下一個節點是誰，還知道前一個節點是誰。現在每顆山楂不僅能被下一顆牽着，還能被上一顆牽着，像帶了雙向掛鉤的糖葫蘆。
雙鏈表的節點結構：¶
前指針 ← 數據 → 後指針
比如，同樣存儲“玩家1→玩家2→玩家3”的雙鏈表：
null ← 玩家1數據 → 玩家2
玩家1 ← 玩家2數據 → 玩家3
玩家2 ← 玩家3數據 → null
雙鏈表怎麼用？¶
- 遍歷：可以從任意節點開始，既能向前走（通過prev指針），也能向後走（通過next指針）。比如從玩家2開始，能直接找到玩家1（用prev）或玩家3（用next）。
- 插入/刪除：在已知節點處插入或刪除時，雙鏈表更方便。比如在玩家2和玩家3之間插入玩家4：
1. 新建玩家4節點，把玩家4的prev指向玩家2
2. 把玩家4的next指向玩家3
3. 把玩家2的next從指向玩家3，改爲指向玩家4
4. 把玩家3的prev從指向玩家2，改爲指向玩家4
這樣一步到位，不需要再找“前驅”，因爲玩家2的prev已經是玩家1，玩家4可以直接和前後節點建立聯繫。
單鏈表 vs 雙鏈表：核心區別大總結¶
| 對比項 | 單鏈表 | 雙鏈表 |
|---|---|---|
| 節點結構 | 只有一個指針（next） | 兩個指針（prev + next） |
| 遍歷方向 | 只能單向遍歷（從頭到尾） | 雙向遍歷（可前可後） |
| 插入/刪除 | 需要先找到“前驅節點”，修改指針 | 直接通過prev/next指針操作，更簡單 |
| 內存佔用 | 少一個指針，節省內存 | 多一個指針，內存佔用稍高 |
| 適用場景 | 簡單單向數據存儲（如隊列） | 需要雙向操作（如瀏覽器歷史、雙向鏈表隊列） |
爲什麼要學雙鏈表？¶
如果你的遊戲只需要“從頭到尾”顯示玩家列表，單鏈表足夠。但如果要實現“同時顯示歷史記錄和未來記錄”（比如瀏覽器的前進後退），或者在鏈表中間頻繁插入刪除節點，雙鏈表更靈活。比如在手機通訊錄中，想在已知聯繫人處同時向前和向後添加聯繫人，雙鏈表能快速完成。
總結¶
- 單鏈表：像一串糖葫蘆，只能從左到右喫，簡單省空間，適合單向操作。
- 雙鏈表：像一串帶雙向掛鉤的糖葫蘆，能從左到右也能從右到左喫，功能更全但稍佔內存，適合需要雙向移動的場景。
初學者不用急着記複雜的操作，先記住“指針數量”和“遍歷方向”的區別，以後遇到實際問題（比如實現一個雙向鏈表隊列）再慢慢熟悉細節~