快速搜索双向链表

发布时间：2020-12-16 09:30:22 所属栏目：百科来源：网络整理

导读：我目前有一个简单的数据库程序,它从文本文件中读取键并将它们存储在双向链表中(如果需要,则稍后读取值).目前,我在列表上进行顺序搜索,但这显然很慢.我希望还有另一种方法可以做.我正在阅读有关二叉树(特别是红黑树)但我不太了解它们,并且希望我可以从stackov

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

编辑：忘了说列表已排序.不知道这是否会改变任何事情.另外,我只读取键的原因是最大值长度是1024 * 32字节,我觉得它太大了.请注意,这是针对分配的,因此“典型使用方案”不适用.教授们很可能会对这件事情进行压力测试,而且我不想把这块大块的东西用来制作.

解决方法

你可以使用一种叫做“ skip list”的东西.

它是一组有序列表.每个列表都会跳过更多列表项.这使您可以进行二进制搜索.但是,维护列表更加困难.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!