如果在列表中间插入，LinkedList是否真的比ArrayList快？

– LinkedList和ArrayList什么区别？ 什么时候最好使用LinkedList ？

我认为每个Java开发人员至少在访谈时都听过一次这个问题。

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

这是这个问题的常见答案。 大家都知道。 每当你问一个关于List实现之间差异的问题时，你会得到如下答案：

我什么时候应该使用LinkedList？ 什么时候需要在元素之间或开始时有效删除？

从这里

忘了提到插入费用。 在LinkedList中，一旦你有正确的位置，插入成本为O(1) ，而在ArrayList中它会上升到O(n) – 必须移动经过插入点的所有元素。

从这里

当您希望能够在列表中间插入项目（例如优先级队列）时，链接列表优于数组。

从这里

ArrayList较慢，因为它需要复制部分数组才能删除已经空闲的插槽。 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 linkedList = new LinkedList(); List arrayList = new ArrayList(); 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时间：114098106

AL时间：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 linkedList = new LinkedList(); List arrayList = new ArrayList(); 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时间：27581163

AL时间：3103051

哦，ArrayList仍然比LinkedList快。 是什么原因？ 这个神话被破坏了吗？ 或许我错了？

Answer 1

破获

并不是的。 这里

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

你不只是插入项目; 你每次都要支付从头到尾迭代的费用。 当然，那是O(i) 。

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

总之，对于99％或更多的实际案例， ArrayList是更好的选择，并且利用LinkedList的狭隘优势需要非常谨慎。

关于微博加密JVM的一般说明

我还应警告您，您的基准测试代码严重不足。 在JVM上进行微操作时，需要注意相当大的事项清单，例如：

• 总是热身代码让JIT编译器得到它;
• 由于精度/精度问题，要非常小心地解释nanoTime结果。 使读数增长至少几毫秒（百万纳秒）以确保可靠性;
• 控制垃圾收集器的虚假副作用;
• 等等

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

Answer 2

为了演示add（）操作的（in）有效性，最好使用ListIterator对象而不是list对象。 如果直接在链表上使用add（）方法，它将从列表头开始，并且必须迭代到要插入项的位置。 这部分需要O（ n ）。 如果使用ListIterator，它将保持我们添加元素的位置，并且算法不必每次都迭代到列表的中间。

 import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.ListIterator; public class Test { public static void main(String... args) { final int MAX_VAL = 10000; List linkedList = new LinkedList(); List arrayList = new ArrayList(); 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:\t" + (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:\t" + (System.nanoTime() - time)); //Reset the lists linkedList = new LinkedList(); arrayList = new ArrayList(); for(int i = 0; i < MAX_VAL; i++) { linkedList.add(i); arrayList.add(i); } time = System.nanoTime(); ListIterator li = linkedList.listIterator(MAX_VAL/2); for(int i = 0; i < MAX_VAL; i++) { li.add(i); } System.out.println("LL iterator:\t" + (System.nanoTime() - time)); time = System.nanoTime(); ListIterator ali = arrayList.listIterator(MAX_VAL/2); for(int i = 0; i < MAX_VAL; i++) { ali.add(i); } System.out.println("AL iterator:\t" + (System.nanoTime() - time)); } } 

我的结果显示在LinkedList上使用ListIterator可以在“中间”中插入元素时获得最佳性能：

 LL time: 237819474 AL time: 31410507 LL iterator: 5423172 AL iterator: 23975798 

Answer 3

您的测试存在偏差 – 它不能衡量通常的性能差异。

关于LinkedList结构的一般观察（与ArrayList相比，对于大型列表）：

1. 在头部或尾部添加/删除节点非常快
2. 从中间获取元素非常慢
3. 当你接近列表的任何一端时，获得一个元素变得更快（线性）
4. 从头部或尾部获取元素接近ArrayList的速度
5. 在中间某处添加/删除元素是两个操作：获取加上节点插入
6. 如果您使用ListIterator，您可以在中间的某处添加/删除节点并避免获取 – 一个非常快速的操作

你的测试打算测试（5）。

但它始终执行最坏的情况 – 在中间添加/删除元素。

您的微基准测试会产生系统错误 。 您需要统一或随机分发添加/删除位置。 或者使用真实复杂且具有挑战性的应用程序进行宏观基准测试 。

关于创建准确的微观基准的挑战的有趣读物： Java理论与实践：有缺陷的微基准的剖析

Answer 4

我重写了Matej的程序，随机选择一个方法并为每种方法运行50个试验的数组。 如果您在每个类别中平均进行最快一半的试验，那么结果如下：

LL：570
AL：120
LL迭代器：1
AL迭代器：60

LL迭代器确实需要很多分拣时间。 在最坏的情况下，由于预热（第一个周期）和gc（未排序数据的随机尖峰），它的性能下降了15倍。

 import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.ListIterator; import java.util.Random; public class TestList { public static void main(String... args) { final int MAX_VAL = 10000; int[] currentIndex = {0, 0, 0, 0}; int[] remaining = {50, 50, 50, 50}; int[][] sequence = new int[4][50]; while (keepWorking(remaining)) { //run 50 tests for each case at random int currentMethod = chooseMethod(remaining); //choose case. Probability is higher for tests with less trials switch (currentMethod) { //run a test based on the choice case 0: sequence[currentMethod][currentIndex[currentMethod]] = getLL(MAX_VAL); break; case 1: sequence[currentMethod][currentIndex[currentMethod]] = getAL(MAX_VAL); break; case 2: sequence[currentMethod][currentIndex[currentMethod]] = getLLIt(MAX_VAL); break; default: sequence[currentMethod][currentIndex[currentMethod]] = getALIt(MAX_VAL); break; } remaining[currentMethod]--; currentIndex[currentMethod]++; } for (int[] ar : sequence) { Arrays.sort(ar); } System.out.println("Time (us\nLL \tAL\tLL incr\t AL incr"); for (int i = 0; i < sequence[0].length; i++) { System.out.println(sequence[0][i] + "\t" + sequence[1][i] + "\t" + sequence[2][i] + "\t" + sequence[3][i]); } System.out.println("\nTime normalized to fastest run of a method\nLL\tAL\tLL incr\t AL incr"); for (int i = 0; i < sequence[0].length; i++) { System.out.print(i); for (int j = 0; j < sequence.length; j++) { //to 4 int a = sequence[j][i] / (sequence[j][0]/100); //to keep result within the scope of int System.out.print("\t" + a); } System.out.println(); } } public static boolean keepWorking(int[] remaining) { for (int i = 0; i < remaining.length; i++) { if (remaining[i] > 0) { return true; } } return false; } public static int chooseMethod(int[] rem) { int[] bins = new int[rem.length]; for (int i = 0; i < rem.length; i++) { for (int j = i; j < rem.length; j++) { bins[j] += rem[i]; } } int randomNum = new Random().nextInt(bins[rem.length - 1]); for (int i = 0; i < bins.length; i++) { if (randomNum < bins[i]) { return i; } } return -1; } public static int getLL(int MAX_VAL) { List linkedList = new LinkedList<>(); for (int i = 0; i < MAX_VAL; i++) { linkedList.add(i); } long time = System.nanoTime(); for (int i = 0; i < MAX_VAL; i++) { linkedList.add(MAX_VAL / 2, i); } return (int) (System.nanoTime() - time)/1000; } public static int getAL(int MAX_VAL) { List arrayList = new ArrayList<>(MAX_VAL); for (int i = 0; i < MAX_VAL; i++) { arrayList.add(i); } long time = System.nanoTime(); for (int i = 0; i < MAX_VAL; i++) { arrayList.add(MAX_VAL / 2, i); } return (int) (System.nanoTime() - time)/1000; } public static int getLLIt(int MAX_VAL) { List linkedList = new LinkedList<>(); for (int i = 0; i < MAX_VAL; i++) { linkedList.add(i); } long time = System.nanoTime(); ListIterator li = linkedList.listIterator(MAX_VAL / 2); for (int i = 0; i < MAX_VAL; i++) { li.add(i); } return (int) (System.nanoTime() - time)/1000; } public static int getALIt(int MAX_VAL) { List arrayList = new ArrayList<>(MAX_VAL); for (int i = 0; i < MAX_VAL; i++) { arrayList.add(i); } long time = System.nanoTime(); ListIterator ali = arrayList.listIterator(MAX_VAL / 2); for (int i = 0; i < MAX_VAL; i++) { ali.add(i); } return (int) (System.nanoTime() - time)/1000; } } 

Answer 5

必须谨慎对待这样的简单分析：

• 垃圾收集可能在不可预测的时间发生，从而减慢不可预测的部分。
• JRE首次启动时速度较慢，后来“预热”。

要解决这个问题，请在循环中进行分析，以随机顺序多次重复这两种情况，并采用典型值而不是极值。 这有时会产生不同的结果。

Answer 6

因为ArrayList按顺序存储值，因此1：更快地添加值（只是在最后一个索引中添加值）2：更新或删除更慢（在我们到达节点之前必须遍历整个列表）

因为数组列表适用于LinkedList概念1：插入速度较慢（需要查找对prev或next值的引用）2：更新速度更快（因为只能通过引用访问确切的节点）

这个链接可以参考

Answer 7

在理想的情况下，您总是插入排序列表。 首先，使用二进制搜索机制找到插入索引，然后在该索引处插入。 此外，在执行此操作时，您无法始终使用相同的列表器。 您将迭代器设置为新索引位置evrytime。 所以在这种现实生活中，插入速度更快。