雙重連結串列
雙連結串列是一種連結串列 。雙向連結串列的節點有兩個指向其他節點的指標，下一個和前一個。它被稱為雙連結串列，因為每個節點只有兩個指向其他節點的指標。雙向連結串列可以具有頭部和/或尾部指標。
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │
│"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
▲ △ △
HEAD │ │ DOUBLE │
└──── REFERENCE ────┘
雙連結串列比單連結串列更節省空間; 但是，對於某些操作，它們可以顯著提高時間效率。一個簡單的例子是 get 函式，對於帶有頭部和尾部引用的雙向連結串列，它將從頭部或尾部開始，具體取決於要獲取的元素的索引。對於 n 元素列表，要獲取 n/2 + i 索引元素，帶有頭/尾引用的單連結串列必須遍歷 n/2 + i 節點，因為它不能從尾部返回。帶有頭/尾引用的雙向連結串列只需要遍歷 n/2 - i 節點，因為它可以從尾部返回，以相反的順序遍歷列表。