数据结构 - 数组
简介
数组本质上是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表
如上图所示，线性表就是数据排成一条线一样的结构，因此每个线性表中的数据只有前后两个方向。像数组、链表、栈、队列都是线性表结构。
与线性表对应的就是非线性表结构，非线性表中的数据会存在多个方向，数据之间不是简单的前后关系。像树、堆都是非线性表结构。
连续的内存空间
数组存储使用的内存空间是连续的，在数组存储的这一片空间只会存储数组元素，不会再拆分出来存储其他的数据。
相同类型的数据
在数组的原始定义中，数组只能存储相同类型的数据，这样可以保证数组中每个元素占用的内存空间都能保持一致。
正是数组存在“连续的内存空间”和“相同类型的数据”这两个限制，才让它拥有了随机存取这个高效的特性，但同时也使得数组在插入、删除数据的时候会比较低效。
数组的特性
就数组增删改查的操作而言，数组拥有高效随机存取的特性，也存在低效插入、删除的劣势。
随机存取
这里的“随机存取”指的的是通过下标访问数组元素，然后对这个元素做存取操作。
计算机会给每个内存单元分配一个地址，然后通过地址来访问内存中的数据。当计算机需要随机访问数组中的数据时，它可以通过下面的寻址公式来计算出对应下标的内存地址：
address[i] = base_address + data_type_size * i
其中 base_address 表示数组的起始地址，data_type_size 表示每个元素占用的空间大小。
可想而知，同时具有“连续的内存空间”和“相同类型的数据”两个限制的数组结构，通过下标查找数组中的元素能达到 \(O(1)\) 的时间复杂度。
插入、删除
同随机存储的高效不同，对一个数组做插入、删除操作是非常低效的。这里的低效体现在插入和删除元素之后，需要对数组中的其他元素做搬移操作，以保证数组元素的连续性。
在一个长度为 n 的数组中，假如要在第 k 个位置插入一个元素，这不是修改元素的操作，不能直接替换掉第 k 个元素，而是需要依次将第 k 个及之后的元素都往后挪一位，然后才能在第 k 个位置上存入这个元素。
数组删除元素时和插入元素类似，为了避免删除元素之后导致数组中间出现空洞，需要将删除位置之后的元素往前挪一位。
通过计算得知，插入、删除的最好时间复杂度为 \(O(1)\)、最坏时间复杂度为 \(O(n)\)，平均时间复杂度为 \(O(n)\)。
使用上的问题
数组越界
数组可以通过寻址公式做到高效随机访问，但这并没有限制使用超出数组长度的下标访问数组，通常把访问的数组下标超出数组长度的情况称为数组越界。
在 C 语言中，编译器不会检测出数组越界的问题，如果出现数组越界的情况而又没处理的话，极可能出现如代码进入死循环等不可预知的情况。
int main(int argc, char* argv[]){
int i = 0;
int arr[3] = {0};
for(; i<=3; i++){
arr[i] = 0;
printf("hello world\n");
}
return 0;
}
如上述代码，在字节对齐和分配内存的特性下，先后定义了 i 和 arr 共占据了 8 个字节，表现为 {arr[0], arr[1], arr[2], i} 的形式，当循环到下标为 3 时，实际 arr[3] 指向的就是 i 所在地址，也就出现 arr[3] = i = 3，出现死循环。
相比较下，使用 Java 会更加安全，Java 不会把检查数组越界的工作丢给程序员来做，其本身就会做越界检查，如果出现错误则会抛出 域名yIndexOutOfBoundsException 异常，而不是出现死循环。
容器和数组的选择
这里说的容器指的是封装了数组的操作方法、并且支持动态扩容的容器类，比如 Java 中的 ArrayList 类。
与原生数组相比，ArrayList 拥有非常大的优势，但并不是所有地方都必须使用 ArrayList 而不使用数组，在某些地方使用数组更方便、效率更高。以下情况可以选择原生数组：
- 追求极致性能选择原生数组。Java 的
ArrayList不支持存储基本类型，而是存储基本类型封装后的对象，自动装箱、拆箱会有一定的性能消耗 - 操作简单，仅使用原生功能选择原生数组。虽然
ArrayList提供了非常多额外的功能，但也额外增加了风险，使用原生数组更简单便捷
为什么数组从 0 开始编号
这个问题可以通过数组的寻址公式来回答。
首先需要重新定义数组下标：下标不是只数组的第几个元素，而是指数组元素的偏移。
在使用时，使用 0 作为起始下标，数组使用下述的表达式作为寻址公式：
address[i] = base_address + data_type_size * i
如果使用 1 作为起始下标，将不能直接使用上面的寻址公式，而是需要修改如下：
address[i] = base_address + data_type_size * (i - 1)
在对比前后两个寻址公式之后，可以发现，使用 1 作为起始下标的寻址公式会比使用 0 作为起始下标的寻址公式多一个简单的减法指令。
对于非常底层的程序来说，即使只是多出一个简单的减法指令，也是一种性能的损耗，为了做到极致优化，选择 0 作为起始下标会更好。
当然还有一个历史原因，C 语言使用了 0 作为数组的起始下标，后续 Java、JavaScript 都纷纷仿效，这也算是为了统一，降低程序员的学习成本。
