arrays - 双端动态数组数据结构的缺点是什么？

Question

动态数组是一种众所周知的数据结构:例如，我们为 8 个元素分配一个数组，并在插入到数组末尾时使用这些槽。当我们没有槽时，我们分配一个大小为 16 的数组，依此类推。我们得到 O(1) 插入到最后的摊销复杂性。许多语言及其标准库都实现了动态数组。

这里的一个限制是插入到数组的开头是 O(n) 因为开头没有空闲插槽。但是，为什么不在数组的开头和结尾都有一些空闲槽呢？它使得在两端插入 O(1) 并且如果我们用完任何一侧的空闲插槽，我们将像往常一样分配一个更大的数组。

它的内存效率将低于单端动态数组(因为我们需要在两侧维护空闲槽)，但在两侧插入 O(1) 并不是一个糟糕的折衷.或者是吗？还有其他缺点吗？我还没有在任何地方看到这种数据结构的实现，它的致命缺陷是什么？

Answer 1

这是我个人的看法。就像你说的，动态数组非常简单和常见，但它们在开始时肯定不会很好地执行插入操作。像你建议的那样，增加两端数组的大小，是有可能的，也许在某些情况下它工作得很好，但算法并不像看起来那么清晰。增长内部阵列时，您是始终在两端添加松弛还是仅在已耗尽的一侧添加松弛？或者您是否尝试保持两个边距平衡？这可能会以一种可能不容易预测的方式极大地影响结构的空间效率。

另一方面，如果您需要在两端插入，您可能可以使用动态循环数组。循环数组的许多实现都有固定的最大大小，但没有什么能真正阻止您将其动态化。您甚至可以在某些动态数组实现之上实现它。循环数组引入了添加基本索引(使用双端 slack 无论如何都需要)和计算模数的小开销，但它们具有可预测且节省空间的行为。