雙向鏈表中節點刪除的時間複雜度

爲什麼雙向鏈表（O（1））中節點刪除的時間複雜度比單向鏈表（O（n））中的節點刪除快？雙向鏈表中節點刪除的時間複雜度

作業？編寫從單個鏈接列表中刪除節點的代碼，然後就會很明顯。 – 2009-12-13 06:53:06

我認爲在標題中不應該有像dll這樣的縮寫，但我想不出更好的縮寫。 – 2009-12-13 07:08:40

它與修復正在刪除的節點之前的節點中的下一個指針的複雜性有關。

2009-12-13 06:53:51

因爲你不能向後看...

2009-12-15 03:15:29 Paul

問題假定節點被刪除是已知的，一個指向該節點是可用的。

爲了刪除節點並將上一個節點和下一個節點連接在一起，您需要知道它們的指針。在雙向鏈表中，兩個指針在要刪除的節點中可用。在這種情況下時間複雜度是恆定的，即O（1）。

而在單鏈表中，指向前一個節點的指針是未知的，只能通過從頭開始遍歷列表直到它到達具有指向要刪除的節點的下一個節點指針的節點。這種情況下的時間複雜度是O（n）。

如果僅通過值知道要刪除的節點，則必須搜索該列表，並且在單向鏈接和雙向鏈接列表中時間複雜度變爲O（n）。

2013-05-02 06:17:14 Raj

這對於從單個鏈接列表中移除需要O（n）複雜性的節點而言是不正確的 - 請參閱下面的答案。有一個技巧，您可以從被刪除的節點複製下一個節點的值，然後跳過該節點以指向節點，從而消除了遍歷列表的任何需要。 – Ben 2017-10-07 07:17:42

在已知位置插入和刪除是O（1）。然而，找到那個位置是O（n），除非它是列表的頭部或尾部。

當我們談論插入和刪除複雜性時，我們通常假設我們已經知道將會發生什麼。

2014-11-17 07:51:10 Tony

除非要刪除的元素是頭（或第一個）節點，否則我們需要遍歷要刪除的節點之前的節點。因此，在最壞的情況下，即當我們需要刪除最後一個節點時，指針必須一路走到第二個節點，從而遍歷（n-1）個位置，這給我們的時間複雜度爲O（n）。

2016-08-05 06:40:16

實際上單鏈表中的刪除也可以在O（1）中實現。

給定一個單向鏈表具有以下狀態：

SinglyLinkedList: 
    Node 1 -> Node 2 
    Node 2 -> Node 3 
    Node 3 -> None 

    Head = Node 3

我們可以以這樣的方式實現delete Note 2：

Node 2 Value <- Node 3 Value 
Node 2 -> None

在這裏，我們與它的未來價值取代Node 2值節點（Node 3），並將其下一個值指針設置爲Node 3（None）的下一個值指針，跳過現在有效的「重複」Node 3。因此不需要遍歷。

2017-10-07 01:21:32 Ben

回答