数据结构：数组详细介绍，你足够了解数组的特性和使用场景吗？

基本介绍

定义

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

特性

从定义可以看出，数组的特性主要有两个：

1. 线性表：
   线性表的定义-百度百科：
   线性表是最基本、最简单、也是最常用的一种数据结构。线性表是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
   从这句话我们可以知道：
   a. 线性表是一个序列。
   b. 线性表是有限的。
   c. 线性表的数据元素具有相同的特性。
   常见的线性表：数组，链表，队列，栈等。

2. 连续的内存空间， 相同类型的数据：我们平时使用最多的元素随机访问，就是归功于数组的这个特性。

优缺点

优点

1. 支持随机访问： 如上文所说，数组存于连续的地址空间，并且存储的是相同类型的数据，这使得数组可以通过下标与数据类型的大小直接定位到数据位置。假设数组a的数据类型大小为size，那么可以得到第i 个元素的起始地址为：

    a[i]_addr = base_addr + i * size
   

缺点

1. 插入效率低
   因为数组要保证插入后数据的连续性，需要将插入位置后面的数据依次向后进行移动，所以插入的效率很低。插入时最好的情况是在数组末尾插入，时间复杂度为O(1)；最坏的情况是在数组起始位置插入，时间复杂度为O(n)；插入的平均时间复杂度为 (1+2+…+n)/n = O(n)。
   
   优化方法：如果数组内元素不要求有序时，可以将原数组中第k个数据插入到数组末尾，然后将想要插入的数据插入到第k个位置即可。如上图示例，可以将元素b插入到数组末尾，再将f插入到b原来的位置。
2. 删除效率低
   也是因为要保证删除后数据的连续性，需要将删除位置后面的元素依次向前进行移动，所以删除的时间复杂度和插入一样。即最好的情况是删除末尾数据，时间复杂度为O(1)；最坏的情况是删除起始位置数据，时间复杂度为O(n)；删除的平均时间复杂度为O(n)。
   
   优化方法：在允许数组内存在无用数据的前提下，需要删除多个数据时可以采用标记删除法，即先不进行实际删除操作，而是先将所有需要删除的数据标记为被删除状态，最后再进行一次删除操作清除掉所有被标记的元素。
   上面的优化思路可以参考jvm的垃圾收集算法：jvm的垃圾回收算法中最基础的收集算法是’标记-清除‘算法。顾名思义，标记清除算法分为’标记‘和’清除‘两个阶段：首先标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象，参考下图：
   

注意点

1. 严格上来说，数组不是随机查找的时间复杂度为O(1)，而是随机访问的时间复杂度为O(1)。
2. 使用数组进行随机访问时，一定要对数组越界访问时刻保持警惕，不然可能会有意想不到的后果。

参考资料

最近在学习数据结构与算法备战下一家公司的面试，做了一些总结并查阅了一些参考资料：

1. 极客时间-数据结构与算法专栏
2. 百度百科
3. 深入理解java虚拟机

我想说

第一次写技术文章，主要目的还是锻炼一下自己的写作与总结能力，希望可以借此机会激励下自己，多读读书，少玩点游戏 (0.0删除线格式 )
大家有什么意见欢迎指出，我会虚心接受的。ʘᴗʘ