我提出了一种数据结构，该结构结合了链表的某些优点和固定大小的数组的某些优点。对我来说，这似乎很明显，因此我希望有人想到它并对其进行命名。有谁知道这叫什么：
取一个小的固定大小的数组。如果要放入数组中的元素数量大于数组的大小，请添加新数组以及在新旧之间添加的任意指针。
因此，您有：
Static array ————————————————————————— |1|2|3|4|5|6|7|8|9|a|b|c| ————————————————————————— Linked list ———— ———— ———— ———— ———— |1|*->|2|*->|3|*->|4|*->|5|*->NULL ———— ———— ———— ———— ———— My thing: ———————————— ———————————— |1|2|3|4|5|*->|6|7|8|9|a|*->NULL ———————————— ————————————
编辑 ：供参考，此算法提供的最坏情况下最差情况的添加/删除性能，但没有更好的平均情况。我的方案的最大优点是提高了读取操作的缓存性能。
编辑赏金 ：Antal SZ的答案是如此完整和深入研究，以至于我想为其提供赏金。显然，提供奖金后，Stack Overflow并不能让我接受答案，因此我必须等待（诚然，我在滥用意向性奖金系统，尽管它是以奖励某人优秀奖的名义回答）。当然，如果某人 确实 设法提供更好的答案，则可以给他们更多的力量，而他们肯定可以得到赏金！
编辑重命名 ：我对 您的 称呼不感兴趣，除非您称呼它，因为这是该主题上的权威人士所称呼的。如果这是您刚想出的名字，我不感兴趣。我想要的是一个可以在教科书和Google中查找的名称。（另外，这里有一个技巧：安塔尔的答案是什么，我一直在寻找如果你的答案是不是“展开链接列表”没有。 很 充分的理由，这是完全错误的。）
这称为 展开的链表 。似乎有两个优点，一个是速度，另一个是空间。首先，如果每个节点中元素的数量具有适当的大小（ 例如 ，至多一个缓存行的大小），则可以通过改进的内存局部性显着提高缓存性能。其次，由于您具有O（ n / m ）个链接，其中 n 是展开的链接列表中的元素数，而 m是 是您可以在任何节点中存储的元素数量，还可以节省大量空间，如果每个元素都很小，这一点尤其明显。当构造展开的链表时，显然实现会尝试在节点中留出空间；当您尝试插入一个完整的节点时，会将一半的元素移出。因此，至多一个节点将少于一半的充满。根据我的发现（我自己还没有做任何分析），如果您随机插入内容，则节点实际上实际上大约占满了四分之三，如果操作倾向于位于列表的末尾，则节点甚至可能变得更满。
正如其他所有人（包括Wikipedia）所说的那样，您可能想查看跳过列表。跳过列表是一种精美的概率数据结构，用于存储有序数据，其预期运行时间为O（log n ），用于插入，删除和查找。它是由链接列表的“塔”实现的，每层越高，元素越少。在底部，有一个普通的链表，其中包含所有元素。在每个连续的层上，元素数量减少了 p 倍（通常为1/2或1/4）。它的构建方式如下。每次将元素添加到列表时，都会将其插入到底部行中的适当位置（这使用“查找”操作，也可以使其快速进行）。然后，概率为 p ，将其插入到链接列表“上方”的适当位置，并在需要时创建该列表；如果将其放在较高的列表中，则它将 再次 以概率 p 出现在上方。要查询此数据结构中的某些内容，请始终检查顶部通道，看看是否可以找到它。如果看到的元素太大，则下降到下一个最低车道并重新开始寻找。这有点像二进制搜索。维基百科很好地解释了它，并带有漂亮的图表。当然，内存使用情况将变得更糟，并且您将不会具有改进的缓存性能，但是通常它将更快。
