数据结构与算法 数组

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

线性表： 线性表上的每个数据最多只有前和后两个方向。例如数组，链表、队列、栈等等。

非线性表： 非线性表中，数据之间并不是简单的前后关系 。例如 二叉树、堆、图等。

连续的内存空间和相同类型的数据 ：高效的支持随机访问，低效的插入删除。

数组的时间复杂度和优化

    有序的数组插入和删除的时间复杂度为O(n)，因为插入和删除操作都有可能需要移动数组元素。

    插入操作的优化：如果数组不要求有序，那么插入指定位置，可以将此位置的原先值放入数组末尾即可。比如快排算法。

    删除操作的优化：如果数组不要求有序，那么可以将删除元素标记，达到一定条件统一删除。比如JVM 标记清除垃圾回收算法，SparseArray的标记删除算法。

防止数组越界

    java语言会对数据越界进行检查并异常抛出，并非所有的语言都能像java一样，进行数组越界检查，比如c语言。

数组为什么从0来时编号

    数组从0开始编号可以在寻址的时候，更好的计算偏移量，比如第2个元素的偏移量就是1，所以为a[1]。

    大多数语言都沿用了C语言的数组下标设计（从0开始）。但也有类外，比如python。

数组和容器的选择

    java的ArrayList是对数组操作的封装容器，支持动态扩容，使用简单。但是无法存储基本类型，就会导致装箱与拆箱操作的性能损耗。

    数据操作简单且大小已知，则可直接选用数组。

    使用多维数组时，数组比容器更加直观一些。

    从开发效率上来说，直接选用容器即可，省时省力，安全高效。如果是追求性能的底层开发，那么选择数组性能更好。