数据结构-数组，介绍数组的数据结构，及底层实现。
简介
数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同数据类型的数据。
数组特性
线性表
线性表，就是数据排成像一条线一样的结构，每个线性表的数据最多只有前和后两个方向，除了数组，像链表、队列、栈等也是线性表结构。与此对应，非线性表，数据之前并不是简单的前后关系，比如二叉树、堆、图等。
连续内存
数组存储连续的内存空间和相同数据类型的数据，由于这个线性表和连续的内存空间，让数据自由了堪称杀手锏的特性-随机访问。但同时带来弊端，这两个限制让数组的许多操作变得非常低效，比如在数组中删除一个数据，为了保证内存的连续性，就需要大量的数据搬移工作。
底层结构
随机访问
数组是如何根据下标实现随机访问元素的呢，我们拿一个长度为10的int类型数据int a = new int[10] 举例,计算机给数据分配了一块连续的内存空间1000～1039，其中内存块的收地址base_address = 1000.
计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据，当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出元素的内存地址：
1 | a[i]_address = base_address + i * data_type_size |
其中data_type_size表示数据中每个元素的大小，数组中存储的int类型数据，所以data_type_size就是4个字节。
数组和链表的区别，一般都会回答，“链表适合插入、删除、时间复杂度O(1);数据适合查找，查找时间复杂度为O(1)”,实际上这种表述是不准确的，即便是排好序的数组，你用二分查找，时间复杂度也是O(logn),所以，正确的表述应该是：数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。
低效插入删除
插入操作
假设数组的长度为n，如果我们需要将一个数据插入到第k位置，为了把第k为止腾出来，我们需要将第k～n这部分的元素都顺序的向后面移动，那插入的操作的时间复杂度分析如下：
如果在数组的末端插入元素，那就不需要移动数据了，时间复杂度为O(1),但是如果在数组的头部插入元素，那所有的数据都需要一次向后移动，时间复杂度为O(n)。因为我们在每个位置插入元素的概率是一样的，所以平均下来时间复杂度为（1+2+3+…+n）/n=O(n)。
如果数组是有序的，我们在某个位置插入一个新元素时，就必须按照刚才的方法搬移K之后的数据，但是，如果数组中存储的数据没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果将某个数据插入到k位置，为了避免大规模的数据搬移，我们直接将第k个元素搬移到数组的最后，把新的的元素直接放入第k的位置。
利用这种技巧，在特定的场景下，插入数据的时间复杂度就降到了O(1),这个处理思想在快排中也应用了。
删除操作
和插入数据一样，如果我们删除了第k位置的数据，为了保持内存的连续性，也需要搬移数据。
时间复杂度，如果删除在数组的尾部，最好情况的时间复杂度为O(1);如果删除头部的数据，则最坏的情况为O(n).平均的时间复杂度也是O(n)。
实际上，在某些特殊场景，我们不一定非要追求数组中的数据连续性，我们将对此删除操作集中到一起执行，删除的效率就会提高很多。JVM的标记清除垃圾回收算法的核心思想就是这样的。
JVM标记清除算法：大多数主流虚拟机都采用可达性分析算法来判断对象是否存活，在标记阶段，会遍历所有的GC ROOTS,将所有的GC ROOTS可达的对象标记为存活，只有当标记工作完成后，清理工作才会开始。不足：1.效率问题，标记和清理的效率都不高，但是指导只有少量垃圾产生时会很高效 2.空间问题，会产生不连续的内存空间碎片。
对比容器
JAVA中的ArrayList，对比数组，其最大优势就是可以将很多数据操作的细节封装起来，比如前面提到的数组插入、删除数据需要搬移其他数据等，另外它还有一个优势，支持动态扩容。
数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间，如果我们申请了大小为10的数组，当第11个数据需要存储到数组中时，我们就需要重新分配一块更大的空间，将原来的数据复制过去，然后在讲新的数据插入。
如果使用ArrayList，我们就不需要考虑底层扩容的问题，ArrayLisy已经帮我们实现好了，每次存储空间不够的时候，它都会将空间自动扩容为1.5倍大小。
不过扩容操作设计内存的申请和数据搬移，是比较耗时的，所以如果实现能确定需要的存储大小，最好在创建ArrayList的时候就事先制定数据大小。
