定义
数组（Array）：一种线性表数据结构，使用连续内存空间存储相同数据类型的一组数据。
线性表：线性结构，只有前驱和后继元素，常见的有数组、链表、栈、队列。
非线性表：不止有前后关系，常见的有堆、图、树
优点-支持“随机访问”
数组的“随机访问”特性由以下3点保证：
- 数组是线性结构
所有数据线性存储，只有一个前驱一个后继。 - 连续内存空间
数据在内存中占用连续的内存空间，相邻的数据在内存中的存储地址也相邻。 - 相同类型数据结构
每个数据在内存中占用的大小都相同。
数组元素的寻址公式可以表示为：
arr[index]_address = base_address + index * data_type_size
可以根据索引直接访问任意位置元素的内存空间，实现“随机访问”。此处可以解释为什么数组下标从0开始，可以将数组下表看作内存地址的偏移，第一个元素相对首地址的偏移为0，所以下标是0。
缺点-插入删除的低效
插入
在指定位置插入数据时，需要将该位置之后的所有数据整体向后移动，时间复杂度为O(n)。如果数组是无序的，不关心元素的顺序的话，可以将插入元素所在位置的数据交换至数组末尾，再将元素插入。这样可以使插入时间复杂度为O(1)。
删除
为了保证内存空间的连续性，删除指定位置的元素后需要将此位置之后的元素整体前移，时间复杂度为O(n)。有一种解决方案是标记清除算法，删除元素只是将元素标记删除，当数组内存空间不足时再统一将已删除的元素内存空间回收，这样避免了多次移动元素带来的时间消耗。
数组使用注意事项
- 避免越界访问
- 使用容器类时最好根据需要指定大小
网友评论