addFirst为什么比addLast慢？
来源：7-3 集合类的复杂度分析
qq_萌新_4
2020-06-10
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)，后者反而速度更快。
请问这是为啥？
写回答
1回答
-
赞实验精神！
我试验了一下，确实如此。稍微查看了一下，和数据分布相关。准确的说，是 add 函数中 if(!list.contains(e)) 这个判断的原因。
如果使用 addLast，会导致高频词都出现在尽量前面的位置，而 contains 是从前向后扫描的，能尽快找到重复的词，忽略掉；
而使用 addFirst，先添加的词慢慢都到了后面，所以相当于高频词都在后面的位置。contains 依然是从前向后扫描，找到重复的词就会变慢。
可以试一下，如果将 if(!list.contains(e)) 这判断删除，就能正确反映 addFirst 和 addLast 的性能了。
这真是一个有意思的问题。大赞！
继续加油！：）
412020-06-11
相似问题