重温数据结构－数组

在一般的数据结构教科书中，很少把数组单独列一个章节来介绍，一般都是跟着链表一起顺道介绍下，可能很多同学用了高级语言后，基本很少直接在代码中使用数组了，所以对数据结构中非常重要数组数据结构知之甚少。

数组的特点主要是线性的，并且数组中所有数据在内存中占用的是连续的内存空间和相同的数据类型。正是因为有了连续的存储空间和同一数据类型的限制，这就让数组可以很方便的做到通过数组下标进行数据随机读，并且时间复杂度是O(1)。但是同样有这样强大的优点必然有缺点，数组的缺点就是在对数组进行插入和删除操作的时候，为了保证数组中数据存储的连续性，就需要对数据进行迁移，如果是插入数据，那就要在插入位置将数据都后移；如果是删除数据，那就要在删除节点位置将后面的数据都前移。因为插入和删除的最好和最坏时间复杂度分别是O(1)和O(n)，那么根据平均复杂度算下来就是O(n)，可以说性能是比较差的。

数组的基本操作太简单了，这里就不介绍了，下面说下为什么数组的下标随机读的时间复杂度只有O(1)，因为数组有数据连续存储和数组内数据类型一致的特点，这就让计算机去根据下标查找数据的内存地址会非常方便，下面举个例子：

int nums[] = {1,2,3,4};
对于这个数组，计算机如果要读取下标为2的数值3怎么办？首先获取到nums数组的内存地址，假设是0x00001，这里假设int数据类型占用4位，那么3这个数字保存在0x00009,这个地址很好算出来，因为是连续存储的，所以 下标位i的目标地址＝数组地址 ＋ 数据类型大小＊i。

数组数据地址计算的公示也解释了为什么数组下标都是从0开始计数而不是从1开始，因为如果从1开始，公示就会变成下标位i的目标地址＝数组地址 ＋ 数据类型大小＊（i－1），那么计算机就会多一次运算，所以为了节约计算资源，设计成了下标从0开始。

下面再介绍下数组在哪些地方被用到了，我们日常工作中用的最多的ArrayList，在ArrayList底层就是通过数组来实现的，但是jdk将ArrayList底层数组的迁移操作都封装了，并且在ArrayList底层还支持动态扩容，看了源码就会知道所谓的动态扩容其实就是在原数组已经存满的情况下，再申请1.5倍空间的新数组，将原数组数据都迁移到新数组中，一旦遇到需要扩容性能就会下降很厉害，所以这就是为什么很多tips要求我们使用ArrayList的时候一定要根据预计数据量初始化大小，因为jdk中ArrayList的默认初始化空间很小，如果不指定就会导致频繁的扩容，进行数据迁移。

也有同学会问既然已经有了ArrayList那是不是可以完全抛弃数组了？当然不是。要知道ArrayList是无法保存基础数据类型的，像int、long这些基础类型都要封装位Integer、Long类才行，而开箱和闭箱会导致性能损耗，所以对于使用基础类型可以考虑使用数组。

其实对于数组这种数据结构我们只要知道，它是线性的，是连续存储、同样类型的集合，并且数组的随机读时间复杂度是O(1),插入和删除时间复杂度是O(n)就可以了。在日常编程定义数据的时候考虑下这些特性就能知道使用数组在这些场景的性能如何了。