为什么在LinkedList末尾添加一个元素要比ArrayList花费更长的时间

Question

我了解到，在LinkedList的末尾添加一个元素是O(1(，因为我们只是将一个对象添加到列表的最后一个节点。ArrayList也是O(1，但最坏的情况是O(n(，因为当数组中没有空间时，必须调整大小。我试着对它进行测试，期待我学到的结果，但ArrayList在添加1000万个元素方面比LinkedList快得多。

经过多次尝试后，ArrayList花费了大约570毫秒，而LinkedList花费了约1900毫秒。

public static void listPractice(List<String> test) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < 10_000_000; i++) {
test.add(String.valueOf(i));
}
System.out.println(System.currentTimeMillis() - startTime);
}

看起来很奇怪。我一直在阅读其他的讨论，我看到很多程序员说LinkedList，简而言之，有点糟糕。这是证据，还是我缺少的东西？

Answer 1

向数组中添加元素(不需要调整大小(需要将引用复制到空单元格中，并递增数组中对象元素的计数。

将元素添加到链表需要分配一个新节点，将前一个最后条目的"next"链接指向新的最后条目，将新条目的"next"置零，将头的"last"链接指针指向新条目，并将新条目的前一个链接指针指向前一个最终条目。然后将对象引用复制到新节点中，并递增列表中元素的计数。

简而言之，链表需要一个分配，并且比数组版本多写4次。

不过，如果您认为链表很糟糕，请尝试在重复从1000万个条目的数组中删除front元素的情况下使用数组。

有一些技术可以避免在数组中打乱所有条目，但除非是圆形数组，否则很可能会打乱。我看到的ArrayList源进行混洗，因此删除10000000个条目中的第一个条目将向下移动剩余的9999999个条目。删除下一个条目将不得不向下移动剩余的9999998个条目。。。

更不用说1000万条目的数组需要能够获得连续的40或80兆字节的内存。

教训是，不同的数据结构有不同的最佳点。