线性表之数组

数组在开发中是我们最常见的一种数据结构，数组也是最重要的数据结构之一，刚开始接触编程的时候我就有一个疑惑：数组的下标为什么是从 0 开始的，而不是从 1 开始，这样不是更加直观吗？

数组简介

通过前面这篇文章 什么是数组?随机访问特性的原理?为什么数组下标是从0开始? 我们知道，数组是一种线性表数据结构,用一组连续的内存空间来存储一组具有相同数据类型的数据
上面这句话中有几个关键字 线性表、连续内存空间、相同数据类型，我们来看看这几个关键字的含义

线性表

线性表就是数据排列成一条线一样的结构，就像日常生活中我们常见的高铁，每节车厢都是首尾相连，数据最多只有 前 和 后 两个方向，线性表数据结构的特点：存在一个唯一的没有前驱的数据元素(头)，存在一个唯一的没有后继的数据元素(尾)。队列、栈、链表 都是线性表数据结构

非线性表

与线性表对应的就是非线性表数据结构，二叉树、堆 都是非线性表数据结构的代表。之所以叫 非线性表，是因为在非线性表中，数据之间并不是简单的前后关系

连续的内存空间

正是由于数组具备 连续的内存空间 与 相同的数据类型，使得数组具备一个很优秀的特性 随机访问。我们可能见到过面试中会被问到 数组和链表有什么区别?，其实这个问题想要考察的知识点就是数组随机访问的特性，这里正确的回答应该是 数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)

随机访问

我们知道数组是通过下标访问数据的，那么它是如何实现随机访问的？
我们申请一个长度为 6 的 int 类型的数组 int[] a = new int[6]，一个 int 类型占用 4 个字节，所以，该数组占用的内存空间为 4 * 6 个字节，假设计算机分配的连续内存空间为 1000~1023，则该数组内存块的首地址是 base_address = 10000。当程序随机访问数组中的第 i 个元素，计算机通过以下寻址公式计算出内存地址

targetAddress = base_address + i * data_type_size

• targetAddress：访问的目标内存地址
• base_address：数组内存块的首地址
• i：表示要访问数据的下标

• data_type_size：数据类型的字节大小，如，1 个 int 类型数据占用 4 个字节

  
  QQ20200624-190523@2x.png

为什么下标从 0 开始？

下标 最确切的定义应该是 偏移(offset)。前面说到，如果使用 base_address 表示数组内存块的首地址，那么 a[0] 就是偏移为 0 的位置，a[i] 就表示偏移 i 个 data_type 字节的位置，所以计算 a[i] 的内存地址只需要使用下面这个公式(数组寻址公式)即可：

targetAddress[i] = base_address + i * data_type

如果说数组下标是从 1 开始，那么计算 a[i] 的内存地址公式则就需要改成：

targetAddress[i] = base_address + (i - 1) * data_type

对比上面两个公式，当数组下标从 1 开始每次随机访问数组元素都多了一次减法运算，相当于多了一次减法指令

数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就需要尽可能做到极致，所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始

低效的插入和删除

访问效率提升了，但是这也使得数组的插入和删除变得低效，为了保证内存连续性，就需要做数据迁移工作

插入操作

数组长度为 n,现将一个元素插入到数组中的第 k 个位置。为了满足内存连续性要求我们需要把第 k 个位置腾出来存放即将插入的元素，然后把 k 到 n 这部分的数据都往后挪一位。这个插入的时间复杂度是多少?
当把新元素插入到数组的末尾，这个时候不需要移动任何元素，这是最好的情况，所以 最好情况时间复杂度 为 O(1)。
当把新元素插入到数组的头部，那么数组中的所有数据都要往后挪一位，这是最坏情况，所以 最坏情况时间复杂度 是 O(n)
将新元素插入到数组中不同位置总计有 n 种情况，每一种情况发生的概率均为 1 / n，由前面的介绍我们知道 平均情况时间复杂度 = 每种情况遍历的次数累加和 / 所有情况数量
所以时间复杂度为
((1/n) * 1 + (1/n) * 2 + (1/n) * 3 + ...... + (1/n) * n) / n = (n + 1) / 2n = O(n)
注意：这里需要将每种情况发生的概率考虑进去
那么针对这种情况我们如何优化下时间复杂度呢?我们分情况讨论下
1.如果数组中的数据本身是有序的，那么我们需要将 k 之后的数据往后挪一位，此时时间复杂度就是 O(n)
2.如果数组中的数据不是有序的，仅作为一个存放数据的集合，当在第 k 个位置插入数据时，我们只需要把原本存放在 k 位置的数据放到数组的最后一位，然后把新插入的数据放到 k 位置即可，这样的话时间复杂度就是 O(1)

删除操作

实际在删除数组中的某些元素时，在某些特定的场景下，我们为了避免因数据搬迁而导致的效率问题，可以在不保持数据内存地址连续性的情况下，可以整体记录将要删除的数据，每次的删除操作并不是真正的搬迁数据，只是记录数据已经被删除。当数组中没有更多的存储空间或者达到删除阈值时，我们再触发执行一次真正的删除操作，这样就大大减少了山粗糙做带来的数据搬迁

如数组 number[6] 中存储了 6 个 int 类型的元素：1、2、3、4、5、6。我们现在需要删除 1、2、3 三个元素，为了防止因每次删除操作产生的数据搬迁从而导致效率低下的问题，我们只需要将1、2、3这三个要删除的元素进行标记删除，当达到删除阈值 3 的时候，我们再真正的执行一次删除操作，这个时候才会进行数据搬迁，通过这种方式就大大提高数组删除的效率

实际上数组删除操作有点类似 Java 中 JVM 标记清除算法

什么是 JAVA 的 JVM 标记清除算法？
理解了数组的删除操作就不难理解 JAVA 的 JVM 标记清除算法，两者原理基本一致。它的做法是当有效内存空间不够用时，就会将整个程序暂停，然后进行两项工作：第一是标记(Mark)，第二个是清除(Sweep)。标记的过程就是遍历所有的 GC Roots，然后将 GC Roots 可达的对象标记为存活的对象，大多数主流的虚拟机都是采用 可达性分析算法 判断对象是否存活。清除的过程就是遍历所有对象中没有被标记的对象全部清除掉。当程序运行期间，如果可以使用的内存空间不够时，GC 线程就会被触发并将程序暂停，随后将依旧存活的对象标记一遍，最终再将所有对象中没有被标记的对象清除掉，接下来便将程序恢复运行

总结

数组使用一组连续的内存空间存储一组具有相同数据类型的数据，最大的特点就是支持随机访问，通过下标随机访问的时间复杂度是 O(1)，也是因为这个特性导致插入、删除操作比较低小，平均时间复杂度为 O(n)