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

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

- 如果您希望能够在列表中间插入项目，则最好使用链表。

这是对这个问题的常见回答。每个人都知道。每次您询问有关 List 实现之间差异的问题时，您都会得到如下答案:

When should I use LinkedList? When do you need efficient removal in between elements or at the start?

From here

Forgot to mention insertion costs. In a LinkedList, once you have the correct position, insertion costs O(1), while in an ArrayList it goes up to O(n) - all elements past the insertion point must be moved.

From here

Linked lists are preferable over arrays when you want to be able to insert items in the middle of the list (such as a priority queue).

From here

ArrayList is slower because it needs to copy part of the array in order to remove the slot that has become free. LinkedList just has to manipulate a couple of references.

From here

还有更多...

但是你试过自己复现吗？我昨天试过并得到了这些结果:

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));
    }
}

输出:

LL time: 114098106

AL time: 24121889

那是什么？为什么 LinkedList 这么烂？也许我们应该尝试删除操作而不是添加？好的，让我们试试:

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));
    }
}

输出:

LL time: 27581163

AL time: 3103051

哦，ArrayList 还是比 LinkedList 快。是什么原因？这个神话破灭了吗？还是我错了？

最佳答案

BUSTED

不是真的。这里

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

您不只是插入项目；您每次都要支付从头到 i 的迭代成本。自然是 O(i)。

另一方面，列表必须非常大，您才能真正看到中间列表插入的性能优势。 System.arraycopy 是一个超快的操作，另一方面，每次插入 LinkedList 都需要分配一个节点实例。

总而言之，ArrayList 是 99% 或更多真实案例的更好选择，并且利用 LinkedList 的狭窄优势需要非常小心。

JVM 微基准测试的一般说明

我还应该警告您，您的基准测试代码存在严重缺陷。在 JVM 上进行微基准测试时，有相当多的 list 需要注意，例如:

• 始终预热代码，让 JIT 编译器处理它；
• 由于准确性/精度问题，在解释 nanoTime 结果时要非常小心。使读数至少增长到毫秒(百万纳秒)以确保可靠性；
• 控制垃圾收集器的虚假副作用；
• 等等

因此，建议使用现成的微基准测试框架，例如 OpenJDK's jmh .

关于java - 在列表中间插入的情况下，LinkedList 真的比 ArrayList 快吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16808777/