我正在比较ArrayList和LinkedList中包含方法在0到1000的数字序列上的性能。
对于这两个列表，我都做了一个包含(400(。ArrayList的性能总是比LinkedList高3倍。使用JMH进行比较。
ArrayList的耗时329642纳秒
LinkedList花费了945881纳秒的
如果两个列表都具有contains方法的O(n(性能，为什么LinkedList会差3倍？
比较类别：
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class Comparation {
@State(Scope.Thread)
public static class MyState {
private List<Integer> arrayList = new ArrayList<>();
private List<Integer> linkedList = new LinkedList<>();
private int iterations = 1000;
@Setup(Level.Trial)
public void setUp() {
for (int i = 0; i < iterations; i++) {
arrayList.add(i);
linkedList.add(i);
}
}
}
@Benchmark
public boolean testLinkedListContains(MyState state) {
return state.linkedList.contains(400);
}
@Benchmark
public boolean testArrayListContains(MyState state) {
return state.arrayList.contains(400);
}
}
结果：
Benchmark Mode Cnt Score Error Units
Comparation.testArrayListContains avgt 20 329,642 ± 20,709 ns/op
Comparation.testLinkedListContains avgt 20 945,881 ± 43,621 ns/op
在ArrayList中，数据由数组支持，该数组的元素在内存中连续排列。因此，增加迭代器是非常快的->只需转到内存中的下一个地址。
在LinkedList中，情况不一定如此，内存不必是连续的——元素可以随机放置在内存中，因此从一个元素到另一个元素的速度有点慢。
您的问题是：如果两个列表都有contains方法的O(n(性能，为什么LinkedList会差3倍？
这并不违反O(n(复杂度的规则，将O(n(视为描述具有线性时间的算法的东西。与你所相信的相反，这并不意味着这些算法的所有实现都有相同的速度。这意味着它们所花费的时间是它们输入的线性函数，这里ArrayList快三倍，但如果你增加List中元素的数量，你可以看到ArrayList仍然快三倍。迭代它们的时间都是List中元素数量的线性函数。因此，如果说Arraylist执行该功能需要2n，而LinkedList执行该功能则需要10000n，则可以说它们都在O(n(中运行。
在这里，你确切地得出了LikedList差三倍的结论，这意味着它们具有相同的复杂性O(n(。
但是，如果通过增加输入的数量，你发现它不再恶化3倍，而是恶化5倍或30倍，并且这个数字基于输入的数量(即n(而增长，那么它们就没有相同的复杂性O(n(。
非常简单：不同的数据结构有不同的性能权衡。
https://dzone.com/articles/arraylist-vs-linkedlist-vs
LinkedList被实现为一个双链表。它在上的性能add and remove比Arraylist好，但在get and set上更差方法。
换句话说，如果你的动机是不断地修改列表，LinkedList可能是更好的选择。但是为了简单地创建和遍历列表；获胜"；。
继续：
随着更多元素添加到ArrayList，其大小也会增加动态地。它的元素可以使用get直接访问和set方法，因为ArrayList本质上是一个数组。…
随着添加更多元素，Vector和ArrayList需要空间。矢量每次数组大小增加一倍，而ArrayList的大小增加50%每次。…
然而，LinkedList也实现了Queue接口，它增加了更多方法，例如offer((、peek((、poll((，等等
。。。注意：ArrayList的默认初始容量非常大小的构造具有更高初始容量。这样可以避免调整大小的成本。
在这种情况下，数组更快。。但灵活性较差。