数组的插入、删除
在数组存储结构中，由于元素间紧密排列，插入和删除元素时需要保证排列方式维持原状。因此在插入和删除元素时，数组中已有元素的位置要随之进行调整。
算法
插入
需重新分配
动态的数组结构通常在末尾预留空间以保证可以继续插入元素。如果预留空间耗尽，需要重新分配数组空间以保证末尾可以使用，此时需要将旧内存上的元素对应移动到新内存区域中。
不需重新分配
如果空间足够，数组存储结构插入时要保证元素继续保持连续。因此插入新的元素时：
- 如果数组需要标记长度或尾部位置，长度加一，尾部位置向后移动一个位置。
- （如果元素不是要被插入最后的位置）需要将插入位置后续的元素都向右移动一个位置。
- 将新元素插入腾出来的空位上。
这一算法时间复杂度渐近于与需要移动的部分，也就是正比于插入点后的部分，平均情况下即正比于数组长度，线性时间。
特别地，数组的尾部插入不涉及移动步骤，是一个常数时间操作。
删除
删除算法和有空间时的插入算法相反：将所有后续元素向前移动，覆盖掉被删除元素的位置。因此也需要线性时间。
- 释放要删除的元素。
- （如果指定的不是最后一个元素）把后续元素都向前一个位置。
- 如果数组需要标记长度或尾部位置，长度减一，尾部位置向前移动一个位置。
特别地，数组的尾部删除不涉及移动步骤，是一个常数时间操作。