数组是一种线性表数据结构.他用一组连续的内存空间,来存储一组具有相同类型的数据.
线性表 就是数据排成像一条线一样的结构.每个线性表上最多只有前和后两个方向.链表,堆,栈也是线性表结构
连续的内存的空间和相同的类型数据. 正是因为这个两个限制,从而才有了”随机访问”的特性.寻址公式: a[i]
_address = base_address + i * data_type_size.
低效的”插入”和”删除”
插入操作
假设数组长度为n,现在把一个数据插入到k个位置,我们需要将k~n这部分元素顺序的往后挪一位.此时如果是在末尾插入数据,这时候的时间复杂度是O(1);如果在开头插入数据,所有数据都要移动一位,此时最坏时间复杂度是O(n).因为每个位置插入数据的概率一样,所以平均时间负载度为(1+2+3+…+n)/n=O(n).
但是,数组存储并没有要求顺序,在这种情况下,为了避免大量数据移动.直接将k原数据放在数组元素最后,把新的元素直接放在k位置上.这时候时间复杂度就会将为O(1).
删除操作
如果删除第K个位置,为了保证内存的连续性,也需要搬移数据.如果删除末尾数据最好复杂度是O(1).如果是开头,最坏时间复杂度为O(n).平均时间复杂度也是O(n).
但是,如果不一定追求数据的连续性,我们可已将多次删除操作集中一起执行.