根据维基百科关于动态数组的文章,在数组末尾插入/删除是 O(1),而从中间插入/删除是 O(n)。为什么会这样?
另外 - 如果我有一个包含 5 个元素的动态数组,并且我在位置 6 插入一个新元素,则操作为 O(n),而如果我使用该函数附加到数组的末尾,则为 O(1)。假设数组在任何一种情况下都不需要调整大小,这不是相同的操作吗?或者附加到动态数组是否真的在位置 6 之外的某个地方插入了新元素?
谢谢!
编辑:我认为我的主要困惑是在数组末尾插入和在相当于数组末尾的特定位置插入之间的区别。
我想指向数组末尾的内存地址的指针很方便,这就是附加操作很快的原因。相反,如果我指定一个精确的位置(即使它是数组的末尾),它不会知道在那个位置插入就等于使用上述内存地址,所以它必须遍历整个数组,是吗?