查看“︁数组的插入、删除”︁的源代码

[[分类:数组]]
在[[顺序表]]存储结构中，由于元素间紧密排列，插入和删除元素时需要保证排列方式维持原状。因此在插入和删除元素时，数组中已有元素的位置要随之进行调整。
这一算法适用于[[动态数组]]和有结束标记的[[静态数组]]。

== 算法 ==

=== 插入 ===

==== 需重新分配 ====

动态的数组结构通常在末尾预留空间以保证可以继续插入元素。如果预留空间耗尽，需要重新分配数组空间以保证末尾可以使用，此时需要将旧内存上的元素对应移动到新内存区域中。

{{GiteaSvg|array_insert_realloc}}

==== 不需重新分配 ====

如果空间足够，数组存储结构插入时要保证元素继续保持连续。因此插入新的元素时：

# 如果数组需要标记长度或尾部位置，长度加一，尾部位置向后移动一个位置。
# （如果元素不是要被插入最后的位置）需要将插入位置后续的元素都向右移动一个位置。
# 将新元素插入腾出来的空位上。

这一算法时间复杂度渐近于与需要移动的部分，也就是正比于插入点后的部分，平均情况下即正比于数组长度，[[线性时间]]。

{{GiteaSvg|array_insert_in_place}}

特别地，数组的尾部插入不涉及移动步骤，是一个[[常数时间]]操作。

=== 删除 ===

删除算法和有空间时的插入算法相反：将所有后续元素向前移动，覆盖掉被删除元素的位置。因此也需要线性时间。

# [[释放]]要删除的元素。
# （如果指定的不是最后一个元素）把后续元素都向前一个位置。
# 如果数组需要标记长度或尾部位置，长度减一，尾部位置向前移动一个位置。

{{GiteaSvg|array_erase}}

特别地，数组的尾部删除不涉及移动步骤，是一个常数时间操作。