快速搜索双向链表
我目前有一个简单的数据库程序，它从文本文件中读取键并将它们存储在双向链表中（如果需要，稍后会读取值）。目前，我对列表进行顺序搜索，但这显然相当慢。我希望还有另一种方法可以做到。我正在阅读有关二叉树（特别是红黑树）的内容，但我对它们不太了解，并希望我能从 stackoverflow hivemind 中看到一些东西:)我想我的问题是，最快的方法是什么在双向链表中进行搜索？
编辑：忘记说列表已排序。不知道这是否会改变什么。另外，我只读取keys的原因是最大值长度是1024*32字节，我觉得太大了。请注意，这是一项作业，因此“典型使用场景”不适用。教授们可能会对这件事进行压力测试，而我不想分配那么大的块。
I currently have a simple database program that reads keys in from a text file and stores them in a doubly linked list (values are read later if they are required). Currently, I do a sequential search on the list, but that is clearly rather slow. I was hoping that there is another way to do. I was reading about binary trees (in particular, red black trees) but I don't know to much about them, and was hoping that I could gleam something from the stackoverflow hivemind :) I suppose my question is, what is the fastest way to do a search in a doubly linked list?
EDIT: Forgot to say that the list is sorted. Don't know if that changes anything. Also, the reason I only read in keys is that the max value length is 1024*32 bytes, which I feel is too large. Note that this is for an assignment, so "typical usage scenarios" don't apply. The professors are likely going to be stress testing the hell out of this thing, and I don't want to be mallocing blocks that big.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以使用一种名为“跳过列表”的东西。
它是一组有序列表。每个列表都会跳过更多列表项。这使您可以进行某种形式的二分搜索。然而，维护列表更加困难。
There is a thing called a "skip list" that you could use.
It is a set of ordered lists. Each list skips more of the list items. This lets you do a form of binary search. However, maintaining the lists is more difficult.
在未排序的双向链表中进行搜索的最快方法是一次搜索一个元素。
如果您想加快搜索速度，请不要使用链接列表。例如，您使用二叉树的想法肯定会更快，但正如 Matthew Flaschen 在评论中所说，它与您现在使用的实现完全不同。
The fastest way to do a search in an unsorted doubly-linked list is one element at a time.
If you're trying to make search faster, don't use a linked list. Your idea of using a binary tree, for example, will certainly be faster, but as Matthew Flaschen said in comments, it's a completely different implementation from what you're using now.
鉴于您的双向链表已排序，并且您有一个要搜索的项目列表，我建议研究构建自平衡二叉搜索树的问题。树的构建可能需要一些时间，但如果您有很长的要搜索的项目列表，那么它会被摊销。
Given that your doubly-linked list is sorted, and you have a list of items to search for, I suggest looking into the problem of building a self-balancing binary search tree. The tree construction could take some time, but it will be amortized if you have a long list of items to search for.