鏈接列表的相關Big O符號是什麼？

在鏈表中插入和查找元素應該有一個很大的值。

據哥倫比亞筆記，爲一個單鏈表，它是：

單鏈表（SSL）的SLL是一系列節點。每個節點包含數據和對下一個節點的引用。 SSL可以增長，並根據需要收縮。將一個元素添加到列表中的是O（1）。在列表中查找元素是O（n）。

數據結構沒有計算複雜性; *數據結構上的操作*具有計算複雜性。你在問什麼操作？ – Sneftel

你究竟想知道什麼？ – akm

您是否有理由懷疑您發現（和引用）的內容？或者你有什麼問題建立在你發現的東西上？ –

insert()需要O(1)，你可以在固定時間內的元素添加到鏈表的head

find()需要O(n)時間，在最壞的情況下，你需要遍歷列表，直到你到達tail

這些適用於單鏈表和雙鏈表

2014-03-02 22:38:04 arunmoezhi

單倍和雙倍的常量會有變化，並且不會影響大O. – arunmoezhi

回答