在arrayList的某个索引处插入元素的运行时间是多少？

Question

我想知道add(index,E)java方法的运行时间是多少ArrayList.根据javadoc,add操作的运行时间是摊销的O(1).但在add(index,E)的描述中,它说明了这一点.

将指定元素插入此列表中的指定位置.将当前位于该位置的元素(如果有)和任何后续元素向右移动(向其索引添加一个元素).

所以它看起来像O(N).我想知道我们要交易什么,如果这个操作的运行时间是这样的话O(1).是否有任何摊销工作可以进行此操作O(1)并牺牲其他操作的运行时间？

我读过java ArrayList是由数组支持的,会改变数据结构的帮助吗？

Answer 1

ArrayList对于添加/删除的任意索引，时间复杂度为 O(n)，但对于列表末尾的操作，时间复杂度为 O(1)。更接近O(1) 的查找意味着可能类似于哈希表支持的数据结构，其中索引作为键，元素作为值。再次插入将花费 O(n) 时间，因为它会触发调整大小。