定义
数组是一种线性表数据结构。它用一组连续的内存空间存储相同数据类型的集合；基本上每种编程语言都会有数组这一数据结构，数组具有“随机访问”快，删除插入慢的特性。
随机访问
我们先来看下为什么数组的随机访问就快呢？假定我们有一个int类型的数组int[] arrs=new int[10],假定分配到的首地址为000，int类型占4字节，所以第二个元素的地址为004-007。
数组内存结构图.png
由于数组是按连续内存来存储数据的，所以我们可以根据下标计算出要访问的元素的地址，有了地址就可以直接取得数据，假定数组首地址为base_addr，那么第i个元素的地址就可以计算为:
arrs[i]_addr=base_addr+i*data_size
data_size根据数组存储的数据类型来做调整，比如int类型就是4字节，然后就用i*4+守地址。所以，数组的随机访问复杂度为O(1)。注意：只是随机访问时为o（1），当要查找某个元素的位置时，复杂度就要重新计算了，当数组有序时，使用二分查找可以最快得出，此时复杂度为O(logn)。
插入和删除
为了保证内存地址的连续性，数组的插入和删除操作都是比较低效的。比如插入操作，假定一个数组有n个元素，我们需要将一个数据插入到数组的第m(0<m<n)个位置，我们就需要将m+1~n这些位置的数据都往后挪一个位置，此时复杂度为O（n）：最坏时间复杂度是插入第一个位置O(n)，平均时间复杂度为(1+2+3+,,,+n)/n=O(n)。加入我们的数组不要求数据的有序性，可以采用搬移数据的办法将插入的复杂度降低为O(1)，即，将第m个位置的数据挪到数组末尾，然后待插入的数据放到原来m的位置，这样也实现了插入操作。
搬移式数组插入.png
对于删除操作的情况跟插入是基本一致的，具体就进行分析了，和插入一样，删除操作也有一些降低复杂度的技巧，比如类似jvm gc操作中的标记清除算法。前提也是在数组中数据的连续性要求不严格 的时候可行。例如我们上面的数组，我们现在要依次删除a、b、c三个元素，如果每删除一个元素就进行一次移位，那么除了删除的元素外，每个元素都需要在一次删除操作中进行一次移位，那么我们是不是可以先将一定数量的删除操作执行完再一次性执行移位操作呢，那么就能将复杂度降低很多。
数组和容器
容器是什么？Java中我们经常用到的ArrayList就是一种容器，容器可以说包含了数组的所有功能，那么我们为什么还要保留数组这个类型的数据结构呢？存在即合理，我们可以看下哪些情况下使用数组会比使用ArrayList更合适：
1、要存储的数据是基本数据类型的时候，而你的应用又对性能比较敏感，因为ArrayList无法存储基本数据类型，只能存他们的包装类，而这就会增加一次装包和拆包的操作，会降低一定的性能。
2、数组的大小已经确定，而且操作要求不复杂，这个时候就没必要使用ArrayList这么重型的工具了。
总结起来就是，ArrayList封装了数组的操作，使得使用更为简单便捷，但是会牺牲一定的性能，所以，日常业务使用哪个都无所谓吧，比较那一点点性能影响不大，但是对于一些高并发的操作，能用数组当然是数组比较好，比较操作多了，再小的性能损耗也是很可观的。
ps：算法和数据结构很难啃，但是很重要，一步一步学下去吧。
网友评论