2.4　雙向鏈表

雙向鏈表也稱作雙鏈表，是鏈表的一種。雙向鏈表是有前后兩個方向的。與單鏈表不同的是，雙向鏈表帶有兩個引用：一個是指向后一個結(jié)點（通常稱作后繼結(jié)點）的引用；另一個是指向前一個結(jié)點（通常稱作前驅(qū)結(jié)點）的引用。

雙向鏈表第一個結(jié)點稱作頭結(jié)點，可以從頭結(jié)點開始向后正向遍歷雙向鏈表中的元素。頭結(jié)點無前驅(qū)結(jié)點。雙向鏈表的最后一個結(jié)點稱作尾結(jié)點，可以從尾結(jié)點開始向前逆向遍歷雙向鏈表中的元素。尾結(jié)點無后繼結(jié)點。雙向鏈表如圖2-15所示。

單鏈表只能從一個方向訪問鏈表中的元素（通常是從前向后依次訪問）。與單鏈表相比，雙向鏈表的明顯優(yōu)勢在于，雙向鏈表可以方便地從兩個方向（從前向后和從后向前）訪問其中的元素。

2.4.1　雙向鏈表添加元素

向雙向鏈表中添加元素需要修改前一個結(jié)點的后繼結(jié)點的引用和后一個結(jié)點的前驅(qū)結(jié)點的引用。

雙向鏈表添加元素前如圖2-16所示。

在雙向鏈表第i個位置添加元素后的示意圖如圖2-17所示。

2.4.2　雙向鏈表查找元素

雙向鏈表的查找可以分為兩種情況：一種是從頭向尾查找元素；另一種是從尾向頭查找元素。雙向鏈表查找元素的示意圖如圖2-18所示。

2.4.3　雙向鏈表刪除元素

雙向鏈表刪除元素是雙向鏈表添加元素的反向操作。

雙向鏈表刪除element元素之前如圖2-19所示。

雙向鏈表刪除element元素之后的示意圖如圖2-20所示。

2.4.4　雙向循環(huán)鏈表

從雙向鏈表可以看出，雙向鏈表的頭結(jié)點沒有前驅(qū)結(jié)點，雙向鏈表的尾結(jié)點沒有后繼結(jié)點。為了解決頭尾結(jié)點的問題，誕生了雙向循環(huán)鏈表。雙向循環(huán)鏈表在雙向鏈表的基礎(chǔ)上將頭結(jié)點和尾結(jié)點進行首尾相連。雙向循環(huán)鏈表如圖2-21所示。

雙向鏈表只是在單鏈表的基礎(chǔ)上增加了一個“反向單鏈表”。雙向循環(huán)鏈表是在雙向鏈表的基礎(chǔ)上使雙向鏈表首尾相連。讀者可以參考單鏈表的實現(xiàn)，自行開發(fā)實現(xiàn)雙向鏈表和雙向循環(huán)鏈表。

2.4.5　雙向鏈表常見面試考點

（1）雙向鏈表的概念：雙向鏈表可以看成是由兩個方向相反的單鏈表組成的。雙向鏈表既可以從前向后遍歷，又可以從后向前遍歷。

（2）雙向鏈表的存儲：雙向鏈表是使用離散的存儲結(jié)構(gòu)存儲數(shù)據(jù)的。雙向鏈表中每個結(jié)點都有一個指向前驅(qū)結(jié)點的引用和指向后繼結(jié)點的引用。

（3）雙向鏈表的優(yōu)點：

·　雙向鏈表不需要使用連續(xù)的存儲空間存儲數(shù)據(jù)。

·　雙向鏈表沒有固定的容量。

·　添加或刪除單鏈表中的元素只需修改相關(guān)結(jié)點的引用，無須移動其他元素。

·　雙向鏈表可以從正反兩個反向進行遍歷。

·　雙向循環(huán)鏈表相比于雙向鏈表，每個結(jié)點的屬性都是完整的，沒有需要單獨處理的結(jié)點（不存在前驅(qū)結(jié)點或者后繼結(jié)點為空的結(jié)點）。

（4）雙向鏈表的缺點：

·　訪問雙向鏈表中的元素必須從第一個結(jié)點或者從最后一個結(jié)點開始遍歷，依次訪問下一個結(jié)點，直至找到所需的元素位置。因此，訪問雙向鏈表的時間復(fù)雜度為O(n)。

·　雙向鏈表每個結(jié)點保存了前驅(qū)結(jié)點和后繼結(jié)點的引用，每個結(jié)點占用更多的存儲空間。

（5）JDK中的實現(xiàn)：JDK中的LinkedList實現(xiàn)了雙向鏈表，并提供更多高級特性，詳情可參見4.3節(jié)。