是否有可能创建一个具有O(1)插入、删除和0(1)最小访问权限的LinkedList实现

Question

假设这个问题具有无限的空间复杂性。我相信我看到了这个解决方案，但我已经完全忘记了。如果我没有记错的话，一个解决方案涉及一个堆栈来跟踪最小值，另一个涉及向LinkedList节点添加数据值。

最小堆实现将导致日志(n(的插入和删除，但有没有办法使其为O(1(？

如果可能的话，一个能够做到这一点的数据结构的实现是什么。

Answer 1

如果您有这样的数据结构，您可以使用O(n(比较对n个项目进行排序：将它们添加到列表中，然后重复找到最小值并将其删除。

因此，这个数据结构通常不可能存在这些性能边界。