ArrayList：在指定元素处插入vs插入(ArrayList: insertion vs insertion at specified element)

ArrayList：在指定元素处插入vs插入(ArrayList: insertion vs insertion at specified element)

考虑一个Arraylist。 在内部它不是满的，到目前为止插入的元素的数量是已知的。 元素没有排序。 无论ArrayList中包含的元素的数量如何，请选择快速列出的操作。 （换句话说，只需要执行几条指令）。

插入

在给定索引处插入

从指定的索引获取数据

在整数数组中寻找最大值（不一定排序）

在给定索引处删除

替换指定索引处的元素

搜索特定元素

我在指定索引处选择插入，从指定索引获取数据，并替换元素，但答案键为插入。 正如我通常理解的那样，在ArrayList中，插入操作要求所有元素向左移动。 如果我们在列表的开始处这样做，我们将具有$ O（n）$时间复杂性。 但是，如果我们最终做到了，那将是$ O（1）$。

我的问题归结为：（1）在指定索引处的插入和插入之间存在什么区别，以及（2）针对插入给出了这个特定时间复杂度，为什么它被认为是“快速”

Consider an Arraylist. Internally it is not full, and the number of elements inserted so far is known. The elements are not sorted. Choose the operations listed below that are fast regardless of the number of elements contained in the ArrayList. (In other words, takes only several instructions to implement).

Insertion

Insertion at a given index

Getting the data from a specified index

Finding the maximum value in an array of integers (not necessarily sorted)

Deletion at the given index

Replacing an element at a specified index

Searching for a specific element

I chose Insertion at specified index, Getting the data from a specified index, and replacing an element but answer key says Insertion. As I usually understand it, in an ArrayList, the insert operation requires all of the elements to shift left. If we did this at the beginning of the list, we would have $O(n)$ time complexity. However, if we did it at the end, it would be $O(1)$.

My question comes down to: (1) what, if any, difference is there between insertion and insertion at specified index and (2) given this particular time complexity for insertion why is it considered "fast"

最满意答案

首先看看java.util.ArrayList定义的这两个方法

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } 现在如果你看到第一个方法（只是添加元素），它只是确保是否有足够的容量并将元素添加到列表的最后。 所以如果有足够的容量，那么这个操作需要O(1)时间复杂度，否则就需要移动所有元素，最终时间复杂度增加到O(n) 。 在第二种方法中，当你指定索引时，索引之后的所有元素都将被移位，这肯定会比前一个更耗时。

First take a look at these two methods defined in java.util.ArrayList

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } Now if you see the first method (just adding element), it just ensures whether there's sufficient capacity and appends element to the last of the list. So if there's sufficient capacity, then this operation would require O(1) time complexity, otherwise it would require shifting of all elements and ultimately time complexity increases to O(n). In the second method, when you specify index, all the elements after that index would be shifted and this would definitely take more time then former.