数据结构学习 2–数组
数据结构学习系列第二篇–数组
数组
数组是一个最基础而且常见的数据结构，几乎每种编程语言都有。
如何实现随机访问
数组的定义：
数组(Array)是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
这里指出了数组的三个特点：
- 线性表(Linear List)
- 连续的内存空间
- 存储相同类型数据
首先，线性表就是数据排成一条线一样的结构，每个线性表最多只有前后两个方向，线性表结构如下图所示，数组、链表、队列和栈都属于这种结构。
和线性表对立的就是非线性表，比如二叉树、堆、图等，它们不仅仅是简单的前后关系，如下图所示：
接着就是需要连续内存空间和保存相同类型的数据。这两个特点让数组有一个非常好的特性：随机访问。也就是根据下标访问数组的时间复杂度是 O(1) ，但问题就是插入和删除需要 O(n)，因为需要进行大量的数据移动操作。
那么数组是如何实现随机访问的操作的呢？
首先，给定一个长度为 10 的 int 类型的数组 a[10] ，计算机会分配一块存储空间，这里假设就是 1000~1039 ，其中内存块的首地址是 base_address=1000，如下图所示
计算机给每个内存单元分配一个地址，然后通过地址访问内存中的数据。因此，这里如果需要随机访问数组的某个元素，同样也是根据地址访问，也就是首先需要找到该元素存储所在的地址，寻址公式如下所示：
a[i]_address = base_address + i * data_type_size
data_type_size 表示数组每个元素的大小，这里 int 类型是 4 个字节。
注意，对于数组来说，它支持随机访问，根据下标随机访问的时间复杂度是 O(1) ，但查找时间复杂度并非是 O(1) , 因为即便排好序的数值，通过二分查找，时间复杂度是 O(logn) 。
低效的插入和删除
数组的插入和删除操作由于其内存数据的连续性问题，这两个操作会非常低效，那么为什么会导致低效，有哪些改进方法呢？
插入操作
假设数组长度是 n ，现在需要将一个数据插入到数组的第 k 位置，如果需要执行这样的操作，需要将第 k 到 n 位置上的元素都按顺序往后移动一位。这个操作的时间复杂度是多少呢？
最好的情况，就是末尾插入元素，这样不需要移动，O(1) 复杂度；最坏的情况，数组开头就插入元素，那么就是 O(n) 的时间复杂度。平均情况时间复杂度则如下所示，每个位置插入元素概率是相同的：
$$
\frac{1+2+\cdots+n}{n}=O(n)
$$
当然，如果数组是有序的，就需要按照上述做法移动元素。如果数组无序呢，一个快速的方法就是仅移动目标位置的元素，即第 k 个位置的元素放到数组末尾，然后插入元素即可，这样时间复杂度就是 O(1)。
一个简单的例子如下图所示，数组有 5 个元素：a,b,c,d,e，现在希望在第三个位置插入新元素 x，此时可以直接将 c 放到末尾，即 a[5] = a[2]，然后 a[2]=x，即可完成操作。
这种特殊的处理技巧，可以在特定场景下(比如数组无序)将插入元素的时间复杂度降到 O(1)。
删除操作
和插入数据类似，删除第 k 个位置元素，同样需要将后续的元素往前移动。
- 最好的情况是删除末尾数据，
O(1)； - 最坏就是删除开头的元素，
O(n)； - 平均情况时间复杂度也是
O(n)。
同样在某些特定场景下，并不需要时刻追求数组中数组的连续性，可以将多次删除操作集中在一起进行操作。
如下图所示是一个长度为 10 的数组，存储了 8 个元素，`现在是需要依次删除前三个元素，a，b，c。如果每次删除操作都将所有元素往前移动，那么后续的 5 个元素总共需要移动 3 次，为了避免这个情况，我们可以先记录被删除的数据，每次操作仅仅记录那个位置的元素被删除。当数组没有空间存储数据时，再进行一次真正的删除操作，这样可以避免删除操作导致的数据搬移。
这个做法其实就是 Java 中 JVM 标记清除垃圾回收算法的核心思想。
所以，我们对于数据结构和算法的学习，不应该只是死记硬背，而是需要了解它背后的思想和处理技巧，明白为什么需要这种数据结构和这种算法。
数组的越界问题
首先来看一段 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;
}
这段代码的问题就是打印结果的时候，因为循环结束条件问题，会无限打印 “hello world”，给定的数组长度是 3， 但是循环结束条件是 i<=3 ，而 a[3] 其实就是访问越界了。
但是，在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。也就是说，a[3] 也是可以访问的，但是会定位到非数组所在的内存上，而这个地址正好是存储变量 i 的内存地址，也就是 a[3]=0 就相当于 i=0 ，最终导致代码的无限循环。
数组越界在 C 语言中是一种未决行为，没有规定这种情况编译器应该如何处理，所以通常会出现各种奇怪的逻辑错误。
不过，其他编程语言并不会将数组越界的工作丢给程序员来做，它们会有做越界的检查。
数组索引从0开始的原因
大多数的编程语言中，数组，或者说数据结构，索引都是从 0 开始，而不是从 1 开始。
首先，从数组存储的内存模型上看，索引，或者说“下标”最确切的定义应该是偏移(offset)。
前面介绍了数组的寻址公式：
a[i]_address = base_address + i * data_type_size
如果数组是从 1 开始计数，那么寻址公式就会为：
a[i]_address = base_address + (i-1) * data_type_size
对比两个公式，可以知道每次访问数组元素，从 1 开始计数的方式会多一次减法运算，相当于让 CPU 多一次减法指令，但随即访问数组元素应该是非常基础的操作，需要尽可能高效，因此，为了减少一次减法操作，数组采用从 0 开始计数，而非从 1 开始。
其次，主要是 C 语言设计者用 0 开始计数，后续的编程语言，如 Java 等都效仿了 C 语言，这也是方便 C 语言程序员学习其他语言的学习成本。当然，像 Python 还支持负数下标。
参考
极客时间的数据结构与算法之美课程
