單鏈表和時間複雜性

Question

我試圖寫我自己的（儘可能接近標準）單鏈表實現。不過，我想知道人們對這樣的列表期望的時間複雜程度？

特別是對於插入我想知道我應該如何實現它。我讀過互聯網上的一些地方，有人說插入是O（1），而另外一些人說O（n） - 都同意雙鏈表是O（1）。但是我認爲O（1）也適用於單鏈表？

只要你知道前面的節點，你就讓前面的節點指向新的新節點，新節點將指向前面的節點最初指向的地方。

這就是說，這讓我想知道人們如何期待insert的行爲？通常它插入給定迭代器之前的元素。但是，對於單鏈表來說，很難做到這一點（必須經過O(n)才能獲得前面的元素&，然後使用上面的方法）。在這樣的列表中將insert放置在當前迭代器的後面是否很常見？或者 - 可能更好 - 是否有另一個共同的功能呢？

Answer 1

插入的複雜性取決於你需要做什麼。如果你知道前面的節點（實際上，只需要一個合適的句柄來改變前面節點的「下一個指針」），那麼複雜度就是O(1)。如果您需要查找插入位置，則複雜度爲O(n)。

關於期望，我期望insert()的行爲與雙向鏈表相同，但我也意識到你不能實現這一點：你需要有不同的時間複雜性（找到前任節點）或不同的迭代器失效語義（即，其他節點的迭代器失效）。我認爲C++ 2011 std::forward_list類模板用於不同的界面，但保留了迭代器有效性的保證。

簡要解釋爲什麼可以影響迭代器有效性：迭代器不必知道當前節點。例如，它可以指向前任的next指針。當取消引用迭代器時，它將首先取消引用其指向next指針的指針，然後取消引用該指針以獲取實際節點。作爲回報，可以在迭代器前面插入，因爲迭代器知道哪個next指針要更新。不幸的是，這意味着迭代器可能失效，因爲它們指向的指針可能已經改變，並且它們會引用不同的節點（當刪除節點時，雖然引用的節點仍然存在，但迭代器可能已經完全無效）。