在List interface的Collection框架教程中,有一个关于从List实现中删除元素的性能的有趣引用:
对于许多常见的List实现,例如ArrayList,从列表末尾删除元素的性能明显优于从头开始删除元素的性能。
这些教程没有进一步解释这一点,我试图弄清楚为什么会这样。
考虑如下ArrayList<Integer> list
:
在第一种情况下,如果我们从list
的末尾删除最后4个元素,那么这些元素的值将设置为null
(或等效值)。我的理论是,当需要复制操作时,只复制不是null
的元素。
在第二种情况下,如果我们删除前4个元素,它们将被再次设置为null
,并且只会复制非null
元素。
所以从这个角度看,表演看起来差不多了。如果从最后执行操作更快,还有另一个原因吗?
另一方面,对于LinkedList
,反过来似乎是正确的;从开头删除更快,而从末端删除需要几乎完全遍历,除非保留tail-pointer
。
除了将元素设置为null
之外,还需要从列表开头删除元素。您还需要移动剩余的元素以填充空出的位置。
可以使用变量来跟踪列表的“开头”而不移动元素,但是由于数组中未使用的元素,您将牺牲内存效率。
根据我的理解,ArrayList是列表的数组实现。因此,如果从数组的开头删除元素,则需要移动所有剩余元素以填充已删除的元素。所以这基本上是一个O(n-1)操作。但是当你从列表末尾删除元素时不是这种情况。这将是O(1)。
在ArrayList<>
从开始删除是缓慢的,因为整个数组将不得不被移位,因为添加函数add
元素在,如果我们离开开始为空,那么我们将浪费内存。
如果我们考虑big(O)
符号从开始删除基本上线性时间O(n)
,而从末尾删除是恒定时间O(1)
。
虽然Code-Apprentice的答案是正确的,但我想详细说明如何通过进行基于索引的查找来验证每个条目向左移动的行为,即调用list.get(index)
。
要验证的代码:
List<String> list = new ArrayList<>();
list.add("0");
list.add("1");
list.remove(0);
String entry0 = list.get(0);
System.out.println(entry0);
您怀疑会打印null
,但会打印“1”。这确认了所有元素都向左移动。
NB。我使用字符串来避免remove(int index)
和remove(Object o)
引起的混乱。