比较链接列表和自定义链接列表的运行

Question

这是一项家庭作业，它并不难，这只是我的理解可能有缺陷。

所以我有两个链表：一个双向链表和一个自定义链表。我们只关心两个函数：void add（）和布尔值包含（）。

MyLinkedList扩展AbstractList中和功能不变，但自定义LinkedList的延伸MyLinkedList和覆盖了包括（）方法，当一个元素被抬起头来，它总是会被移动到列表的前面，你知道，以提高更频繁使用的单词的查找时间。

它也覆盖了add（）方法，使得项目不会添加到列表的后面，而是添加到列表的最前面。

而且我有一个dictionary.txt文件这是一个包含（〜10000字）的字典。

程序所做的是创建一个MyLinkedList对象和一个自定义链表对象，并将dictionary.txt单词添加到相应的列表中。所以这应该意味着，在MyLinkedList中，单词是按顺序排列的，而在自定义链接列表中则是相​​反的顺序。

然后该程序接受一个txt文件，例如romeo-and-juliet.txt并遍历该txt文件的前10000个单词，如果单词匹配MyLinkedList对象中的单词并为自定义链表对象执行单独运行。

问：为什么自定义链接列表运行得比MyLinkedList快？我的答案是，由于自定义链接列表将经常使用的搜索术语移到前面，所以查找时间更短，所以它的运行速度将比MyLinkedList快。我希望我的回答听起来不错，随时可以改进。

现在一个令人费解的是，现在我们使用的是罗密欧和juliet.txt作为字典文件本身，这是发生了什么：

即最短的时间最长的一次：

1. MyLinkedList使用罗密欧和朱丽叶字典〜上dictionary.txt 80ms的

2. 自定义列表〜160毫秒

3. MyLinkedList上在罗密欧和朱丽叶字典〜dictionary.txt〜360ms

4. 自定义列表390ms

问：为什么会这样？如果我们只使用故事中的词语作为词典的范围，那为什么它对自定义链表更慢？

P.S.如果问题的任何部分不清楚，请随时告诉我，我会编辑我遗漏的任何内容。

Answer 1

自定义列表总是添加单词前，词典将在条款是如何在阅读顺序相反。对于普通字典，不会有太大的差别，但是当你使用罗密欧与朱丽叶本身作为字典的文本，这就是你将要结束的：

Romeo and Juliet：“两个家庭，两个人都有尊严...比朱丽叶和她的罗密欧。”

MyLinkedList： “两个”， “家庭”， “既”， “一点通”， “中”， “尊严”，...

custom list： “罗密欧”， “她”， “和” “朱丽叶”，“中”，“这个”，“比”，...

既然你是为了寻找对R & j的文本，当你搜索对MyLinkedList的R &Ĵ字典，第一个字将始终在第一位置中找到，第二个字将始终被发现在第二位置上被发现等，作为最坏的可能查找，或更快，如果字具有已经出现在剧中。

这很多，很多比在正常字典中查找每个单词更快。

---

现在让我们来看看当您开始搜索custom list时会发生什么。你正在搜索的第一个单词是字典中的最后一个单词，或者如果它在剧本中出现多次，则是早期单词。但是，与搜索MyLinkedList时相比，搜索时间肯定会更长。然后，更糟糕的是，您将该单词移到字典的前面，将第二个单词的“已知”位置推到字典的最后，然后再搜索它。这将有所减轻如常用词（例如“一”，“该”，“和”）冒泡到前面，但它不会克服了大量的优点，即MyLinkedList搜索过。