快速搜索双向链表

Question

我目前有一个简单的数据库程序，它从文本文件中读取关键字并将它们存储在双向链表中（如果需要，以后再读取值）。目前，我在名单上进行了顺序搜索，但是这显然很慢。我希望有另一种方式去做。我正在阅读二叉树（特别是红黑树），但我不太了解他们，并希望我可以从stackoverflow hivemind闪光的东西:)我想我的问题是，什么是最快的方式在双向链表中进行搜索？

编辑：忘了说，列表排序。不知道这是否会改变任何事情。另外，我只读密钥的原因是最大长度是1024 * 32字节，我觉得它太大了。请注意，这是用于分配的，因此“典型使用场景”不适用。教授们可能会对这件事情进行压力测试，我不希望成为那些庞大的块。

Answer 1

有一种叫做“skip list”的东西可以使用。

它是一组有序列表。每个列表跳过更多列表项。这可以让你做一个二进制搜索的形式。但是，维护列表更加困难。

Answer 2

在未排序的双向链表中执行搜索的最快方法是一次一个元素。

如果您尝试更快地搜索，请不要使用链接列表。例如，使用二叉树的想法一定会更快，但正如Matthew Flaschen在评论中所说的那样，它与现在使用的完全不同。

Answer 3

鉴于您的双向链表已排序，并且您有要搜索的项目列表，我建议您查看构建自平衡二叉搜索树的问题。树的构建可能需要一些时间，但是如果您有很长的搜索项目列表，它将被摊销。