用单链循环列表实现字典

Question

我正在解决一个问题，其中我必须执行字典操作插入，删除和搜索使用单一链接，循环列表。你的程序的运行时间是多少？

( 1)插入:可以在O(1)中完成

2)删除:可以在O(1)中完成。

3)搜索:我不确定。O(length_of_linked_list)是最坏的情况。

搜索能在更快的时间内完成吗?？

Answer 1

插入和搜索，都不能用O(1)来完成(除非在使用散列时)。主要有三种可能性：

1. 搜索O(nlogn)并插入O(1)
2. 搜索O(logn)并插入O(logn)
3. 搜索并插入O(1)

例如，当您在链接列表的最后位置插入并在排序完成后(快速排序需要平均nlogn)使用迭代进行搜索时，使用第一种方法。当您需要使用比插入使用更少的搜索使用来维护数据库时，这是很有帮助的。第二种方法是有用的，例如，当您使用k-ary搜索方法对插入和搜索进行排序时，需要花费很长的时间。这是有帮助的，例如，在电话簿中，搜索多于插入。现在，哈希技术更多地用于处理此类问题(O(1))。因此，通过散列和索引，我们可以实现O(1)时间搜索和插入的功能。删除时间和搜索是一样的，因为在找到元素之后，您可以在0时间内删除(再加几个指针移动，没什么大不了的)。