深入理解数组
数组是一种基本的线性表数据结构，它用一段连续的内存空间来存储一组具有相同类型的数据。
线性表, Linear List, 即数据排成一条线似的的结构，比如数组/链表/栈/队列。与之相反的是非线性表，比如二叉树/堆/图，其数据之间并不是简单的前后关系。
原理
正是因为“内存连续+类型相同”的内存模型，数组的基本特点就是支持随机访问。它可以 O(1) 地随机访问一个 a[i]，关键就在于索引和寻址，下标 i 确切地说是偏移（offset）。
下标从 0 开始
a[i]_address = base_address + i * type_size
如果下标是从 1 开始的，即 a[i]_address = base_address + (i-1) * type_size，那就意味着每次随机访问数组元素时，CPU 都要多执行一条减法指令。
大多数高级语言的数组下标都是从 0 开始的。当然也有例外，比如 Matlab 的数组下标是从 1 开始的、Python 的下标支持负数。
访问越界
在 C 语言中，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的（即便不是数组的合法内存），程序就有可能不报任何错误。
在有些语言中，语言本身是会做越界检查的，比如 Java。
时间复杂度
为了保持内存的连续性，数组的插入和删除因此而变得比较低效。
操作 | 时间复杂度 | 不同情况 |
|---|---|---|
访问 | O(1) | |
插入 | O(n) | 最好 O(1)最坏 O(n)平均 O(n) |
删除 | O(n) | 同上 |
平均情况时间复杂度：(1+2+...n)/n = ((1+n)/2) * n / n = (1+n)/2 = O(n)
等差数列求和公式：Sn = (a1+an)/2 * n
在特定场景下，可以对插入和删除的时间复杂度进行优化。比如：
- 插入：把新元素插入到位置 k 后，将原来的数据 a[k] 直接放在最后。eg.快速排序
- 删除：先标记删除，最后再统一移动一次，即合并多次删除。eg. JVM 标记清除垃圾回收算法
JVM 标记清除算法：会先标记出需要回收的对象，然后再统一回收标记对象。不足是效率不高，且会产生不连续的内存空间碎片。
所以，在学习数据结构和算法的时候，重点是理解其背后的思想和处理技巧，切忌照本宣科。
变长数组
从严格意义上讲，数组本身在定义的时候是需要预先指定大小的，因为需要分配连续的内存空间。而变长数组在创建的时候，是可以不指定长度的，它支持动态扩容。
很多高级语言都提供了变长数组（如下），严格说它们不是一种数据结构，而更像是个容器或接口，它们封装了很多数组的操作细节（比如插入和删除元素/在头部插入元素）。
- C++
vector - Java
ArrayList - Python
list
容器能否完全替代数组？
在平时的业务开发中，我们可以直接使用编程语言提供的容器类，因为方便。但是，如果是特别底层的开发，直接使用数组可能会更合适，因为变长数组会涉及到动态扩容，而扩容操作又涉及到内存申请和数据搬移，比较耗时。
数组的适用场景，一是事先知道数据的大小、且对数据的操作比较简单，二是性能。
即便使用的是容器类，如果事先就能确定所需数据的存储大小，最好在创建的时候就能指定数据大小。
设计变长数组
Resizable Array, 场景是编译器或库
变长数组是个系统设计问题，它涉及到基本的数据结构（数组）、接口和覆盖场景。
- 支持索引和随机访问，及其它操作
- 分配多长的连续空间？数组容量、实际长度
- 空间不够用了怎么办？eg.重新申请2倍(或1.5倍)的连续空间，然后拷贝到新空间+释放旧空间
- 空间剩余很多如何回收？eg.当空间利用率低于25%时，就释放掉一半的空间
均摊 O(1) 在空数组中连续插入 n 个元素，总插入/拷贝的次数为 n+n/2+n/4+... < 2n 从一次扩容到下次释放，至少需要再删除 n - 2n*0.25 = 0.5n 次
总结
数组是一种基本的线性表数据结构，它用一段连续的内存空间来存储一组具有相同类型的数据。数组的基本特点是支持随机访问，关键就在于索引和寻址。
- 一维寻址公式，数组的大小是 n
a[i]_address = base_address + i * type_size。
- 二维寻址公式，数组的大小是 m*n
a[i][j]_address = base_address + (i * n + j) * type_size
注意访问越界
为了保持内存的连续性，数组可以做到 O(1) 地随机访问一个数组元素，但也因此插入和删除操作比较低效。它们的时间复杂度分别是随机访问 O(1)、插入操作 O(n)、删除操作 O(n)。
插入和删除的特定场景，可以特殊处理。
变长数组不是严格意义上的数组，它更像是个容器或接口，我们需要理解动态扩容的原理和思路。结合具体的编程语言，感受下数组和变长数组的异同。
数据结构 - 数据类型 - 容器/接口
主要参考
- https://time.geekbang.org/column/article/40961
- https://u.geekbang.org/lesson/270?article=419794