数组

概念

1. 一种线性表数据结构
2. 用一组连续内存，存储相同类型的数据
3. 支持随机访问，但插入删除低效

操作

随机访问

1. 一维寻址公式：a[k]_address = base_address + k * type_size
2. 二维寻址公式：对m * n数组，a[i][j] = base_address + (i * n + j) * type_size

插入操作

1. 最坏(在开头插入)O(n)，平均O(n)
2. 最好(在末尾插入)O(1)
3. 无序在第k位插入，可第k位插最后，写入第k位，O(1)

删除操作

1. 最坏(在开头删除)O(n)，平均O(n)
2. 最好(在末尾删除)O(1)
3. 标记删除，以后触发真正删除操作，均摊

应用

1. 平时开发直接用编程语言提供的容器
2. 特别底层开发，直接使用数组