数组是一种线性表结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表
- 线性表
数组、链表、队列、栈
- 非线性表
二叉树、堆、图
连续的内存空间和相同类型的数据 1
寻址公式（数组下标从0开始 ，减少计算内存地址时的减法运算）
1 | a[i]_address = base_address + i * data_type_size |
- 数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。排好序的数组二分查找的时间复杂度为O(logn)
- 插入操作 大量数据搬移保证连续性
最好O(1)在数组末尾插入元素，不需要移动数据；
最坏O(n)在数组开头插入元素，所有数据都需要依次往后移动一位。
在每个位置插入元素的概率是一样的，平均时间复杂度为”(1+2+…n)/n=O(n)”；
优化：数组中存储的数据没有规律，只是作为一个存储数据的集合，避免大规模的数据搬移，在将某个数据插入到第k个位置时，直接将第k位的数据搬移到数组元素的最后，把新的元素直接放入第k个位置。快速排序的思想
- 删除操作(大量数据搬移保证连续性)的平均时间复杂度为O(n)，最好O(1)，最坏O(n)
优化：先记录下已经删除的数据。每次的删除操作并不是真正的搬移数据，只是记录数据已经被删除了，当数组没有更多空间存储数据时，再触发执行一次真正的删除操作，从而大大减少删除操作导致的数据搬移。JVM标记清除垃圾回收算法的核心思想
数组or容器
容器：
将很多数组操作的细节封装起来，比如搬移数据；支持动态扩容。
数组：
存储基本类型，避免自动装箱拆箱的性能消耗；
数组大小事先已知、对数据的操作简单；
表示多维数组比较直观；
注重性能的底层开发。