我们在说「数组」的时候有多种不同的语境，因为不同的编程语言提供的数组类型和 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)。
