循環雙向鏈表和尾指針雙向鏈表

Question

使用循環指針和尾指針構建雙向鏈表的優點/缺點是什麼？哪一個更適合建立一個deque？

從我的觀點來看，他們在做所有搜索，插入和刪除節點方面基本相同。唯一不同的是，對於尾指針雙鏈表，您需要將尾指針指向最後一個節點，並且每次在尾部之後插入新節點時都需要更新它。此外，在循環鏈表中，第一個節點鏈接到最後一個節點，反之亦然，而在尾指針中，head-> prev和tail->指向空指針。 我認爲他們都是建立一個deque的greate。這一切都取決於你希望你的程序運行的方式。如果你希望你的程序能夠快速地在頭尾節點之間來回運行，使用循環方式，否則尾指針應該足夠。

這是我對這個問題的回答。由於我還沒有建立任何循環雙向鏈表，我沒有任何關於它在機器上運行的經驗，但我懷疑它會像尾指針一樣快。任何建議？並感謝大家的投入。

Answer 1

圓形雙鏈表可能是首選，因爲您可以有效地從開始或結束添加/刪除，並且它使用簡單的統一數據結構。

實現循環dbl鏈表的最簡單方法是容納與所有其他節點相同類型的'head'節點，但始終具有'null'項/值，並且僅用於容納下一個/ prev指向實際的「項目節點」。

當列表爲空時，head.next & head.prev都會指向自身。

對於循環的dbl-linked列表，邏輯更簡單，而不是尾指針變體，允許'head'和'tail'在空時爲空;這需要在任何修改操作中都可能更新「頭」和「尾」指針，這使得邏輯更加複雜。

命名在這裏有點不清楚：我用head來引用'list node'，但它可以被稱爲'list'或'node'。

head.next -> first -> second -> ... 
head.last -> last -> second-last -> ... 

如果列表爲空：

head.next -> head 
head.last -> head 

如果列表中的一個項目：

head.next -> item -> head 
head.last -> item -> head