在鏈結陣列系列的第一篇文章有稍微提過，鏈結陣列除了有單向還有雙向，它的概念其實差不多，就是鏈結陣列的節點，不只有儲存下一個節點的位置(Next)，還有儲存上一個節點的位置(Prev)，如下圖所示：

操作

雙向鏈結陣列在訪問節點資料的部分和單向鏈結陣列相同，透過美個節點指向下一個節點位置，逐一遍歷整個鏈結陣列訪問指定索引的節點，因此也是O(n)時間的查詢操作。

新增與刪除操作的部分和單向鏈結陣列類似，只是要多一個動作；原先只需要改變前一個節點指向下一個節點的位置，雙向鏈結陣列則需要多設定指向前一個節點的位置。

新增

1. 建立一個新的節點，並移動至指定索引位置。
2. 設定新節點的前一個節點為(Prev)，下一個節點為(Next)。
3. 設定前一個節點(Prev)指向下一個節點位置為新節點；同理，設定下一個節點(Next)指向前一個節點位置為新節點

刪除

1. 建立一個新的節點，並移動至指定索引位置。
2. 設定前一個節點(Prev)指向下一個節點位置為指定索引位置(Curr)的下一個節點(Next)；同理，設定下一個節點(Next)指向前一個節點位置為指定索引位置(Curr)的前一個節點(Prev)。

LeetCode Problem

• 707. Design Linked List

小結

知道單向鏈結陣列後，學習雙向鏈結陣列並不困難，只是新增或刪除操作會需要多設定前一個節點位置，在查詢節點上也會比較靈活一點。