使用单链循环表实现字典

Question

我正在解决一个问题，我必须实现字典操作插入，删除和搜索使用单链，循环列表。你的程序的运行时间是多少?
1)插入:0 (1)
2)删除:0 (1)
3)搜索:我不确定。O(length_of_linked_list)是最坏的情况

搜索可以在更快的运行时间内完成吗?

Answer 1

插入和搜索，都不能用0(1)完成(除非您使用散列)。主要有三种可能:

1. 查找O(nlogn)并插入O(1)
2. 查找O(logn)并插入O(logn)
3. 查找并插入O(1)

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