2.1 数组
支持随机访问（索引与寻址）
线性表（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) push_back 最坏 O(n) 平均 O(n)
删除
O(n)
最好 O(1) pop_back 最坏 O(n) 平均 O(n)
平均情况时间复杂度：
等差数列求和公式：
在特定场景下，可以对插入和删除的时间复杂度进行优化。比如：
插入：把新元素插入到位置 k 之后，将原来的数据 a[k] 直接放在最后。eg.快速排序
删除：先标记删除，最后再统一移动一次，即合并多次删除。eg. JVM 标记清除垃圾回收算法
JVM 标记清除算法：会先标记出需要回收的对象，然后再统一回收标记对象。不足是效率不高、会产生不连续的内存空间碎片。
所以，在学习数据结构和算法的时候，重点是理解其背后的思想和处理技巧，切忌照本宣科。
变长数组
从严格意义上讲，数组本身在定义的时候是需要预先指定大小的，因为需要分配连续的内存空间。而变长数组在创建的时候，是可以不指定长度的，它支持动态扩容。
很多高级语言都提供了变长数组，严格说它们不是一种数据结构，而更像是个容器或接口，它们封装了很多数组的操作细节（比如插入和删除元素/在头部插入元素）。
C++
vectorJava
ArrayListPython
list
容器能否完全替代数组？
在平时的业务开发中，我们可以直接使用编程语言提供的容器类，因为方便。但是，如果是特别底层的开发，直接使用数组可能会更合适，因为变长数组会涉及到动态扩容，而扩容操作又涉及到内存申请和数据搬移，比较耗时。
数组的适用场景，一是事先知道数据的大小、且对数据的操作比较简单，二是性能。
即便使用的是容器类，如果事先就能确定所需数据的存储大小，最好在创建的时候就能指定数据大小。
设计变长数组
Resizable Array, 场景是编译器或库
变长数组是个系统设计问题，它涉及到基本的数据结构（数组）、接口和覆盖场景。
支持索引和随机访问，及其它操作
分配多长的连续空间？数组容量、实际长度
空间不够用了怎么办？eg.重新申请2倍(或1.5倍)的连续空间，然后拷贝到新空间+释放旧空间
空间剩余很多如何回收？eg.当空间利用率低于25%时，就释放掉一半的空间
均摊 O(1) 在空数组中连续插入 n 个元素，总插入/拷贝的次数为 从一次扩容到下次释放，至少需要再删除 次
总结
数组是一种基本的线性表数据结构，它用一段连续的内存空间来存储一组具有相同类型的数据。数组的基本特点是支持随机访问，关键就在于索引和寻址。
一维寻址公式，数组的大小是 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)。
说明：插入和删除的特定场景，可以特殊处理。
变长数组不是严格意义上的数组，它更像是个容器或接口，我们需要理解动态扩容的原理和思路。结合具体的编程语言，感受下数组和变长数组的异同。
数据类型：数据结构 or 容器/接口
主要参考
Last updated