一、概念：数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
(解释两个关键词)
线性表：顾名思义，线性表就是数据排成想一条线的结构。每个线性表上的数据都只有前后两个方向。其实除了数组，链表，队列，栈等也是现行表结构。
线性表.png
而与他相对应的就是非线性表。比如二叉树，堆，图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系
非线性表.png
连续的内存空间和相同类型的数据：正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但是有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。
数组的寻址公式：
a[i]_address = base_address + i * data_type_size
其中表示数组总每个元素的大小。如果数组中存储的是int类型的数据，那么 data_type_size 就为4个字节。
数组和链表的区别问题，准确的的面试回答：链表适合插入、删除，时间复杂度是O(1);数组适合查找，同时数组支持随机访问，根据下标随机访问的时间复杂度是O(1)；
【解析：数组是适合查找操作，但是查找的时间复杂度并不为O(1)。即便是排好序的数组，你用二分法查找，时间复杂度也O(logn)。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度是O(1)】
二、低效的“插入”和“删除”
插入操作
我们举个例子来说，假设数组长度为n，现在我们需要将一个数据插入到数组的第K个位置。为了把第K个位置腾出来，给新数据，，我们需要将k~n这部分元素顺序向后移动一位。那么我们分析一下时间复杂度。
如果在数组末尾插入数据，那么就不需要移动任何数据了，这样就是最好的情况，时间复杂度就是O(1)；
如果在数组的开头插入数据，那么就需要所有数据依次向后移动一位，所以就是最坏的情况，时间复杂度为O(n);
因为我们在每个位置插入的概率是一样的，所以平均情况时间复杂度就是 (1+2+…n)/n=O(n)。
如果数组是有序的，我们在某个位置插入新元素时，就必须按照上面的方法，一次移动k后面的所有元素。但是如果数组是无序的，没有任何规律的，数组只是被当做一个存储数据的集合。在这种情况下，如果将某个数据插入到第k个位置，为了避免大规模数据移动，我们还有一个简单的方法，就是将k位的数据直接移动到数组的最后，然后将新元素放在k位即可。
利用这种处理技巧，在特定的场景下，在第k个位置插入一个元素的时间复杂度就会降为O(1)。这个处理思想在快排中也会用到。。。
删除操作
跟插入操作类似，如果我们要删除第k个位置的元素，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。
和插入类似，如果删除末尾的数据，那么时间复杂度就是O(1)，删除开头的数据就是O(n)，平均时间复杂度也就是O(n)
实际上某些特殊的场景下，我们不一定非要追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率会更高一些。因为我们为了避免多次删除的时候，数据进行多次搬移，，我们可以先记录下已删除的数据。每次删除操作并不是真正的搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们在触发执行一次真正的删除操作，这样就大大的减少了删除操作导致的数据搬移。
上面的思想就是JVM标记清除垃圾回收算法的核心思想
三、警惕数组的访问越界的问题
举两个例子来讲：一个是C语言例子，一个是Java语言的例子
C语言代码例子：
int main(int argc, char* argv[]){
int i = 0;
int arr[3] = {0};
for(; i<=3; i++){
arr[i] = 0;
printf("hello world\n");
}
return 0;
}
根据上面的例子可以看出，最后的打印结果是无限输出hello world。这就是由于数组下标越界导致的。
数组越界在C语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续的内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。
正是这样很多计算机病毒也正是利用代码中的数组越界可以访问非法地址的漏洞，来攻击系统，所以写代码是一定要警惕数组下标越界问题。
Java的例子：
Java代码本身就会做越界检查，比如下面这几行代码就会抛出java.lang.ArrayIndexOutOfBoundsException异常。
int[] a = new int[3];
a[3] = 10;
四、容器是否能够完全代替数组
针对数组类型，很多语言都提供了容器类，比如Java中的ArrayList、LinkedList；C++ STL中的vector。在项目开发中，什么时候适合用数组，什么时候使用用容器呢？
先说一说容器和数组对比有哪些优势呢？？？
个人认为ArrayList最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，他还有一个优势，就是支持动态扩容
数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。如果我们申请了大小为10的数组，当第11个数据需要存储到数组的时候，我们就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。
如果使用ArrayList，我们就完全不需要关心底层的扩容逻辑，ArrayList已经帮我们实现好了。每次存储空间不够的时候，他都会将空间自动扩容1.5倍大小。
不过，这里需要注意一点，因为扩容操作涉及到内存申请和数据搬移，是比较耗时的。所以如果事先能确定存储的数据大小，最好在创建ArrayList的时候先指定数据大小
例子：比如我们要从数据库中取出10000条数据放到ArrayList。我们看下面几行代码，你会发现，相比之下，事先指定数据大小可以省掉很多次内存申请和数据搬移操作。
ArrayList<User> users = new ArrayList(10000);
for (int i = 0; i < 10000; ++i) {
users.add(xxx);
}
使用数组比较合适的场景，总结几点：
- Java中ArrayList无法存储基础类型，比如int、long，需要封装为Integer、Long类，而AutoBoxing，UnBoxing则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
- 如果数据大小事先已知，并且对数据的操作非常简单，用不到ArrayList提供的大部分方法，也可以直接使用数组
- 当表示多维数组时，用数组往往更加直观。比如Object[][] arr;而用容器的话则需要这样定义ArrayList<ArrayList> arr
总结
对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢的性能，完全不会影响到系统的整体性能。，但是如果做得是一些非常底层的开发。比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。
篇外了解：
JVM标记清除算法：
大多数主流虚拟机采用可达性分析算法来判断对象是否存活，在标记阶段，会遍历所有 GC ROOTS，将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后，清理工作才会开始。
不足：1.效率问题。标记和清理效率都不高，但是当知道只有少量垃圾产生时会很高效。2.空间问题。会产生不连续的内存空间碎片。
二维数组内存寻址：
对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为：address = base_address + ( i * n + j) * type_size
函数体内的局部变量存在栈上，且是连续压栈。在Linux进程的内存布局中，栈区在高地址空间，从高向低增长。变量i和arr在相邻地址，且i比arr的地址大，所以arr越界正好访问到i。当然，前提是i和arr元素同类型，否则那段代码仍是未决行为。
