一种数据结构，其支撑O（1）随机接入和最坏情况下的O（1）附加？一种数据结构，其支撑O（1）随机接入

我认识到，使用数组来存储它的元素（如一个可调整大小的索引的集合List<T>在.NET或ArrayList在Java中）已经摊销O（1）插入时间在集合的末尾。但后来总是有在其中收集刚刚达到其容量和下插入关键时刻一个讨厌的插入需要内部数组中的所有元素的完整副本到一个新的（大概是两倍大）。

一个常见的错误（在我看来）是去同一个链表来“解决”这个问题; 但相信分配用于每一个元素中的节点的开销可能是相当浪费的，并且实际上将矮保证的O的益处（1）插入在罕见的情况下，阵列插入是昂贵-时，实际上，每隔阵列插入是显著便宜（更快）。

我想可能是有意义的是由阵列的链表，其中每一次当前的“头”阵列达到其容量，新阵列的两倍被添加到链表的混合方法。然后没有副本将是必要的，因为链表仍然有原来的数组。本质上，这似乎是类似的（对我）的List<T>或ArrayList方法，但无论你以前就已经发生复制内部数组的所有元素，成本在这里你只能招致分配一个新的阵列的成本加上单个节点插入。

当然，如果他们被期望的，这将复杂化的其他特征（例如，插入/移除到从收集的中间/）; 但正如我在标题所表达的，我真的只是寻找一个只添加 （和迭代）集合。

是否有任何数据结构，那里非常适合这个目的是什么？或者，你能想到一个自己？

Answer 1:

有一个美丽的结构，称为具有最坏情况下的可延伸的阵列O（1）的插入和O（n）的存储器开销（也就是，它的渐近媲美动态数组，但是具有O（1）的最坏情况的插入）。关键是要采取矢量使用方法 - 加倍和复制 - 而是要复制懒惰。例如，假设你有这样一个四个元素的数组：

[1] [2] [3] [4]

如果你想添加一个新的号码，说5，你就开始通过分配的数组的两倍：

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

接下来，您将5到新的数组：

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [5] [ ] [ ] [ ]

最后，从旧的阵列到新拉下4：

[1] [2] [3] [ ]
[ ] [ ] [ ] [4] [5] [ ] [ ] [ ]

从现在开始，你插入任何时候，元素添加到新的阵列和从旧阵列拉下一个多元素。例如，添加6后，我们会得到

[1] [2] [ ] [ ]
[ ] [ ] [3] [4] [5] [6] [ ] [ ]

将两个值后，我们会在这里结束：

[ ] [ ] [ ] [ ]
[1] [2] [3] [4] [5] [6] [7] [8]

如果我们现在需要添加更多的元件，我们丢弃现在空的旧阵列和分配数组两倍大电流阵列（能够保持16个元素）：

[1] [2] [3] [4] [5] [6] [7] [8]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

并重复此过程。贴现的存储器分配的成本（通常在所述阵列的大小次线性），这样做在每次插入最O（1）的工作。

查找仍然是O（1），因为你只是决定要看看这两个阵列中，而在中间插入为O（N），因为洗牌。

如果你很好奇，我已经在我的个人网站的Java实现这种结构。我不知道你会多么有用找到它，但你比欢迎更多的尝试。

希望这可以帮助！

编辑：如果你想投资一点时间阅读过的研究论文，并试图实现一个相当复杂的数据结构，你可以在O（√N）空间开销相同的结果（最坏情况O（1）追加）（这是可证明的最佳，的方式）使用本文中的想法。我从来没有抽时间去实际执行这一点，但它肯定是很好，值得读内存是否超稀缺资源。有趣的是，它使用此之上建设作为一个子程序！

Answer 2:

当我需要一个这样的容器，我用我的实现中所描述的结构“调整大小阵列中的最佳时间和空间”

Answer 3:

好。你所描述的是几乎什么的std :: deque的是C ++标准库。不同的是，一个阵列（通常）被用于保持指针的子阵列，而不是使用一个链表。

Answer 4:

一个想法是创建一些元素，如列表：

struct item
{
    int data[NUM_ITEMS];
    item *next;
}

在这种情况下插入会采取O(1)如果你达到了极限只需要创建一个新块并将它添加到你的列表的末尾

文章来源: A data structure supporting O(1) random access and worst-case O(1) append?