数组

• 线性表结构
• 使用一组连续的内存空间
• 相同类型数据

线性表结构

数据像一条线一样的结构,只有前,后两个方向.如链表,队列,栈等

连续内存空间

• 随机访问
• 插入,删除就要做大量的迁移工作

内存地址: a[i]_address = base_address + i * data_type_size

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

如果我们在数组最后插入或删除,复杂度为O(1),如果在中间为O(n)

优化

插入:如果数组只是数据集,数据没有规律的情况下,我们可以把插入变成移动.

删除:记录删除数据,将多次删除合并为一次删除.

越界问题

访问到不属于该数组的一块内存地址上,造成bug.