有了前項連結串列的基礎, 我們在寫連結串列程式碼的時候, 就不顯得太難
因為連結串列比前項連結串列多一個指標, 也就是 previous
, 用於指向當前位置的前一個結點
我們同樣使用圖表的方式來看一下連結串列的結構
通過和前項連結串列的對比, 我們發現連結串列除了每個結點多了一個指標之外, last
的下一個結點指向了 first
, first
的前一個結點指向了 last
這樣會導致一個有趣的結果, 也就是 List 的疊代器不會超過目前 List 的範圍. 而如果你看過之前前項連結串列的程式碼後, 你會發現, 在疊代器中, 我們處理疊代器超過界定的方法是通過 throw
擲出例外情況
但是 first
和 last
在插入和擦除的時候, first
的 previous
和 last
的 next
是不會改變的, 因此插入和擦除的操作只需要更改新結點的 first
和 next
, 以及插入位置所對應結點的 next
和插入位置之後所對應結點的 previous
即可. 因為多了一個結點, 所以訪問起來是雙向的, 在插入和擦除的操作會比前項連結串列更加複雜
資料結構 list : GitHub 點擊直達
自創文章, 原著 : Jonny. 如若閣下需要轉發, 在已經授權的情況下請註明本文出處 :