不對稱鏈表需要什麼

Question

我正在研究數據結構。我所遇到Asymmetric linked list其中規定，它是一種特殊類型的雙鏈表，其中

1. next link points to next node address 
2. prev link points to current node address itself 

但我不知道，

1. what are the advantages we get by designing such linked list? 
2. what kind of applications this would be suitable for? 

誰能好心解釋更多Asymmetric linked list。我google搜索，但我找不到相關的答案。謝謝。

來源：http://en.wikipedia.org/wiki/Doubly_linked_list#Asymmetric_doubly-linked_list

Answer 1

我同意維基頁面是誤導性的。這裏是LL和ALL之間的區別：

打開鏈接列表：

node.next = nextNode 
node.prev = prevNode 

不對稱鏈接列表：

node.next = nextNode 
node.prev = prevNode.next 

注VS prevNode.next區別prevNode。

雖然指向節點內的指針仍然保留向後遍歷列表的能力（您可以通過從prevNode.next中減去prevNode地址），它可以簡化列表中的插入和刪除操作，特別是在開始元素上。

Answer 2

鑑於從雙鏈表節點指針，我們可以遍歷由「下一頁」的所有節點和「下一步」，而單鏈表不能這樣做，如果指針提供沒; t指向第一個節點。

例如，從鏈表中刪除節點。使用單鏈表時，必須從頭遍歷列表以查找特定節點，並且還需要針對特定​​節點記錄prev節點，這會導致時間複雜度爲O（n）。但是，使用雙鏈表時，可以用固定時間執行與特定節點的刪除。

簡而言之，給定一個特定的節點，對於單鏈表，如果我們需要使用它的prev節點信息，那麼從頭開始的O（n）是不可避免的，而雙線列表不會。

順便說一下，在STL和LinkedList中的Java列表是用雙鏈表實現的。