ArrayList和LinkedList之间的性能差异 [英] Performance differences between ArrayList and LinkedList

问题描述

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

在Java中，人们说：

1. ArrayList是比LinkedList的更快，如果我随机访问它的元素。我想，随机访问的意思是给我的第n个元素。为什么ArrayList是更快？




2. 的LinkedList比ArrayList中删除更快。我理解这一点。 ArrayList中的速度较慢，因为内部后备达阵需要重新分配。一个code解释：

    列表＆LT;串GT;名单=新的ArrayList＆LT;串GT;（）;
   list.add（一）;
   list.add（B）;
   list.add（C）;
   list.remove（B）;
   的System.out.println（list.get（1））; //输出C
    




3. 的LinkedList比ArrayList中插入得更快。这是什么意思插在这里？如果这意味着一些元素回迁，然后把该元素在中间空白处，ArrayList的应该比LinkedList的慢。如果插入只意味着一个附加（对象）操作，怎么会这样慢？

解决方案

  

ArrayList是比LinkedList的更快，如果我随机访问它的元素。我想，随机访问的意思是给我的第n个元素。为什么ArrayList是更快？

的ArrayList 已到列表中的每一个元素的直接引用，因此它可以在固定时间内的第n个元素。 链表有从一开始遍历列表获取到第n个元素。

  

链表比ArrayList的删除更快。我理解这一点。 ArrayList中的速度较慢，因为内部后备达阵需要重新分配。

ArrayList的是慢，因为它需要在阵列的复制部分，以除去已成为自由的插槽。如果删除使用完成的<一href=\"https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html#remove--\"><$c$c>ListIterator.remove() API，的LinkedList 只是有操纵一对夫妇的参考;如果删除通过值或指数做，的LinkedList 已潜在地扫描整个表最先找到的元素（S）被删除。

  

如果这意味着将一些元素回去，然后把该元素在中间空白处，ArrayList中应该会比较慢。

是的，这是什么意思。 的ArrayList 确实比的LinkedList 慢，因为它必须释放数组中间的插槽。这涉及到围绕移动一些参考，并在最坏的情况下重新分配整个阵列。 的LinkedList 只是有操纵一些参考。

Yes, this is an old topic, but I still have some confusions.

In Java, people say:

1. ArrayList is faster than LinkedList if I randomly access its elements. I think random access means "give me the nth element". Why ArrayList is faster?

2. LinkedList is faster than ArrayList for deletion. I understand this one. ArrayList's slower since the internal backing-up array needs to be reallocated. A code explanation:

   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"
   

3. LinkedList is faster than ArrayList for insertion. What does insertion mean here? If it means to move some elements back and then put the element in the middle empty spot, ArrayList should be slower than LinkedList. If insertion only means an add(Object) operation, how could this be slow?

解决方案

ArrayList is faster than LinkedList if I randomly access its elements. I think random access means "give me the nth element". Why ArrayList is faster?

ArrayList has direct references to every element in the list, so it can get the n-th element in constant time. LinkedList has to traverse the list from the beginning to get to the n-th element.

LinkedList is faster than ArrayList for deletion. I understand this one. ArrayList's slower since the internal backing-up array needs to be reallocated.

ArrayList is slower because it needs to copy part of the array in order to remove the slot that has become free. If the deletion is done using the ListIterator.remove() API, LinkedList just has to manipulate a couple of references; if the deletion is done by value or by index, LinkedList has to potentially scan the entire list first to find the element(s) to be deleted.

If it means move some elements back and then put the element in the middle empty spot, ArrayList should be slower.

Yes, this is what it means. ArrayList is indeed slower than LinkedList because it has to free up a slot in the middle of the array. This involves moving some references around and in the worst case reallocating the entire array. LinkedList just has to manipulate some references.

这篇关于ArrayList和LinkedList之间的性能差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！