每个人都知道(或者必须知道)，设计一个既支持中间0(1)插入又支持0(1)查找的列表数据结构是不可能的。
例如，链表支持O(1)个插入操作，但查找操作支持O(N)个;数组支持O(1)个查找操作，但插入操作支持O(N)个插入操作(可能是平摊O(1)个开始插入、结束插入或同时插入)。
然而，假设你愿意用O(1)插入来交换:
- 平摊O(1)插入
- O (log (N))插入
那么在每种情况下查找的理论边界是什么?您了解现有的数据结构吗?内存复杂度呢?
基于树的数据结构，如rope或finger tree，通常可以在任意位置提供对数插入时间。这种权衡是在访问时间上，除了在特殊情况下，比如手指树的末端，访问时间往往也是对数的。
动态数组可以在末端提供平摊的常量插入，但在中间插入需要复制数组的一部分，并且时间为O(N)，如您所述。
有可能实现一个支持平摊常数中间插入的数据结构。如果在任意一端添加，则视为动态数组。如果插入到中间，则保留旧数组，并在其"上面"添加一个包含列表新"中间"的新数组，使用旧数组存储位于中间左侧或右侧的数据。在第一次中间插入之后，访问时间将是对数的，并且跟踪哪个层中有什么数据将很快变得复杂。
这可能是维基百科文章中提到的"分层"动态数组，我还没有进一步研究。
我怀疑没有人真正使用这样的数据结构的原因是，在中间插入很少是你最需要的情况，而对数插入(使用树)对于大多数现实世界的情况来说已经足够好了。
这些仍然是开放的问题，但我所知道的最好的界限是来自Arne Andersson的不带乘法的次对数搜索，它具有O(sqrt(lg(n)))的插入，删除和查找。然而，这是以2^k的额外空间为代价的，其中k是存储在数据结构中的整数的位数，因此我们仍然使用平衡二叉树而不是Andersson的数据结构。数据结构的一种变体允许进行O(1)次查找，但随后额外的空间增加到n2^k，其中n是数据结构中元素的数量。随机变体不使用任何额外的空间，但随后sqrt(lg(n))插入/删除/查找时间成为平均空间时间，而不是最坏情况时间。