ArrayList 和 LinkedList 之间的性能差异 [英] Performance differences between ArrayList and LinkedList
问题描述
是的，这是一个老话题，但我仍然有些困惑.
Yes, this is an old topic, but I still have some confusions.
在 Java 中，人们说:
In Java, people say:
如果我随机访问它的元素，ArrayList 比 LinkedList 快.我认为随机访问意味着给我第 n 个元素".为什么 ArrayList 更快?
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?
LinkedList 的删除速度比 ArrayList 快.我明白这一点.ArrayList 较慢，因为需要重新分配内部备份数组.一段代码说明:
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"
LinkedList 在插入方面比 ArrayList 快.这里插入是什么意思?如果意味着将一些元素移回，然后将元素放在中间的空白位置，则 ArrayList 应该比 LinkedList 慢.如果插入仅意味着 add(Object) 操作，这怎么可能很慢?
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 比 LinkedList 快.我认为随机访问意味着给我第 n 个元素".为什么 ArrayList 更快?
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 直接引用列表中的每个元素，因此可以在恒定时间内获取第 n 个元素.LinkedList 必须从头开始遍历列表才能到达第 n 个元素.
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 的删除速度比 ArrayList 快.我明白这一点.ArrayList 较慢，因为需要重新分配内部备份数组.
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 速度较慢，因为它需要复制部分数组以移除空闲的插槽.如果删除是使用 ListIterator.remove() API，LinkedList 只需要操作几个引用；如果删除是按值或按索引完成的，LinkedList 必须首先扫描整个列表以找到要删除的元素.
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.
如果这意味着将一些元素向后移动，然后将元素放在中间的空白处，ArrayList 应该更慢.
If it means move some elements back and then put the element in the middle empty spot, ArrayList should be slower.
是的，就是这个意思.ArrayList 确实比 LinkedList 慢，因为它必须在数组中间释放一个槽.这涉及移动一些引用，在最坏的情况下重新分配整个数组.LinkedList 只需要操作一些引用.
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屋！
