数组在我们日常的编程工作中会经常用到，它不仅仅是一种编程语言的数据类型，还是一种最基础的数据结构。今天我们来重新认识一下它。
@[toc]
数组是什么？
数组是一种线性表数据结构，用一组连续的内存空间，来存储一组具有相同类型的数据。
关键词
- 线性表
- 连续的内存空间和相同类型的数据
线性表，表示数据像糖葫芦一样被串起来，每个数据最多只有前后两个方向。除了数组，其他线性表结构的还有， 栈、链表、队列等。
与之对应的就是非线性表，即内部数据元素非简单的前后关系，比如，二叉树，图，堆等结构。
连续内存空间和相同类型数据，提供了“随机访问”的特性，但是在插入和删除数据的时候，会导致大量的内存空间需要进行迁移。以保证内存空间的连续性。
数组是如何通过下标随机访问元素的
首先我们创建一个数组 int[] a = new int[10]。假如计算机给我们创建的数组内存地址如下，内存地址范围1000~1039， 内存的首地址为k=1000；
那么每个元素的内存地址等于首地址加上数据类型占用的字节数,那计算公式就是
a[i]_address = k + i * data_byte_size
比如，第三个元素的地址为： 1000 + 2* 4 = 1008
插入和删除操作低效原因
假如我们有一个长度为n的数据，现在我们需要将一个元素x,插入到k的位置，那么为了保证数组内存空间的连续性，那么k~n之间的数据都需要顺序的往后挪一位。
从时间复杂度上来说看，如果插入的数据正好是数组的末尾，就不需要移动任何数据，那么时间复杂度为O(1)；如果恰好插入在数组的头部，那么后面的元素都要顺序后移一位，那么最坏时间复杂度就是O(n)；其实在数组每个位置插入元素的概率是一样的，所以平均时间复杂度为O(n)。
如果数组中的元素是有序的，那么我们需要遵循上面的方法；如果数组中的元素不需要有序呢，比如我们有个元素需要插入到k位置， 最简单的方式就是将原来k位置的元素放到数组的末尾，将新元素放在k的位置上，这种情景下，插入元素的时间复杂度就是O(1)了。
同样的删除操作也是一样，最好的时间复杂度为O(1),最坏的为O(n)，平均为O(n)
再将元素多次删除时，为了提高效率，可以考虑将删除操作集中在一起。我们在进行删除操作是，并不是真正的删除，只是将需要删除的元素进行标记，当数组没有更大存储空间时，再进行一次真正的删除，删除标记的元素。这就大大减少了每次删除元素进行的搬移操作，这也是JVM 标记清除垃圾回收算法的核心思想。
数组越界问题
首先对于Java语言来说，java本身会做数组越界检查，比如下面的代码，就会抛出异常
java.lang.ArrayIndexOutOfBoundsException。
int[] a = new int[6]; a[6] = 10;
而在C语言中，数组越界是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。因此需要C语言的开发者，在开发过程中需要处理数组越界问题。
数组和容器的适用场景
Java中ArrayList的使用是非常常见的。ArrayList相对于数组来说有两大优点：
- 分装了数组的需要操作细节，比如插入，删除操作
- 动态扩容。数组是固定的，而ArrayList在存储空间不够的时候，会自动扩容为1.5倍大小。
实际业务开发场景中，如果一直数据的数量大小，在使用ArrayList时建议指定大小，减少内存扩容申请和数据搬移的耗时，比如我们已知数据大小为10000
ArrayList<Books> books = new ArrayList(10000); for (int i = 0; i < 10000; ++i) { books.add(xxx);}
那么什么时候使用数组更合适呢？
- 数据大小已确定，数据操作比较简单，
- 多维数组，使用数组比较直观
- Java ArrayList无法存储基本类型数据，比如int,long 等，需要进行装箱拆箱，有一定的性能损耗，使用数组会比较合适
为什么数据的下标索引是从零开始
首先我们回到上面计算元素内存地址的公式
如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[i]就表示偏移 i 个 type_size 的位置
a[i]_address = base_address + i * data_byte_size
如果下标索引从1开始，那么公式就变成了
a[i]_address = base_address + (i-1) * data_byte_size
对比上面的公式，从 1 开始编号，每次随机访问数组元素都多了一次(i-1)减法运算，对于 CPU 来说，就是多了一次减法指令,增加了性能开销。
面试问题
面试官： 说一说链表和数组的区别？
答：1、数组中的元素存在一个连续的内存空间中，而链表中的元素可以不存在于连续的内存空间。
2、数组支持随机访问，根据下标随机访问的时间复杂度是O(1)；链表适合插入、删除操作，时间复杂度为O(1）
