数组

1.一种线性表数据结构
2.用一组连续的内存空间，存储一族具有相同类型的数据
3.支持随机访问，但插入、删除操作比较低效

随机访问：

1.一维寻址公式：a[i]_address = base_address + i * data_type_size
2.二维寻址公式：a[i][j]_address = base_address + (i * n + j) * data_type_size

插入操作：

1.在开头插入：最坏时间复杂度是O(n)，平均时间复杂度：O(n)；（需要将数据向后移动）
2.在中间第k位插入：时间复杂度是O(n-k)(保持顺序时)，无序时O(1)
3.在末尾插入：时间复杂度O(1)

删除操作：

1.在开头删除：最坏时间复杂度O(n)，平均时间复杂度O(n)
2.在中间第k位删除：每次删除操作知识记录数据已经被删除，当没有更多空间时，才触发直销真正的删除操作
3.在末尾删除：最好时间复杂度O(1)

数组下标为什么从0开始？

1.从数组的内存模型上来看，’下标‘最确切的定义应该是’偏移量（offset）’。
如果用a来表示数组的首地址，a[0]就是偏移量0的位置，也就是首地址，a[k]就表示便宜k个type_size的位置：a[k]_address = base_address + k * type_size；如果从1开始，则a[k]_address = base_address + (k-1) * type_size每次随机访问数组元素都多了一次减法运算，对于CPU来说，多了一次减法指令。
2.C语言下标从0开始，为了在一定程度上减少 C 语言程序员学习 Java 的学习成本，因此继续沿用了从 0 开始计数的习惯。

数组和ArrayList的应用场景区别？

1.ArrayList无法存储基本类型，比如int、long,需要封装为Integer、Long类，而自动拆装箱则会有一定的性能消耗。
2.如果数据大小事先已知，并且对数据的操作非常简单，用不到ArrayList提供的大部分方法。可以使用数组。但是如果不事先知道数据大小，使用ArrayList，动态扩容为1.5倍。
3.多维数组时，使用数组表示更加直观.Object[][] array；ArrayList<ArrayList<Object> > array。

数组对CPU缓存友好：

CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块，并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取。这样就实现了比内存访问速度更快的机制，也就是CPU缓存存在的意义:为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。
对于数组来说，存储空间是连续的，所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。