代码之家 › 专栏 › 技术社区 › me_and

数据结构名称:组合数组/链表

data-structures language-agnostic algorithm

me_and · 技术社区 · 14 年前

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

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

因此你有:

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
ââââââââââââ  ââââââââââââ

编辑 :作为参考,此算法提供了相当差的最坏情况添加/删除性能,而平均情况则不太好。在我的场景中,最大的优势是提高了读操作的缓存性能。

编辑重新赏金 :安塔尔S-Z的回答是如此完整和深入研究,我想为他们提供一笔赏金。显然,一旦我提供了一个赏金,堆栈溢出不会让我接受一个答案,所以我必须等待(诚然,我有点滥用意向赏金系统,尽管这是为了奖励一个优秀答案的人)。当然,如果有人做设法给他们提供一个更好的答案,更多的权力,他们当然可以得到赏金!

编辑重名 我对什么不感兴趣你会叫它吧,除非你这么叫它,因为这正是当局所说的。如果这是你刚想到的名字,我不感兴趣。我想要的是一个名字,我可以在教科书和谷歌中找到。(还有,这里有一个提示:安塔尔的答案是我正在寻找的。如果你的答案不是“展开链接列表”,没有非常很好的理由,这显然是错误的。)

6 回复 | 直到 7 年前

Antal Spector-Zabusky 14 年前

它叫做 unrolled linked list . 似乎有两个优点,一个在速度上,一个在空间上。首先,如果每个节点中的元素数量大小合适( 例如最多只有一条缓存线的大小),您可以从改进的内存位置获得明显更好的缓存性能。第二,既然你有O( n / 米链接,在哪里 n 是展开的链接列表中的元素数,并且米是可以存储在任何节点中的元素数,还可以节省可观的空间量,如果每个元素都很小,这一点尤其明显。当构建展开的链接列表时,显然实现会尝试在节点中留下空间;当您尝试插入一个完整的节点时,您会将一半元素移出。因此,最多一个节点将小于半满。根据我的发现(我自己还没有做过任何分析),如果你随机插入东西,节点实际上会满四分之三,如果操作在列表的末尾,甚至会满四分之三。

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

工具书类

_展开的链接列表__, http://en.wikipedia.org/wiki/Unrolled_linked_list
_156;展开的链接列表_, http://blogs.msdn.com/b/devdev/archive/2005/08/22/454887.aspx
_156;跳过列表_157;, http://en.wikipedia.org/wiki/Skip_list
我的算法课上的“跳过列表”课。

Doug Currie 14 年前

CDR coding (如果你年龄足够大,能记住Lisp机器)。

也看到 ropes 这是对字符串的列表/数组思想的概括。

fubra 14 年前

我会把这称为一份清单。

jer 14 年前

虽然我不知道您的任务,但我强烈建议您查看跳过列表。

至于名字,我想一份木桶清单可能是最合适的

eljenso 14 年前

你可以称之为 LinkedArrays .

另外,我想看看 removeIndex 操作。

rkitauchi 14 年前

这个数据结构在插入和删除方面有什么优势? 前任: 如果你想在3到4之间添加一个元素怎么办?还得换班,需要O(N) 你如何找到适合元素的桶?

我同意杰尔的看法,你得看看 跳跃表 . 它具有链表和数组的优点。 大多数操作都是在O(log n)中完成的。