如何使用LinkedList和ArrayList来衡量性能

Question

我已经实现了冒泡和快速排序算法，现在我必须使用以下LinkedList和ArrayList代码来衡量它们的性能。

Instant start = Instant.now();
Sort…
Instant stop = Instant.now();
Duration duration = Duration.between(start, stop);
System.out.println(duration);

为什么我们在使用ArrayList和LinkedList时会得到不同的时间？

Answer 1

ArrayList和LinkedList有不同的实现。

检索具有ArrayList的元素可以在O(1(中完成，因为您只需要知道元素的索引，就可以直接从存储它的数组中检索它。使用LinkedList，在获得请求的元素之前，您需要对列表中的元素进行迭代，这样就可以在O(n(中完成。

这种差异可以传播到您的排序时间。

Answer 2

因为它们的结构不同。例如，ArrayList的迭代速度更快，但LinkedList的插入和删除速度更快。