数组的插入与删除
数组是数据结构中最简单的结构，很多编程语言都内置数组。数组是有限个相同类型的变量所组成的集合，数组中的每一个变量被称为元素。
创建数组时会在内存中划分出一块连续的内存，将数据按顺序进行存储，数组中的每一个元素都有着自己的下标（index），下标从 0 开始。
对于数组来说，读取元素是最简单的操作。由于数组在内存中顺序存储，所以只要给出数组的下标，就可以读取到对应位置的元素。像这种根据下标读取元素的方式叫作随机读取。数组读取元素的时间复杂度是 。
知识测验
题目
数组能够在 O(1) 时间内访问任意下标，最关键的原因是什么？
数组的劣势体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。总的来说，数组所适合的是读操作多、写操作少的场景。
插入元素
在数组中插入元素存在 3 种情况：
- 尾部插入：直接把插入的元素放在数组尾部的空闲位置即可。
- 中间插入：首先把插入位置及后面的元素向后移动，腾出位置，再把要插入的元素放入该位置上。
- 扩容：数组的长度在创建时就已经确定了，要实现数组的扩容，只能创建一个新数组，长度是旧数组的 2 倍，再把旧数组中的元素全部复制过去。
互动实验
可视化数组插入
访问权限免费
选择插入位置。新值进入空位之前，已有元素会从后向前逐个右移。
0
1
2
3
4
5
6
7
12
24
36
48
斜纹单元格是尚未使用的容量。
数组插入元素最好情况是尾部插入，无需移动任何元素，时间复杂度为 。最坏情况是在第一个位置插入，这样就需要移动后面所有 个元素，时间复杂度为 。
知识测验
题目
一个长度为 n 且仍有空余容量的数组，在下标 0 插入元素需要移动多少个已有元素？
C
array_t *array_add(array_t *arr, T elem) {
if (arr == NULL) {
return NULL;
}
if (arr->size == arr->capacity) {
arr = resize(arr);
}
arr->data[arr->size++] = elem;
return arr;
}
array_t *array_insert(array_t *arr, int index, T elem) {
if (arr == NULL) {
return NULL;
}
if (index < 0 || index > arr->size) {
fprintf(stderr, "Error: index out of bound.\n");
return arr;
}
if (arr->size == arr->capacity) {
arr = resize(arr);
}
for (int i = arr->size - 1; i >= index; i--) {
arr->data[i + 1] = arr->data[i];
}
arr->data[index] = elem;
arr->size++;
return arr;
}删除元素
数组的删除操作与插入操作过程相反，如果被删除的元素位于数组中间，其后的元素都需要向前挪动一位。
互动实验
可视化数组删除
访问权限免费
选择删除位置。目标元素移除后，后续元素会逐个左移，使已使用区域仍然连续。
10
020
130
240
350
460
5·
6·
7选择位置，比较不同删除操作需要移动多少元素。
知识测验
题目
长度为 10 的数组删除下标 6 的元素后，为保持连续需要移动多少个元素？
C
T array_remove(array_t *arr, int index) {
if (arr == NULL) {
exit(1);
}
if (index < 0 || index >= arr->size) {
fprintf(stderr, "Error: index out of bound.\n");
exit(1);
}
T elem = arr->data[index];
for (int i = index; i < arr->size - 1; i++) {
arr->data[i] = arr->data[i + 1];
}
arr->size--;
return elem;
}数组的删除操作，由于涉及元素的移动，时间复杂度为 。