快速搜索双向链表

Question

我目前有一个简单的数据库程序，从文本文件中读取键并将它们存储在双向链表中（如果需要，稍后再读取值）。目前，我在列表上进行顺序搜索，但这显然相当慢。我希望有另一种方法来解决这个问题。我正在阅读关于二叉树（特别是红黑树）的内容，但我对它们了解不多，希望能从stackoverflow社区中获得一些信息。我的问题是，双向链表中最快的搜索方式是什么？

编辑：忘记说列表已排序。不知道这是否会改变任何东西。此外，我只读取键的原因是最大值长度为1024 * 32字节，我觉得太大了。请注意，这是为了完成任务，因此“典型使用情况”不适用。教授们可能会对这个东西进行压力测试，而我不想分配那么大的内存块。

- David Watson

---

二叉树和链表是不同的数据结构（链表是树的一种简化形式），因此你需要考虑是否愿意更改结构。 - Matthew Flaschen

注意读取文本文件两次可能会带来性能成本；最好在读取键时同时读取和保存值。文件速度low，而内存通常是便宜的。 - Jonathan Leffler

一个快速的解决方法是，使用哈希表将列表节点的指针存储在键值对中 :-) - yadab

Answer 1

有一种叫做“跳跃表”的东西可以使用。

它是一组有序列表。每个列表都跳过更多的列表项。这使您可以进行一种二进制搜索。然而，维护这些列表更加困难。

- Zan Lynx

---

这看起来非常有前途。谢谢你提供链接。 - David Watson

Answer 2

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

如果你想让搜索更快，不要使用链表。例如，你想使用二叉树来实现，但正如Matthew Flaschen在评论中所说，这是完全不同于你现在使用的实现方式。

- Michael Todd

Answer 3

假设您的双向链表已排序，并且您有一组要搜索的项目，我建议研究构建自平衡二叉搜索树的问题。树的构建可能需要一些时间，但如果您有一个长列表要搜索，则会分摊成本。

- Pirooz