比较链表和自定义链表的运行情况

Question

这是一个家庭作业，并没有那么难，只是我的理解可能有缺陷。

所以我有两个链表：双链表和自定义链表。我们只关心两个函数：void add（）和boolean contains（）。

MyLinkedList扩展了AbstractList，函数未被触及，但自定义linkedList扩展了MyLinkedList并重写了contains（）方法，这样在查找元素时，它总是会移动到列表的前面，以缩短更常用单词的查找时间。

它还重写add（）方法，使项目不会添加到列表的后面，而是添加到列表的前面。

我有一本字典。txt文件，这是一个包含（~10000个单词）的字典。

程序所做的是创建MyLinkedList对象和自定义linkedlist对象，并添加字典。将txt单词添加到相应的列表中。这意味着在MyLinkedList中，单词是按顺序排列的，而在CustomLinkedList中，单词是按相反顺序排列的。

然后，该程序接收一个txt文件（例如romeo-and-juliet.txt），并遍历该txt文件的前10000个单词，如果这些单词与MyLinkedList对象中的单词匹配，并为自定义Linkedlist对象单独运行。

问：为什么自定义LinkedList比MyLinkedList运行得更快？我的答案是，由于自定义的LinkedList将常用的搜索词移到前面，查找时间更短，所以它比MyLinkedList运行得更快。我希望我的答案听起来不错，请随意改进。

现在令人困惑的是，我们现在正在使用罗密欧和朱丽叶。txt作为字典文件本身，会发生以下情况：

i、 e.从最短时间到最长时间：

>

MyLinkedList使用romeo-and-juliet字典~80ms

字典上的自定义列表。txt~160ms

MyLinkedListdictionary.txt~360ms

罗密欧与朱丽叶词典上的自定义列表~390ms

问：为什么会这样？如果我们只使用故事的单词作为字典的范围，为什么自定义链接列表的速度较慢？

另外，如果问题的任何部分不清楚，请随时告诉我，我将编辑我遗漏的任何内容。

Answer 1

由于自定义列表总是将单词添加到前面，因此字典的顺序将与阅读术语的顺序相反。对于普通的字典来说，这不会有太大的区别，但是当你使用《罗密欧与朱丽叶》这本书作为字典时，你最终会得到：

罗密欧和朱丽叶：“两个家庭，在尊严上都一样……比朱丽叶和她的罗密欧更重要。”

MyLinkedList："两个"，"家庭"，"两者"，"相似"，"在"，"尊严"，...

自定义列表：“罗密欧”、“她”、“和”、“朱丽叶”、“的”、“这个”、“比”。。。

因为您正在搜索R的文本

这比在普通词典中查找每个单词要快得多。

现在让我们考虑一下，当你开始搜索<代码>自定义列表< /代码>时会发生什么。您要搜索的第一个单词是词典中的最后一个单词，如果它在游戏中出现多次，则更早。然而，找到它肯定要比在MyLinkedList中搜索时花费更长的时间。然后，更糟糕的是，你把那个词移到字典的前面，把第二个词的“已知”位置推到字典的最末端，就在你搜索它之前。当常用词（如“a”、“the”、“and”）出现在最前面时，这会有所缓解，但它不会克服MyLinkedList搜索所具有的巨大优势。