我们在说「数组」的时候有多种不同的语境，因为不同的编程语言提供的数组类型和 API 是不一样的，所以开头先统一一下说辞，方便后面的讲解。

我认为暂且可以把「数组」分为两大类，一类是「静态数组」，一类是「动态数组」。

「静态数组」就是一块连续的内存空间，我们可以通过索引来访问这块内存空间中的元素，这才是数组的原始形态。

而「动态数组」是编程语言为了方便我们使用，在静态数组的基础上帮我们添加了一些常用的 API，比如 push, insert, remove 等等方法，这些 API 可以让我们更方便地操作数组元素，不用自己去写代码实现这些操作。

本章的内容就是带大家仅仅使用最原始的静态数组，自己实现一个动态数组，实现增删查改的常见 API。以后你在使用标准库提供的数据结构时，就知道它们的底层运行原理了。

有了动态数组，后面讲到的队列、栈、哈希表等复杂数据结构都会依赖它进行实现。

静态数组

静态数组在创建的时候就要确定数组的元素类型和元素数量。只有在 C++、Java、Golang 这类语言中才提供了创建静态数组的方式，类似 Python、JavaScript 这类语言并没有提供静态数组的定义方式。

静态数组的用法比较原始，实际软件开发中很少用到，写算法题也没必要用，我们一般直接用动态数组。但为了理解原理，在这里还是要讲解一下。

定义一个静态数组的方法如下：

// 定义一个大小为 10 的静态数组
int[] arr = new int[10];
// 使用索引赋值
arr[0] = 1;
arr[1] = 2;
// 使用索引取值
int a = arr[0];

就这，没有其他什么操作了。

拿 C++ 来举例吧，int arr[10] 这段代码到底做了什么事情呢？主要有这么几件事：

1、在内存中开辟了一段连续的内存空间，大小是 10 * sizeof(int) 字节。一个 int 在计算机内存中占 4 字节，也就是总共 40 字节。

2、定义了一个名为 arr 的数组指针，指向这段内存空间的首地址。

那么 arr[1] = 2 这段代码又做了什么事情呢？主要有这么几件事：

1、计算 arr 的首地址加上 1 * sizeof(int) 字节（4 字节）的偏移量，找到了内存空间中的第二个元素的首地址。

2、从这个地址开始的 4 个字节的内存空间中写入了整数 2

😸写给初学者

我记得以前刚上大学的时候要学 C 语言基础，有些同学就绕不清楚什么指针的数组，数组的指针，绕来绕去的。其实只要明白了上面这个简单的流程，一切就很清楚了。

1、为什么数组的索引从 0 开始？就是方便取地址。arr[0] 就是 arr 的首地址，从这个地址往后的 4 个字节存储着第一个元素的值；arr[1] 就是 arr 的首地址加上 1 * 4 字节，也就是第二个元素的首地址，这个地址往后的 4 个字节存储着第二个元素的值。arr[2], arr[3] 以此类推。

2、因为数组的名字 arr 就指向整块内存的首地址，所以数组名 arr 就是一个指针。你直接取这个地址的值，就是第一个元素的值。也就是说，*arr 的值就是 arr[0]，即第一个元素的值。

3、如果不用 memset 这种函数初始化数组的值，那么数组内的值是不确定的。因为 int arr[10] 这个语句只是请操作系统在内存中开辟了一块连续的内存空间，你也不知道这块空间是谁使用过的二手内存，你也不知道里面存了什么奇奇怪怪的东西。所以一般我们会用 memset 函数把这块内存空间的值初始化一下再使用。

当然，上面讲的这些内容都是针对 C/C++，因为大家学习计算机基础的时候都接触过。其他比如 Java Golang 这种语言，静态数组创建出来后会自动帮你把元素值都初始化为 0，所以不需要再显式进行初始化。

😀总结

我梳理一下上面的因果逻辑，静态数组本质上就是一块连续的内存空间，int arr[10] 这个语句我们可以得知：

1、我们知道这块内存空间的首地址（数组名 arr 就指向这块内存空间的首地址）。

2、我们知道了每个元素的类型（比如 int），也就是知道了每个元素占用的内存空间大小（比如一个 int 占 4 字节，32 bit）。

3、这块内存空间是连续的，其大小为 10 * sizeof(int) 即 40 字节。

所以，我们获得了数组的超能力「随机访问」：只要给定任何一个数组索引，我可以在 O(1)O(1) 的时间内直接获取到对应元素的值。

因为我可以通过首地址和索引直接计算出目标元素的内存地址。计算机的内存寻址时间可以认为是 O(1)O(1)，所以数组的随机访问时间复杂度是 O(1)O(1)。

但是，一个人最大的优势往往也是他的最大劣势。数组连续内存的特性给了他随机访问的超能力，但它也因此吃了不少苦，下面介绍。

增删改查

数据结构的职责就是增删查改，再无其他。

那么刚刚介绍数组这种数据结构的底层原理，我们其实只介绍了「查」和「改」的部分，也就是通过索引修改和访问对应元素的值。那么「增删」这两个操作又是如何实现的呢

增

要想给静态数组增加元素，这就有些复杂了，需要分情况讨论。

情况一，数组末尾追加（append）元素

比方说，我有一个大小为 10 的数组，里面装了 4 个元素，现在想在末尾追加一个元素，怎么办？

比较简单，直接在对应的索引赋值就行了，这是大概的代码逻辑：

// 大小为 10 的数组已经装了 4 个元素
int[] arr = new int[10];
for (int i = 0; i < 4; i++) {
    arr[i] = i;
}
// 现在想在数组末尾追加一个元素 4
arr[4] = 4;
// 再在数组末尾追加一个元素 5
arr[5] = 5;
// 依此类推
// ...

可以看到，由于只是对索引赋值，所以在数组末尾追加元素的时间复杂度是 O(1)。

情况二，数组中间插入（insert）元素

比方说，我有一个大小为 10 的数组 arr，前 4 个索引装了元素，现在想在第 3 个位置（arr[2]）插入一个新元素，怎么办？

这就要涉及「数据搬移」，给新元素腾出空位，然后再才能插入新元素。大概的代码逻辑是这样的

// 大小为 10 的数组已经装了 4 个元素
int[] arr = new int[10];
for (int i = 0; i < 4; i++) {
    arr[i] = i;
}
// 在第 3 个位置插入元素 666
// 需要把第 3 个位置及之后的元素都往后移动一位
// 注意要倒着遍历数组中已有元素避免覆盖，不懂的话请看下方可视化面板
for (int i = 4; i > 2; i--) {
    arr[i] = arr[i - 1];
}
// 现在第 3 个位置空出来了，可以插入新元素
arr[2] = 666;

综上，在数组中间插入元素的时间复杂度是 O(N)，因为涉及到数据搬移，给新元素腾地方。

情况三，数组空间已满

静态数组在创建时就要确定大小，比方说现在我创建了一个数组 int arr[10]（一块 40 字节的连续内存空间），然后往里面存了 10 个元素，这时候我想再插入一个元素，怎么办？无论是追加在尾部还是插入到中间，都没有位置留给新元素了。

有的读者可能说，这个简单呀，在这 40 字节后面再加上 4 个字节的连续内存空间，用来存储新的元素，不就行了吗？

不行的，连续内存必须一次性分配，分配完了之后就不能随意增减了。因为你这块连续内存后面的内存空间可能已经被其他程序占用了，不能说你想要就给你。

那怎么办呢？只能重新申请一块更大的内存空间，把原来的数据复制过去，再插入新的元素，这就是数组的「扩容」操作 [Java中已经帮我们做了自动的扩容]。

比方说，我重新创建一个更大的数组 int arr[20]，然后把原来的 10 个元素复制过去，这样就有空余位置插入新的元素了。

大概的逻辑是这样的：

// 大小为 10 的数组已经装满了
int[] arr = new int[10];
for (int i = 0; i < 10; i++) {
    arr[i] = i;
}
// 现在想在数组末尾追加一个元素 10
// 需要先扩容数组
int[] newArr = new int[20];
// 把原来的 10 个元素复制过去
for (int i = 0; i < 10; i++) {
    newArr[i] = arr[i];
}
// 旧数组的内存空间将由垃圾收集器处理
// ...
// 在新的大数组中追加新元素
newArr[10] = 10;

综上，数组的扩容操作会涉及到新数组的开辟和数据的复制，时间复杂度是 O(N)。

删

删除元素的操作和增加元素的操作类似，也需要分情况讨论。

情况一，删除末尾元素

比方说，我有一个大小为 10 的数组，里面装了 5 个元素，现在想删除末尾的元素，怎么办？

很简单，直接把末尾元素标记为一个特殊值代表已删除就行了，我们这里简单举例，就用 -1 作为特殊值代表已删除好了。后面带大家具体实现动态数组的时候，会有更完善的方法删除数组元素，这里只是为了说明删除数组尾部元素的本质就是进行一次随机访问，时间复杂度是 O(1)。

大概的代码逻辑是这样的：

// 大小为 10 的数组已经装了 5 个元素
int[] arr = new int[10];
for (int i = 0; i < 5; i++) {
    arr[i] = i;
}
// 删除末尾元素，暂时用 -1 代表元素已删除
arr[4] = -1;

情况二，删除中间元素

比方说，我有一个大小为 10 的数组，里面装了 5 个元素，现在想删除第 2 个元素（arr[1]），怎么办？这也要涉及「数据搬移」，把被删元素后面的元素都往前移动一位，保持数组元素的连续性。

大概的代码逻辑是这样的：

// 大小为 10 的数组已经装了 5 个元素
int[] arr = new int[10];
for (int i = 0; i < 5; i++) {
    arr[i] = i;
}
// 删除 arr[1]
// 需要把 arr[1] 之后的元素都往前移动一位
// 注意要正着遍历数组中已有元素避免覆盖，不懂的话请看下方可视化面板
for (int i = 1; i < 4; i++) {
    arr[i] = arr[i + 1];
}
// 最后一个元素置为 -1 代表已删除
arr[4] = -1;

综上，在数组中间删除元素的时间复杂度是 O(N)，因为涉及到数据搬移

总结

综上，静态数组的增删查改操作的时间复杂度是：

• 增：

• 在末尾追加元素：O(1)
• 在中间（非末尾）插入元素：O(N)

• 删：

• 删除末尾元素：O(1)
• 删除中间（非末尾）元素：O(N)

• 查：给定指定索引，查询索引对应的元素的值，时间复杂度 O(1)
• 改：给定指定索引，修改索引对应的元素的值，时间复杂度 O(1)

还有个问题初学者要注意：我们说数组的查、改复杂度是 O(1)，这个仅适用于给定索引的情况。如果反过来，如给你一个值，让你去找这个值在数组中对应的索引，那你只能遍历整个数组去寻找对吧，这个复杂度就是 O(N)了。所以说要搞清楚原理，而不要去背概念。原理懂了，概念你自己都能推导出来的

动态数组

刚才讲了静态数组的超能力和种种局限性，现在讲动态数组，动态数组是静态数组的强化版，也是我们在实际软件开发或者写算法题时最常用的数据结构之一。

首先，你不要以为动态数组可以解决静态数组在中间增删元素效率差的问题，不可能解决的。数组随机访问的超能力源于数组连续的内存空间，而连续的内存空间就不可避免地面对数据搬移和扩缩容的问题。

动态数组底层还是静态数组，只是自动帮我们进行数组空间的扩缩容，并把增删查改操作进行了封装，让我们使用起来更方便而已。

简单列举一下动态数组使用方法

// 创建动态数组
// 不用显式指定数组大小，它会根据实际存储的元素数量自动扩缩容
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 0; i < 10; i++) {
    // 在末尾追加元素，时间复杂度 O(1)
    arr.add(i);
}
// 在中间插入元素，时间复杂度 O(N)
// 在索引 2 的位置插入元素 666
arr.add(2, 666);
// 在头部插入元素，时间复杂度 O(N)
arr.add(0, -1);
// 删除末尾元素，时间复杂度 O(1)
arr.remove(arr.size() - 1);
// 删除中间元素，时间复杂度 O(N)
// 删除索引 2 的元素
arr.remove(2);
// 根据索引查询元素，时间复杂度 O(1)
int a = arr.get(0);
// 根据索引修改元素，时间复杂度 O(1)
arr.set(0, 100);
// 根据元素值查找索引，时间复杂度 O(N)
int index = arr.indexOf(666);