数组（Array）：是一种线性表数据结构。用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表： 线性表上的每个数据最多只有前和后两个方向。例如数组，链表、队列、栈等等。
非线性表： 非线性表中，数据之间并不是简单的前后关系 。例如 二叉树、堆、图等。
连续的内存空间和相同类型的数据 ：高效的支持随机访问，低效的插入删除。
数组的时间复杂度和优化
有序的数组插入和删除的时间复杂度为O(n)，因为插入和删除操作都有可能需要移动数组元素。
插入操作的优化：如果数组不要求有序，那么插入指定位置，可以将此位置的原先值放入数组末尾即可。比如快排算法。
删除操作的优化：如果数组不要求有序，那么可以将删除元素标记，达到一定条件统一删除。比如JVM 标记清除垃圾回收算法，SparseArray的标记删除算法。
防止数组越界
java语言会对数据越界进行检查并异常抛出，并非所有的语言都能像java一样，进行数组越界检查，比如c语言。
数组为什么从0来时编号
数组从0开始编号可以在寻址的时候，更好的计算偏移量，比如第2个元素的偏移量就是1，所以为a[1]。
大多数语言都沿用了C语言的数组下标设计（从0开始）。但也有类外，比如python。
数组和容器的选择
java的ArrayList是对数组操作的封装容器，支持动态扩容，使用简单。但是无法存储基本类型，就会导致装箱与拆箱操作的性能损耗。
数据操作简单且大小已知，则可直接选用数组。
使用多维数组时，数组比容器更加直观一些。
从开发效率上来说，直接选用容器即可，省时省力，安全高效。如果是追求性能的底层开发，那么选择数组性能更好。
网友评论