ArrayList：在指定元素处插入与插入

Question

考虑一个数组列表。在内部它是不完整的，到目前为止插入的元素数量是已知的。元素未排序。无论 ArrayList 中包含的元素数量如何，都可以选择下面列出的快速操作。（换句话说，只需几条指令即可实现）。

插入

在给定索引处插入

从指定索引获取数据

查找整数数组中的最大值（不一定排序）

在给定索引处删除

替换指定索引处的元素

正在搜索特定元素

我选择了 Insertion at specified index，Getting the data from a specified index，并替换了一个元素，但答案是插入。按照我通常的理解，在一个ArrayList中，插入操作需要所有的元素都左移。如果我们在列表的开头这样做，我们将有 $O(n)$ 的时间复杂度。但是，如果我们在最后这样做，它将是 $O(1)$。

我的问题归结为：(1) 插入和在指定索引处插入之间有什么区别（如果有的话），以及 (2) 考虑到插入的这个特定时间复杂度，为什么要考虑 "fast"

Answer 1

第一个问题的答案是：

在指定索引 i 处插入需要 O(n)，因为 i 之后的所有元素都必须向右移动一个位置。
另一方面，在 Java (ArrayList.add()) 中实现的简单插入将只需要 O(1)，因为元素附加到数组的末尾，所以没有移位是必需的。

对于第二个问题，很明显简单插入为什么很快：不需要额外的操作，所以时间是常数。

Answer 2

(1) what, if any, difference is there between insertion and insertion at specified index and

ArrayList 连续存储它的元素。添加到 ArrayList 的末尾不需要以任何方式更改 ArrayList，除非将新元素添加到其自身的末尾。因此，这个操作是 O(1)，需要常数时间，这在想要在数据结构中重复执行一个动作时是有利的。

但是，将元素添加到索引需要 ArrayList 以某种方式为元素腾出空间。这是怎么做到的？插入元素之后的每个元素都必须移动一步以为新插入腾出空间。您的索引是第一个元素和第 n 个元素（包括）之间的任何内容。因此，此操作充其量为 O(1)，最差为 O(n)，其中 n 是数组的大小。对于大型列表，O(n) 比 O(1) 花费更长的时间。

(2) given this particular time complexity for insertion why is it considered "fast"

它被认为是快速的，因为它是 O(1) 或常数时间。如果时间复杂度真的只是一个操作，它尽可能快，其他小常量也被认为是快速的并且通常同样记为O（1），其中“1”并不意味着严格的单个操作，但是操作的数量不依赖于其他东西的大小，在你的例子中它将是 ArrayList 的大小。然而，恒定时间复杂度也可能涉及大常数，但通常被认为是尽可能快的时间复杂度。为了说明这一点，O(1) 操作在具有 1000 个元素的 ArrayList 中大约需要 1 * k 个操作，而 O(n) 操作大约需要 1000 * k 个操作，其中 k 是某个常数。

Big-O 表示法用作衡量一个动作或整个程序在运行时将执行多少操作的度量标准。

有关大 O 表示法的更多信息： What is a plain English explanation of "Big O" notation?

Answer 3

先看看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).
在第二种方法中，当您指定索引时，该索引之后的所有元素都会被移动，这肯定比前者花费更多的时间。

Answer 4

ArrayList 在内部不过是一个数组本身，它使用 Array.copyOf 创建一个新的数组，在添加时增加了大小，但原始内容完好无损。所以关于插入，无论你是做一个简单的添加（这将在数组的末尾添加数据）还是在第一个（第 0 个）索引上，它仍然比大多数数据结构更快，记住简单性数据结构。

唯一的区别是简单的加法不需要遍历，但在索引处加法需要将元素向左移动，删除也类似。它使用 System.arrayCopy 将一个数组复制到另一个数组，并更改索引和数据。

所以，是的，简单插入比索引插入更快。

ArrayList：在指定元素处插入与插入

ArrayList: insertion vs insertion at specified element

java

arraylist

data-structures

abstract-data-type