完美列表结构？

Question

从理论上讲,数据结构是否可行

O(1)访问,插入,删除次数

和动态长度？

我猜一个尚未发明或我们完全放弃使用数组和链表(单独),而是选择使用其中之一.

有没有证据证明这是不可能发生的,因此访问时间,插入时间和删除时间(如能量守恒)之间的某种关系表明,如果其中一个时间变得不变,另一个时间必须是线性的或者其他东西.

Answer 1

让我们枚举您的需求，而不是首先提及单个可能的数据结构。

基本上，您想要恒定的操作时间......

• 使用权
  • 如果您确切地知道您正在寻找的实体在哪里，那么这很容易完成。哈希值或索引位置可用于唯一标识实体并提供恒定的访问时间。 这种方法的主要缺点是您无法将真正相同的实体放入相同的数据结构中。
    
    
• 插入
  • 如果您可以在列表的最后插入而不需要遍历它，那么您就可以实现恒定的访问时间。这种方法的主要缺点是您必须始终有一个指向列表末尾的引用，该引用必须在更新时进行修改（理论上，这也应该是一个恒定时间操作）。如果您决定对每个值进行散列以便稍后快速访问，那么计算散列并将其添加到某些支持结构以进行快速索引都会产生成本。
    
    
• 删除时间
  • 这里的主要原则是运动部件不能太多；我正在从一个固定的、明确定义的位置删除。像Stack、Queue、 或 这样的东西在很大程度上Deque可以提供这一点，因为它们只删除一个元素，无论是按 LIFO 还是 FIFO 顺序。 这种方法的主要缺点是您无法扫描集合以查找其中的任何元素，因为这将花费 O(n) 时间。如果您打算使用散列，您可能可以在O(1) 时间内完成，但代价是 O(n) 存储空间的倍数（对于散列）。
    
    
• 动态长度
  • 如果您要链接引用，那么这应该不是什么大问题；LinkedList已经有一个内部Node类了。 这种方法的主要缺点是你的记忆不是无限的。如果你采用哈希方法，那么你必须哈希的东西越多，冲突的概率就越高（这确实会让你脱离 O(1) 时间，并让你更多地陷入摊销的 O(1 ） 时间）。

因此，实际上没有任何单一、完美的数据结构可以为您提供绝对恒定的运行时性能和动态长度。我也不确定通过为这样的事情编写证明可以提供任何价值，因为数据结构的一般用途是利用其积极因素并接受其消极因素（在散列集合的情况下：喜欢访问时间，没有重复是一个 ouchie）。

不过，如果您愿意承受一些摊销的性能，那么一套可能是您的最佳选择。