Java:ArrayList add()和remove()性能,实现？

Question

我已经读过某个地方,ArrayList的add()和remove()操作在"amortized constant"时间内运行.这究竟是什么意思？

在add(item)的实现中,我可以看到它ArrayList使用的数组缓冲区最多是list't大小的3/2,如果它已满,则调用System.arraycopy(),它应该执行在O(n)中,而不是O(1)时间.那么System.arraycopy是否尝试做一些比将元素逐个复制到新创建的数组更聪明的事情,因为时间实际上是O(1)？

---

结论:add(item)以分摊的常量时间运行,但add(item,index)和remove(index)不运行,它们以线性时间运行(如答案中所述).

Answer 1

我已经读过某个地方,ArrayList的add()和remove()操作在"amortized constant"时间内运行.

remove()除非在特殊情况下,我不认为这是真的.

• 一remove(Object)为平均随机元素调用必须调用equals列表中的条目的一半,然后复制另一半的引用.

• 一remove(int)为平均随机元素调用有复制的元素的一半引用.

其中唯一的情况下,remove(...)将是O(1)对平均值(例如摊销)是当您使用remove(int)删除元素一些常数从列表的末尾偏移.