# 数组
- 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
	- 线性表（Linear List）：数据呈线性排列，每个数据最多只有前和后两个方向。除了数组，链表、队列、栈等也是线性表结构。
	- 非线性表，比如二叉树、堆、图等。

- 连续的内存空间和同类型的数据 --> 随机访问，根据下标访问元素，O(1)的时间复杂度
	- 插入、删除操作的低效：在位置 i 插入或删除 i 元素时，i 后面的所有元素都要向后或向前移一位（保证内存空间的连续性）；平均情况时间复杂度为 O(n)

- 动态数组（dynamic array）
	- 创建数组时需要预先指定数组的大小；
	- 当用户持续增添新元素，预留空间会耗尽；而与数组相邻的内存可能已经储存其他数据；
	- 此时会生成一个新的、更大的数组，将原数组元素复制进新数组
	
- 数组为什么从 0 开始编号？
    - 下标 其实指的是 “偏移（offset）”，计算 k 元素的内存地址公式：
        `a[k]_address = base_address + k * type_size`	
    - 若下标以 1 开始，则 `a[k]_address = base_address + (k-1) * type_size`，每次随机访问数组元素都多了一次减法运算