链表与字典数组

如果您只是将其用于查找，那么数组显然是两者中的最佳选择。你可以从O（n-logn）中的单词列表构建字典——只需构建一个数组并对其进行排序。查找是O（logn）和二进制搜索。

尽管您可以在O（n）中构建单词的链表，但查找平均需要查找n/2个单词。差别很大。给定一本包含128K个单词的英语词典，链表查找平均需要64000个字符串比较。二进制搜索最多需要17。

此外，n个单词的链表将比n个单词数组占用更多的内存，因为列表中需要next指针。

如果您需要更新字典的能力，那么如果与查找相比更新不频繁（几乎可以肯定是这样），您可能仍然希望使用数组。我想不出一个现实世界中的单词词典更新频率比查询频率更高的例子。

正如其他人所指出的，数组和链表都不是单词词典的最佳选择。但在给出的两个选项中，array在几乎所有情况下都是优越的。

没有一个答案。

如果你只想查找单个项目，两个明显的选择是基于哈希表的，如果你想查找项目范围，则是基于平衡树的。

如果进行大量搜索而插入或删除相对较少，则排序数组可以很好地工作。查找首选链表的情况要困难得多。根据情况（尤其是找到所有以"ste"开头的单词），尝试也可以非常有效（通常也能很好地减少给定数据集所需的存储）。

然而，这些确实是广泛的类别，而不是具体的实现。还有一些变体，如可扩展哈希和分布式哈希表，它们在特定情况下可能很有用（也有一些类似树的属性，因此基于范围的搜索可能相当有效）。

好吧，如果你正在构建一个字典，你会希望它是一个排序结构。所以你要的是一个排序数组或排序链表。

• 对于链表，检索是O(n)，因为你必须检查所有单词，直到找到你需要的单词。对于已排序的数组，可以使用二进制搜索来找到正确的位置，即O(log n)
• 对于排序数组，插入是O(log n)来查找正确的位置（二进制搜索），然后是O(n)来插入，因为您需要向下推所有内容。对于链表，它将是O(n)来查找位置，然后是O(1)来插入，因为您只需要调整指针。这同样适用于删除

由于您不会更新太多字典，因此只需在O(nlog n)时间内构建并排序数组即可（例如使用快速排序）。之后，查找是使用二进制搜索的O(log n)。此外，正如delnan下面提到的，使用数组的优点是，您访问的所有内容在内存中都是顺序的；即数据被本地化（参考的位置）。这样可以最大限度地减少缓存未命中（代价高昂）。使用链表时，数据会分散在各处，并且不能保证它们靠得很近，这会增加缓存未命中的几率。考虑到这一点，在给定两个选项的情况下，使用数组。

如果你使用红黑树实现一个排序的哈希图，你可以做得更好（你的树条目，也就是键，可以与哈希图耦合）；这里的搜索、插入和删除是O(log n)。但这实际上取决于你的行为特征；如果您只进行查找，那么一个简单的hashmap将是最好的（O(1)检索）。

您可以使用的另一个有趣的数据结构是Trie，其中插入和查找是O(m)；CCD_ 17是字符串的长度。