arrays - 为什么在动态数组末尾插入是 O(1)，而在中间插入是 O(n)？

Question

根据维基百科文章dynamic arrays ，在数组末尾插入/删除是 O(1)，而从中间插入/删除是 O(n)。到底为什么会这样？

另外 - 如果我有一个包含 5 个元素的动态数组，并且在位置 6 处插入一个新元素，则操作为 O(n)，而如果我使用该函数附加到数组末尾，则为 O(1) 。假设在任何一种情况下数组都不需要调整大小，这不是相同的操作吗？或者追加到动态数组中真的会在位置 6 之外的某个位置插入新元素吗？

谢谢!

编辑:我认为我的主要困惑是在数组末尾插入和在相当于数组末尾的特定位置插入之间的区别。

我认为指向数组末尾的内存地址的指针放在方便的地方，这就是追加操作很快的原因。相反，如果我指定一个精确的位置(即使它是数组的末尾)，它不会知道在该位置插入相当于使用前面提到的内存地址，因此它必须遍历整个数组，是吗？ p>

Answer 1

要在数组末尾插入，您只需将项目放在那里即可。

要插入数组的中间，您需要将该点之后的项目向上移动一位。

要从数组末尾删除，只需将其计数减一即可。

要从中间删除，您必须执行此操作，并将其他项目向下移动。

正是移位将其变成了 O(n)。