Java中的ArrayList和LinkedList的性能基准

Question

阅读此[问题]后：何时在arraylist上使用linkedlist？我试图基准基准的ArrayList和LinkedList的性能。但是我发现的结果与答案大不相同。就add（）而言，ArrayList性能比LinkedList好2-3时间。我知道linkedlist.Add（e element）是o（1）＆lt; --- - LinkedList的主要好处arraylist.add（e元素）为o（n-索引）但是结果表明，数组列表比linkedlist

快得多

任何人都可以解释这个行为

 public static void main(String[] args) {
    long start = System.currentTimeMillis();
    List<Integer> b = new LinkedList<Integer>();
    for (int i = 0; i < 1000000; i++) {
        b.add(i);
    }
    System.out.println(System.currentTimeMillis() - start);
    start = System.currentTimeMillis();
    List<Integer> a = new ArrayList<Integer>();
    for (int i = 0; i < 1000000; i++) {
        a.add(i);
    }
    System.out.println(System.currentTimeMillis() - start);
}

Answer 1

您仅测试列表的 append属性。

ArrayList和LinkedList是列表的具体实现。归根结底，您的基准目的是确定哪种列表更适合哪种情况。这就是为什么A 有效的基准测试将尝试针对列表接口提供的所有新操作和规定测试实现。

Answer 2

你很困惑。列表末尾添加元素是o（1）是两个列表。

ArrayList唯一的特殊情况是到达列表的容量时，该列表迫使ArrayList实例化新数组并将所有元素从旧元素复制到新元素。但这很少发生，因为每次完成时容量乘以1.5。

在两种情况下，列表中间添加一个元素都是O（n）。LinkedList必须迭代（从末端开始），直到找到必须插入新节点的位置。阵列列表必须将所有元素从插入索引转移到末尾。