addFirst为什么比addLast慢？

Question

addFirst:

pride-and-prejudice.txt
Total words: 125901
Total different words: 6530
bst time1: 0.0945035

pride-and-prejudice.txt
Total words: 125901
Total different words: 6530
link time2: 1.778542

Process finished with exit code 0

LinkedListSet改为addLast结果如下：

pride-and-prejudice.txt
Total words: 125901
Total different words: 6530
bst time1: 0.0927352

pride-and-prejudice.txt
Total words: 125901
Total different words: 6530
link time2: 0.3961773

Process finished with exit code 0

虽然链表的时间复杂度为O(n), 单从add操作看addFirst时间复杂度为O(1)。
addLast时间复杂度为O(n)，后者反而速度更快。
请问这是为啥？

Answer 1

liuyubobobo 2020-06-11 03:53:21

赞实验精神！

我试验了一下，确实如此。稍微查看了一下，和数据分布相关。准确的说，是 add 函数中 if(!list.contains(e)) 这个判断的原因。

如果使用 addLast，会导致高频词都出现在尽量前面的位置，而 contains 是从前向后扫描的，能尽快找到重复的词，忽略掉；

而使用 addFirst，先添加的词慢慢都到了后面，所以相当于高频词都在后面的位置。contains 依然是从前向后扫描，找到重复的词就会变慢。

可以试一下，如果将 if(!list.contains(e)) 这判断删除，就能正确反映 addFirst 和 addLast 的性能了。

这真是一个有意思的问题。大赞！

继续加油！：）

• 提问者 qq_萌新_4 #1

  非常感谢！确实如此，如果头添加，高频词汇会放到后面，因为小说越后面重复的单词就越多，如果把单词放在前面就好找了。这个陷阱真的好难看出来啊