ArrayList和LinkedList之间的性能差异

是的，这是一个老话题，但我仍然有些困惑。

在Java中，人们说：

如果我随机访问它的元素，ArrayList比LinkedList快。我认为随机访问意味着“给我第n个元素”。为什么ArrayList速度更快？

LinkedList比ArrayList更快地删除。我明白这一点。由于内部备份数组需要重新分配，因此ArrayList速度较慢。代码说明：

List<String> list = new ArrayList<String>(); list.add("a"); list.add("b"); list.add("c"); list.remove("b"); System.out.println(list.get(1)); //output "c"

LinkedList比用于插入的ArrayList快。插入是什么意思？如果这意味着要移回一些元素，然后把元素放在中间的空白位置，ArrayList应该比LinkedList慢。如果插入只意味着添加（对象）操作，那么这怎么会慢呢？

如果我随机访问它的元素，ArrayList比LinkedList快。我认为随机访问意味着“给我第n个元素”。为什么ArrayList速度更快？

ArrayList直接引用列表中的每个元素，所以它可以在常量中获得第n个元素。 LinkedList必须从头开始遍历到第n个元素。

LinkedList比ArrayList更快，用于删除。我明白这一点。由于内部备份数组需要重新分配，因此ArrayList速度较慢。

ArrayList速度较慢，因为它需要复制数组的一部分，以删除已经变为空闲的插槽。如果使用ListIterator.remove() API完成删除操作， LinkedList只需要操作几个引用; 如果删除是通过值或索引完成的，则LinkedList必须先扫描整个列表才能find要删除的元素。

如果这意味着移动一些元素，然后把元素放在中间的空白点，那么ArrayList应该会变慢。

是的，这就是它的意思。 ArrayList确实比LinkedList慢，因为它必须释放数组中间的一个槽。这涉及到移动一些引用，最坏的情况是重新分配整个数组。 LinkedList只需要操作一些引用。

现在忽略这个答案。其他答案，尤其是aix的答案，大都是正确的。从长远来看，他们是打赌的方式。如果你有足够的数据（在一台机器上的一个基准testing中，似乎大概有一百万个条目），ArrayList和LinkedList目前的工作方式如同广告。但是，在21世纪初还有一些优点可以应用。

现代计算机技术似乎在我的testing中给arrays带来巨大的优势。数组元素可以以疯狂的速度移动和复制。因此，在大多数实际情况下，数组和ArrayList在插入和删除方面的performance要优于LinkedList，通常情况下也是如此。换句话说，ArrayList将在自己的游戏中击败LinkedList。

ArrayList的缺点是它往往会在删除后挂在内存空间上，LinkedList在放弃条目的时候放弃了空间。

数组和ArrayList的更大的不利之处在于它们是片段可用的内存，并且是垃圾收集器的过度工作。随着ArrayList的扩展，它会创build新的更大的数组，将旧数组复制到新数组，并释放旧数组。内存填充大量连续的空闲内存块，对于下一次分配来说不够大。最终没有合适的分配空间。尽pipe90％的内存是免费的，但是没有哪个个体能够胜任这项工作。 GC将疯狂地移动，但如果重新排列空间需要很长时间，则会抛出OutOfMemoryExceptionexception。如果它不放弃，它仍然可以减慢你的程序的方式。

最糟糕的是这个问题很难预测。您的程序将运行良好的一次。然后，使用less量的内存，没有任何警告，它会减慢或停止。

LinkedList使用小而精致的内存，而GC则喜欢它。当您使用99％的可用内存时，它仍能正常运行。

因此，一般情况下，对于不大可能删除大部分内容的较小数据集，或者对创build和增长进行严格控制时，请使用ArrayList。（例如，创build一个使用90％内存的ArrayList，并且在程序运行期间不使用它，这是没有问题的。不断创build和释放使用10％内存的ArrayList实例将会导致你死亡。）否则，请使用LinkedList （或者如果需要随机访问的话，可以使用某种地图）。如果你有非常大的集合（比如超过10万个元素），不用担心GC，并且计划大量的插入和删除操作，而且没有随机访问，可以运行几个基准来看看最快的。

ArrayList类是一个数组的包装类。它包含一个内部数组。

 public ArrayList<T> { private Object[] array; private int size; }

LinkedList是链接列表的包装类，具有pipe理数据的内部节点。

 public LinkedList<T> { class Node<T> { T data; Node next; Node prev; } private Node<T> first; private Node<T> last; private int size; }

请注意，目前的代码是用来显示类是如何，而不是实际的实现。知道实施可能如何，我们可以做进一步的分析：

如果我随机访问它的元素，ArrayList比LinkedList快。我认为随机访问意味着“给我第n个元素”。为什么ArrayList速度更快？

ArrayList的访问时间：O（1）。 LinkedList的访问时间：O（n）。

在数组中，您可以使用array[index]访问任何元素，而在链表中，您必须从first列表开始浏览所有列表，直到获取到所需的元素。

LinkedList比ArrayList更快，用于删除。我明白这一点。由于内部备份数组需要重新分配，因此ArrayList速度较慢。

ArrayList的删除时间：访问时间+ O（n）。 LinkedList的删除时间：访问时间+ O（1）。

ArrayList必须将所有元素从array[index]到array[index-1]从删除索引项开始。 LinkedList应该导航到该项目，然后通过从列表中分离来清除该节点。

LinkedList比ArrayList更快地删除。我明白这一点。由于内部备份数组需要重新分配，ArrayList速度较慢。

ArrayList的插入时间：O（n）。 LinkedList的插入时间：O（1）。

为什么ArrayList可以采取O（n）？因为当你插入一个新元素并且数组已满时，你需要创build一个更大尺寸的新数组（你可以使用像2 * size或3 * size / 2这样的公式计算新的尺寸）。 LinkedList只是在最后一个旁边添加一个新节点。

这种分析不仅在Java中，而且在C，C ++和C＃等其他编程语言中。

更多信息：

回答1：ArrayList在引擎下使用一个数组。访问ArrayList对象的成员与访问提供的索引处的数组一样简单，假定索引位于支持数组的范围内。一个LinkedList必须遍历其成员才能到达第n个元素。这是一个LinkedList的O（n），而ArrayList是O（1）。

在LinkedList中，元素在元素之前和之后都有一个引用。在ArrayList中，数据结构只是一个数组。

LinkedList需要遍历N个元素来获取第N个元素。 ArrayList只需要返回支持数组的元素N.
支持数组需要为新的大小重新分配，并且在删除的元素需要向上移动以填充空的空间之后复制整个或每个元素的数组。一个LinkedList只需要在删除元素之前的元素上移除之前的元素上的前一个引用，以及在删除的元素之前的元素上的下一个引用。更长时间来解释，但要做得更快。
同样的原因在这里删除。

对于ArrayLists和LinkedLists，remove（）和insert（）都具有O（n）的运行效率。然而线性处理时间背后的原因来自两个非常不同的原因：

在一个ArrayList中，你得到了O（1）中的元素，但实际上删除或插入的东西使得O（n），因为所有以下元素需要改变。

在一个LinkedList中，实际上需要O（n）来获得所需的元素，因为我们必须从最初开始，直到达到所需的索引。一旦我们到达那里，移除或插入就是不变的，因为我们只需要为insert（）更改1个remove（）引用和2个引用。

哪两个更快插入和删除取决于发生的地方。如果我们更接近开始，LinkedList会更快，因为我们必须经历相对较less的元素。如果我们更接近结束，ArrayList会更快，因为我们在那里得到了恒定的时间，只需要改变其余的几个元素。

奖金：虽然没有办法为ArrayList创build这两个方法O（1），但实际上有一种方法可以在LinkedList中执行此操作。比方说，我们想要通过我们的方式去除和插入整个列表。通常你会从一开始就使用LinkedList开始每个元素，我们也可以用Iterator“保存”当前正在处理的元素。在Iterator的帮助下，当在LinkedList中工作时，我们得到了一个O（1）的remove（）和insert（）效率。使它成为唯一的性能好处，我知道LinkedList总是比ArrayList好。

ArrayList ：ArrayList具有像数组一样的结构，它具有对每个元素的直接引用。所以在ArrayList中，rendom访问是快速的。

LinkedList ：在LinkedList中获得第n个元素，你必须遍历整个列表，与ArrayList相比需要时间。每个元素都有一个到它以前的＆nest元素的链接，所以删除很快。

ArrayList： ArrayList类扩展了AbstractList，并实现了List接口和RandomAccess（标记接口）。 ArrayList支持可以根据需要增长的dynamic数组。 它给了我们第一次元素迭代。

LinkedList：根据索引位置对LinkedList进行sorting，就像ArrayList一样，除了元素是双向链接的。这种链接为您提供了新的方法（超出了从List接口获得的内容），用于从开始或结束添加和删除，这使得它成为实现堆栈或队列的简单select。请记住，LinkedList的迭代速度可能比ArrayList缓慢， 但在需要快速插入和删除时 ， 这是一个不错的select。 从Java 5开始，LinkedList类已被增强以实现java.util.Queue接口。因此，它现在支持常见的队列方法：peek（），poll（）和offer（）。

即使它们看起来是完全相同的（同样实现了inteface List – 非线程安全），它们在添加/删除和search时间和消耗内存（LinkedList消耗更多）方面的性能方面给出了不同的结果。

如果使用性能O（1）进行高度插入/删除，则可以使用LinkedLists。如果使用性能为O（1）的直接访问操作，则可以使用ArrayLists。

此代码可能会使这些注释变得清晰，并且您可以尝试了解性能结果。（对不起锅炉代码）

 public class Test { private static Random rnd; static { rnd = new Random(); } static List<String> testArrayList; static List<String> testLinkedList; public static final int COUNT_OBJ = 2000000; public static void main(String[] args) { testArrayList = new ArrayList<>(); testLinkedList = new LinkedList<>(); insertSomeDummyData(testLinkedList); insertSomeDummyData(testArrayList); checkInsertionPerformance(testLinkedList); //O(1) checkInsertionPerformance(testArrayList); //O(1) -> O(n) checkPerformanceForFinding(testArrayList); // O(1) checkPerformanceForFinding(testLinkedList); // O(n) } public static void insertSomeDummyData(List<String> list) { for (int i = COUNT_OBJ; i-- > 0; ) { list.add(new String("" + i)); } } public static void checkInsertionPerformance(List<String> list) { long startTime, finishedTime; startTime = System.currentTimeMillis(); int rndIndex; for (int i = 200; i-- > 0; ) { rndIndex = rnd.nextInt(100000); list.add(rndIndex, "test"); } finishedTime = System.currentTimeMillis(); System.out.println(String.format("%s time passed at insertion:%d", list.getClass().getSimpleName(), (finishedTime - startTime))); } public static void checkPerformanceForFinding(List<String> list) { long startTime, finishedTime; startTime = System.currentTimeMillis(); int rndIndex; for (int i = 200; i-- > 0; ) { rndIndex = rnd.nextInt(100000); list.get(rndIndex); } finishedTime = System.currentTimeMillis(); System.out.println(String.format("%s time passed at searching:%d", list.getClass().getSimpleName(), (finishedTime - startTime))); } }