有了前項連結串列的基礎, 我們在寫連結串列程式碼的時候, 就不顯得太難

因為連結串列比前項連結串列多一個指標, 也就是 previous, 用於指向當前位置的前一個結點

我們同樣使用圖表的方式來看一下連結串列的結構

通過和前項連結串列的對比, 我們發現連結串列除了每個結點多了一個指標之外, last 的下一個結點指向了 first, first 的前一個結點指向了 last

這樣會導致一個有趣的結果, 也就是 List 的疊代器不會超過目前 List 的範圍. 而如果你看過之前前項連結串列的程式碼後, 你會發現, 在疊代器中, 我們處理疊代器超過界定的方法是通過 throw 擲出例外情況

但是 first 和 last 在插入和擦除的時候, first 的 previous 和 last 的 next 是不會改變的, 因此插入和擦除的操作只需要更改新結點的 first 和 next, 以及插入位置所對應結點的 next 和插入位置之後所對應結點的 previous 即可. 因為多了一個結點, 所以訪問起來是雙向的, 在插入和擦除的操作會比前項連結串列更加複雜

資料結構 list : GitHub 點擊直達