快速搜索双向链表

Question

我目前有一个简单的数据库程序，它从文本文件中读取键并将它们存储在双向链表中（如果需要，稍后会读取值）。目前，我对列表进行顺序搜索，但这显然相当慢。我希望还有另一种方法可以做到。我正在阅读有关二叉树（特别是红黑树）的内容，但我对它们不太了解，并希望我能从 stackoverflow hivemind 中看到一些东西:)我想我的问题是，最快的方法是什么在双向链表中进行搜索？

编辑：忘记说列表已排序。不知道这是否会改变什么。另外，我只读取keys的原因是最大值长度是1024*32字节，我觉得太大了。请注意，这是一项作业，因此“典型使用场景”不适用。教授们可能会对这件事进行压力测试，而我不想分配那么大的块。

Answer 1

您可以使用一种称为“跳过列表”的东西。

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