1.数组是一种***线性表***（只有前后位置关系）数据结构； 2.他用一组***连续的内存空间***存储一组***相同类型的数据***
链表适合插入和删除，时间复杂度是O(1)； 数组适合***随机访问***，根据下标随机访问的时间复杂度是O(1)
若删除末尾元素，没有数据的移动，时间复杂度O（1）； 若删除开头元素，删除之后，所有的数据都要向前移动一位，时间复杂度是O(n)； 平均情况时间复杂度是O(n)；
若要删除多个元素，为了避免其他数据被移动多次，我们可以记录下已经删除的数据，每次的删除操作并不是真正的移除数据，只是记录某个数据已经被删除，当数组中没有更多空间来储存数据时，我们才触发一次真正的删除操作。
若在末尾插入元素，没有数据的移动，时间复杂度O（1）； 若在开头插入元素，所有的数据都要向后移动一位，然后插入新的数据，时间复杂度是O(n)； 平均情况时间复杂度是O(n)；
如果想要在k位置插入一个新的元素，我们可以直接将k位置的元素移动到数组末尾，然后在k位置插入新的数据
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; } 运行结果是：无限的打印
原因： 数组大小为3，a[0] a[1] a[2]; 当i=3时 数组a[3]访问越界，但是a[3]也会被定位到某块不属于数组的内存地址上； 如果这个内存地址恰好是存储变量i的内存地址，那么a[3]=0也就是i=0，会导致代码无限的循环。 （java会做越界检查）
容器的优势：可以将很多数组操作的细节封装起来；支持动态扩容（扩容操作涉及到内存的申请和数据的搬移，比较耗时，最好在创建容器的时候就指定好数据的大小）。
什么情况下用数组不用容器： 1.如果使用基本类型，可以使用数组（容器无法存储基本类型，比如int，long，需要封装为Integer和Long，java虽然有自动拆箱和装箱机制，但是有性能的消耗） 2.如果数据大小已知，并且对数据的操作非常简单，涉及不到容器提供的大部分方法，可以用数组 3.表示多维数组时，数组比较直观
a[i] i下标最确切的定义应该是“偏移” i如果是从0开始，a[i]的内存地址是：a[i]=数组首地址+i*type_size(存储数据类型的尺寸 例如 int为4字节) i如果是从1开始，a[i]的内存地址是：a[i]=数组首地址+（i-1）*type_size，每次随机访问数组元素多了一次减法运算，对于cpu来说是一种负担。
历史原因：其他语言都效仿c语言从0开始
第一步：标记出所有需要回收的对象（类比删除：记录所有删除的数据） 第二步：在标记完成后统一回收被标记的对象（类比删除：数组没有多余内存存储数据时，全部清除）
1.标记和清除效率都很低（时间问题）； 2.会产生很多不连续的内存碎片（空间问题），导致以后需要较大内存时，无法找到足够的连续空间而不得不提前触发垃圾收集动作
第一步：将可用内存按照容量划分为相等的两块； 第二步：每次只使用其中的一块A； 第三步：当使用的一块内存A用完了，就将还存活的对象复制到另外一块内存B上面； 第四步：原来使用的内存空间A一次清理掉。
1.内存缩小了一半
回收新生代（只浪费了百分之十的内存）： 第一步：将内存划分为Eden空间和两块较小的Survivor空间，HotSpot虚拟机是8:1； 第二步：每次只使用Eden空间和一块Survivor空间（A); 第三步：当使用的内存用完时，把所有存活着的对象复制到另外一块Survivor空间（B); 第四步：原来使用的内存空间A一次全部清理掉。
1.当对象存活率较高的时候就需要进行较多的复制操作，效率将会变低 2.还要有额外的空间作为担保
第一步：标记出所有需要回收的对象； 第二步：将所有的存活对象都向一端移动； 第三步：直接清理掉端边界以外的内存。
第一步：将Java堆分为新生代和老生代（根据对象存活周期的不同）； 第二步：新生代中采用复制算法（新生代中对象存活率较低）； 第三步：老生代中采用标记-清除或者标记-整理算法（老生代中对象存活率比较高，没有额外的空间对她进行分配担保）
一维数组：a[i]=数组首地址+i*type_size(存储数据类型的尺寸 例如 int为4字节)
二维数组：如果是a[m][n]:是m个1维数组（数组元素为n个） a【i】【j】=数组首地址+（i*n+j）*type_size
