在list中间插入的情况下，LinkedList真的比ArrayList快吗？

Question

-LinkedList和ArrayList有什么区别？什么时候使用LinkedList更好？

我想每个Java开发人员至少在面试中听过一次这个问题。

-如果您希望能够在列表中间插入项目，则首选链表。

从这里

忘了提到插入费用。在LinkedList中，一旦有了正确的位置，插入将花费O(1)，而在ArrayList中，插入将上升到O(n)-所有超过插入点的元素都必须移动。

从这里

还有更多...

但你有没有尝试过自己复制它？我昨天试了一下，得到了这些结果：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test {
    public static void main(String... args) {
        final int MAX_VAL = 10000;
        List<Integer> linkedList = new LinkedList<Integer>();
        List<Integer> arrayList = new ArrayList<Integer>();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }
        long time = System.nanoTime();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(MAX_VAL/2, i);
        }
        System.out.println("LL time: " + (System.nanoTime() - time));
        time = System.nanoTime();
        for(int i = 0; i < MAX_VAL; i++) {
            arrayList.add(MAX_VAL/2, i);
        }
        System.out.println("AL time: " + (System.nanoTime() - time));
    }
}

产出：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test {
    public static void main(String... args) {
        final int MAX_VAL = 10000;
        List<Integer> linkedList = new LinkedList<Integer>();
        List<Integer> arrayList = new ArrayList<Integer>();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }
        long time = System.nanoTime();
        for(int i = 0; i < MAX_VAL/2; i++) {
            linkedList.remove(MAX_VAL/2);
        }
        System.out.println("LL time: " + (System.nanoTime() - time));
        time = System.nanoTime();
        for(int i = 0; i < MAX_VAL/2; i++) {
            arrayList.remove(MAX_VAL/2);
        }
        System.out.println("AL time: " + (System.nanoTime() - time));
    }
}

哦，ArrayList还是比LinkedList快。原因何在？这个神话破灭了吗？也许我错了？

Answer 1

破灭

不是真的。这里

for(int i = 0; i < MAX_VAL; i++) {
    linkedList.add(MAX_VAL/2, i);
}

你不只是插入项目；您每次都要付出从开始到i迭代的代价。当然，这是o(i)。

null