在ArrayList的开头添加元素的时间复杂度是多少？ [英] What is the time complexity of adding an element at the beginning of an ArrayList?

问题描述

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

Say I have a ArrayList with n element in this array, and I add an element at the beginning:

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

此操作的时间复杂度是多少？

What will be the time complexity of this operation?

Java Doc 未指定此内容。

另外

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

I just start learning Java, and I saw the sentence

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

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

What does 'backed' here mean? Thank you!

推荐答案

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

Adding an element to beginning of array is O(n) - it would require to shift all the existing elements by one position.

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

All elements in an array list are stored in a contiguous array. If you add more elements than the current size of the array - it will be grown automatically to accommodate the new element.

除了结尾是O（1）摊销多次插入。

Addition to the end is O(1) amortized over multiple insertions.

这篇关于在ArrayList的开头添加元素的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！