目前我們所學到的鏈表，無論是動態鏈表還是靜態鏈表，表中各個節點都只包含一個指針（游標），且都統一指向直接后繼節點，這類鏈表又統稱為單向鏈表或單鏈表。雖然單鏈表能 100% 存儲邏輯關系為 "一對一" 的數據，但在解決某些實際問題時，單鏈表的執行效率并不高。例如，若實際問題中需要頻繁地查找某個結點的前驅結點，使用單鏈表存儲數據顯然沒有優勢，因為單鏈表的強項是從前往后查找目標元素，不擅長從后往前查找元素。解決此類問題，可以建立雙向鏈表（簡稱雙鏈表）。

(資料圖片僅供參考)

雙向鏈表是什么

從名字上理解雙向鏈表，即鏈表是 "雙向" 的，如圖?1 所示：

“雙向”指的是各節點之間的邏輯關系是雙向的，頭指針通常只設置一個。

從圖 1 中可以看到，雙向鏈表中各節點包含以下 3 部分信息（如圖 2 所示）：

指針域：用于指向當前節點的直接前驅節點；

數據域：用于存儲數據元素。

指針域：用于指向當前節點的直接后繼節點；

因此，雙鏈表的節點結構用 C 語言實現為：

雙向鏈表的創建

同單鏈表相比，雙鏈表僅是各節點多了一個用于指向直接前驅的指針域。因此，我們可以在單鏈表的基礎輕松實現對雙鏈表的創建。需要注意的是，與單鏈表不同，雙鏈表創建過程中，每創建一個新節點都要與其前驅節點建立兩次聯系，分別是：

將新節點的 prior 指針指向直接前驅節點；

將直接前驅節點的 next 指針指向新節點；

這里給出創建雙向鏈表的 C 語言實現代碼：

我們可以嘗試著在 main 函數中輸出創建的雙鏈表，C 語言代碼如下：

程序運行結果：

1 <-> 2 <-> 3 <-> 4 <-> 5鏈表中第 4 個節點的直接前驅是：3

關鍵詞：