数组

为什么很多编程语言中数组都从0开始编号

如何实现随机访问

什么是数组

1. 一种线性表数据结构

2. 连续的内存空间

3. 具有相同的类型的数据

低效的“插入” 和 “删除”

插入

1. 有序数组的插入

   1. 插入到k位置
   2. 将k-n数据后移
   3. 将k插入

2. 无序数组的插入

删除

逐个删除

1. 删除第k个元素
2. 将k-n元素前移一位

标记统一删除

1. 将要删除的数据做上标记
2. 等数组空间不够时，统一一起删除

警惕数组的访问越界问题

1. c没有对数组越界做任何处理，交由开发负责
2. java等高级语言对数组越界会抛出异常

容器能否完全替代数组

1. 在业务上，能（有微小的性能开销换取开发效率）
2. 在底层，不能 （对性能要求极高的不能）

解答开篇

1. 从数组存储的内存模型上看， 下标 应该为 偏移量
2. a[k]的内存地址公式：

   a[k]_address = base_address + k * type_size

3. cpu 可以省去一次减法