單鏈表中的時間複雜度

我正在學習數據結構：單鏈表。單鏈表中的時間複雜度

該網站說單鏈表的插入和刪除時間複雜度爲O(1)。我錯過了什麼嗎？

我做這在C++，我只有一個root pointer。如果我想在最後插入，那麼我必須一路走到後面，這意味着O(n)。

看起來像一個副本http://stackoverflow.com/questions/14048143/why-is-deleting-in-a-single-linked-list-o1 –

如果你按照鏈接該實現示例中，該界面與您描述的情況不同。 –

對此的解釋是，鏈接表中的大O符號指的是函數實現本身，不包括列表遍歷以在列表中找到前一個參考節點。

如果按照鏈接到Singly-LinkedList implementation的維基百科文章變得更加清晰：

function insertAfter(Node node, Node newNode) 
function removeAfter(Node node)

上述函數簽名已經採取了前代節點作爲參數（同爲其他變體隱）。

查找前驅是一個不同的操作，可能是O（n）或其他時間複雜度。

2016-11-05 21:08:52

你錯過了接口在兩個地方：

的std ::目錄::插入（）/ STD：列表::擦除（）需要一個迭代器在哪裏插入或刪除元素。這意味着你沒有搜索，只能在列表中的元素中改變兩個指針，這是不變的複雜性。
插入列表的末尾可以通過push_back完成。該標準要求這也是O（1）。這意味着，如果你有一個std :: list，它將存儲第一個和最後一個元素。

編輯：對不起，你遇到std :: forward_list。即使名稱是insert_after和erase_after，點1也適用於此。點2不是，你必須迭代到列表的末尾。

2016-11-05 21:17:02 user6556709

我在C++中這樣做，我只有一個根指針。如果我想在最後插入，那麼我必須一路走到後面，這意味着O（n）。

這兩個操作，首先搜索O（n）的的列表中指定位置，然後插入O（1）元素到列表中。

在單鏈表，插入的操作包括：

兩者都不變列表大小。

另一方面，以堆結構爲例。插入每個元素需要O（log（n））操作才能保留其結構。樹結構具有類似的機制，將在插入時運行並取決於當前的樹大小。

2016-11-05 21:32:32 thorhunter

回答