在ArrayList的开头添加元素的时间复杂度是多少？

假设我在这个数组中有一个带有n个元素的ArrayList，我在开头添加了一个元素：

myArrayList.add(0,'some value'); 

这次行动的时间复杂程度是多少？

Java Doc没有指定这一点。

也

我刚开始学习Java，我看到了句子

 An ArrayList in Java is a List that is backed by an array. 

这里’支持’是什么意思？ 谢谢！

Answer 1

将元素添加到数组的开头是O（n） – 它需要将所有现有元素移位一个位置。

数组列表中的所有元素都存储在一个连续的数组中。 如果添加的元素多于数组的当前大小 – 它将自动生成以适应新元素。

最后，O（1）在多次插入时摊销。

Answer 2

ArrayList.add(0, element)占用线性时间，但常量非常低，因为它可以使用超快的System.arraycopy 。

Answer 3

• 从头开始构建列表并在开头添加大量元素以二次时间运行：O（n ² ）。
• 将所有元素添加到列表末尾然后调用Collections.reverse（list）以线性时间运行：O（n）。