algorithm - 数据结构名称 : combination array/linked list

Question

我提出了一种数据结构，它结合了链表的一些优点和固定大小数组的一些优点。这对我来说似乎很明显，所以我希望有人已经想到并命名它。有谁知道这叫什么:

取一个固定大小的小数组。如果您要放入数组的元素数量大于数组的大小，请添加一个新数组以及您喜欢的新旧数组之间的任何指针。

因此你有:

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 S-Z 的回答非常完整且经过深入研究，我想为他们提供赏金。显然 Stack Overflow 不允许我在提供赏金后立即接受答案，所以我不得不等待(诚然，我在某种程度上滥用了意图赏金系统，尽管它是以奖励某人的名义回答)。当然，如果有人确实设法提供更好的答案，给他们更多的权力，他们肯定可以获得赏金!

编辑重命名:我对你会怎么调用它不感兴趣，除非你那样调用它，因为这就是该主题的权威人士所说的它。如果这是你刚刚想出的名字，我不感兴趣。我想要的是一个我可以在教科书和 Google 上查找的名字。 (另外，这里有一个提示:Antal 的答案正是我要找的。如果你的答案不是“展开的链表”而没有非常充分的理由，那它就是完全错误的。)

Answer 1

它叫做 unrolled linked list .似乎有几个优势，一个是速度，一个是空间。首先，如果每个节点中的元素数量大小合适(例如，最多一个缓存行的大小)，您可以从改进的内存局部性中获得明显更好的缓存性能。其次，由于您有 O(n/m) 个链接，其中 n 是展开链表中的元素数， m 是您可以在任何节点中存储的元素数，您还可以节省可观的空间量，如果每个元素都很小，这一点尤其明显。在构建展开的链表时，显然实现会尝试在节点中留出空间；当您尝试插入一个完整节点时，您会将一半元素移出。因此，至多一个节点将少于半满。根据我能找到的(我自己没有做过任何分析)，如果你随机插入东西，节点实际上往往是四分之三满，如果操作往往在列表的末尾，甚至会更满。

正如其他所有人(包括维基百科)所说，您可能需要查看 skip lists .跳跃列表是一种漂亮的概率数据结构，用于存储插入、删除和查找的预期运行时间为 O(log n) 的有序数据。它由链表的“塔”实现，每层越高，元素越少。在底部，有一个普通的链表，包含所有元素。在每个连续的层中，元素的数量会减少 p(通常为 1/2 或 1/4)。它的构建方式如下。每次将一个元素添加到列表中时，都会将其插入底行的适当位置(这使用“查找”操作，也可以快速完成)。然后，以 p 的概率，它被插入到它“上方”的链表中的适当位置，如果需要则创建该链表；如果它被放置在更高的列表中，那么它将再次以p的概率出现在上面。要查询此数据结构中的某些内容，您始终会检查顶部 channel ，看看是否可以找到它。如果你看到的元素太大，你会掉到下一个最低的车道并重新开始寻找。这有点像二分查找。维基百科对其进行了很好的解释，并附有漂亮的图表。当然，内存使用情况会更糟，并且您不会获得改进的缓存性能，但通常会更快。

引用资料

• “展开链表”，http://en.wikipedia.org/wiki/Unrolled_linked_list
• “展开链表”，Link
• “跳过列表”，http://en.wikipedia.org/wiki/Skip_list
• 我的算法课上的跳过列表讲座。