c - 高效的列表数据结构

Question

我需要一个列表类型的数据结构在项目中实现。实际上它不一定是某种列表，但它必须是快速的，我将使用它不断地从中插入/删除/检索数据(其他数据结构)。我可能会插入一些东西，搜索，再次插入，删除，再次搜索等等，所以操作是随机的。

到目前为止，我发现跳过列表是最快的，还有什么比这更快的呢？

Answer 1

很大程度上取决于您选择的语言。 C 使您可以最大程度地控制最终的数据结构，并且您最终将获得最快的实现之一。当然，很容易搬起石头砸自己的脚。相当糟糕。 Python 抽象了很多列表数据结构，我发现它一直很快，但我也没有过分强调它。

我建议检查 freshmeat 是否有预建的 C 库，您可以将其重新用于您的任务。也许维基百科关于跳过列表的页面会让您指向更多:http://en.wikipedia.org/wiki/Skip_list

数据结构是一门深奥的学科，需要对大 O 表示法以及我们谈论“速度”和“效率”时的确切含义有很好的了解，否则您将无法做出客观的比较。最后，一切都需要权衡取舍。选择一种数据结构，它最能模拟你的数据，以及你打算如何操作它。如果您的任务相当随机，请回到设计阶段并问问自己如何在到达数据结构之前改进发生的事情。也就是说，敲定你的算法，然后选择一个数据结构来补充它。