複雜度O（1）的循環雙鏈表如何以及爲什麼串聯？

它作爲一個事實在某些標準書籍中給出了循環雙向鏈表的連接具有複雜性O（1），並且不是單一或雙向鏈表的情況。有人可以澄清爲什麼以及如何這是可能的...複雜度O（1）的循環雙鏈表如何以及爲什麼串聯？

2016-01-07 kanishka

那麼，請嘗試爲您提到的三種情況編寫連鎖代碼，並計算您的實現中每個實例的漸近代價。你有什麼結果？它們是否與書中的索賠相匹配？ –

在一個圓形雙向鏈表中，你有head->prev指向最後一個元素。所以，你所要做的就是使用該節點的地址來執行連接，所以O（1）。然而，在一個簡單的單向或雙向鏈表中，你必須遍歷這個列表才能得到最後一個元素，並且對我來說執行看起來像O（n）的連接。

2016-01-07 03:37:42 venkatKA

哦，是的.. thanq ..我忽略了雙重的詞..所以有一種印象，即從頭部到最後一個元素，需要遍歷整個循環鏈表。現在它對你的解釋有意義。。謝謝：） – kanishka

回答