数组（顺序存储）基本原理
我们在说「数组」的时候有多种不同的语境，因为不同的编程语言提供的数组类型和 API 是不一样的，所以开头先统一一下说辞，方便后面的讲解。
我认为暂且可以把「数组」分为两大类，一类是「静态数组」，一类是「动态数组」。
「静态数组」就是一块连续的内存空间，我们可以通过索引来访问这块内存空间中的元素，这才是数组的原始形态。
而「动态数组」是编程语言为了方便我们使用，在静态数组的基础上帮我们添加了一些常用的 API，比如 push, insert, remove 等等方法，这些 API 可以让我们更方便地操作数组元素，不用自己去写代码实现这些操作。
本章的内容就是带大家仅仅使用最原始的静态数组，自己实现一个动态数组，实现增删查改的常见 API。以后你在使用标准库提供的数据结构时，就知道它们的底层运行原理了。
有了动态数组，后面讲到的队列、栈、哈希表等复杂数据结构都会依赖它进行实现。
静态数组
静态数组在创建的时候就要确定数组的元素类型和元素数量。只有在 C++、Java、Golang 这类语言中才提供了创建静态数组的方式，类似 Python、JavaScript 这类语言并没有提供静态数组的定义方式。
静态数组的用法比较原始，实际软件开发中很少用到，写算法题也没必要用，我们一般直接用动态数组。但为了理解原理，在这里还是要讲解一下。
定义一个静态数组的方法如下：
就这，没有其他什么操作了。
拿 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)。
但是，一个人最大的优势往往也是他的最大劣势。数组连续内存的特性给了他随机访问的超能力，但它也因此吃了不少苦，下面介绍。
增删改查
