使用單向鏈接循環列表實現字典

我正在解決一個問題，在這個問題中，我必須實現字典操作插入，刪除和使用單鏈接，循環列表搜索。你的程序的運行時間是什麼？
1）插入：它可以在O完成（1）
2）刪除：它可以在O完成（1）
3）搜索：我不知道這一點。 O（length_of_linked_list）是最糟糕的情況。
使用單向鏈接循環列表實現字典

可以在更快的運行時間內完成搜索嗎？

來源

2014-07-01 sp1rs

我應該假設您的鏈接列表已排序嗎？ – Jerky

@AyushJain如果你按照排序的順序假設鏈接列表不會在O（1）中實現插入。 – sp1rs

是的，我會這麼說。那麼我猜如果它沒有排序，搜索不能在O（log（n））時間完成。它應該是O（n） – Jerky

插入和搜索，都不能用O（1）完成（除非你使用散列）。主要有3種可能性：

搜索O（nlogn）和插入O（1）
搜索O（logn）時間和插入O（logn）時間
搜索和插入均爲O（1）

例如，當您在鏈表的最後位置插入並在排序後進行迭代搜索（快速排序需要平均nlogn）時才使用第一個例子。當您需要使用比插入用法更少的搜索用法維護數據庫時，這會很有幫助。第二個有用的例子是，當您在k-ary搜索方法的幫助下對插入和搜索進行排序時，需要花費時間。這很有用，例如在電話簿中，搜索次數多於插入次數。現在一天，散列技術更多用於處理這些問題（O（1））。因此，使用散列和索引，我們可以實現O（1）時間搜索和插入的功能。刪除時間與搜索相同，因爲您可以在找到元素後立即刪除0（再加上幾個指針移位，而不是大問題）。

來源

2014-07-01 12:10:42

帶有所有這些可能性（不包括散列），最好有O（1）插入，O（1）刪除和O（N）搜索。但thx爲您的幫助兄弟。我研究k-ary搜索方法。 – sp1rs

不客氣我的朋友:)我想澄清的一件事是O（1）中的刪除無法使用鏈接列表來實現。假設你必須刪除鏈表中的一個元素，你必須首先搜索它，不管你的列表是否被排序。這肯定會花O（有些時候！= 1）。無論如何，這取決於您的選擇以及您希望提供哪種方法的功能。 –

我們可以在O（1）時間內刪除..看看這篇文章.. http：// stackoverflow。com/questions/793950/algorithm-for-deletion-one-one-in-an-one-linked-list-with-o1-complexity – sp1rs

使用單向鏈接循環列表實現字典

回答

相關問題