数组

数组是一种线性表数据结构，用一组连续的内存空间来存储一组具有相同类型的数据。

特性：

1.线性表。
2.可以根据下标随机访问。

线性表：数组，链表，队列，栈。
非线性表：树，图。

计算元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

data_type_size：数组中每个数据元素的大小。

数组数据读取的时间复杂度：

1.根据下标随机访问的时间复杂度O(1)。
2.根据元素值访问的时间复杂度要看数组是否有序以及具体的查找算法，二分查找是O(logn)。

数据插入和删除的时间复杂度：

由于数组在内存空间上是连续的，插入或者删除数据时，为了保证连续性，需要做大量的数据搬移工作。所以数组的插入和删除操作元素的时间复杂度是O(n)；

针对数组插入和删除的优化：

• 如果数组的数据没有有序性要求，要将某个数据插入到第 k 个位置，为了避免大规模的数据搬移，一个简单的办法是直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。

• 如果应用场景下并不一定要求数据中数据的连续性，删除数据时，可以不真正删除数据。先数据标记为已删除，当数组没有更多可用存储空间时，再触发一次真正的数据删除操作，减少删除操作导致的数据移动。