c - 高效的列表数据结构

Question

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

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

Answer 1

很大程度上取决于您选择的语言。C 为您提供了对最终数据结构的最大控制权，您最终将获得最快的实现之一。当然，很容易在脚下射击自己。比较糟糕。Python 抽象了很多列表数据结构，我发现它一直很快，但我也没有过分强调它。

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

数据结构是一门深奥的学科，需要在大 O 表示法上有良好的基础，当我们谈论“速度”和“效率”时，它究竟意味着什么，否则你将无法进行客观的比较。最后，一切都有取舍。选择一种数据结构，可以最接近地模拟您的数据以及您打算如何操作它。如果您的任务相当随机，请回到设计阶段并问自己如何改进在数据结构之前发生的事情。也就是说，敲定你的算法，然后选择一个数据结构来补充它。

Answer 2

哈希表/hashmap/dictionary 听起来像你想要的。例如， Python 中的字典。

Answer 3

您可能会查看BTree