数据结构——数组

在绝大多数的变成语言中都会有数组这么一种最基础的数据结构,而且基本都是从 0 开始编号的。

为什么要从 0 开始编号而不是 1 呢?

如何实现随机访问

数组,是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据

线性表结构,限制了数组只有前后两个方向。这个时候,再加上连续的内存空间相同的数据类型这两个特点,这就使数组拥有了随机访问的特性。但与此同时,也给数组在删除、插入一个数据的时候带来了麻烦。

假设有一个长度为 10 的 int 类型的数组 int[] a = new int[10],在内存中我们给分配了这样一块内存空间 1000~1039,内存块的首地址 base_address=1000。

计算机是通过内存地址来访问到这块内存里的数据。对于上面数组这块内存,我们很容易通过下面这个公式,使用下标访问任意一个数组元素:

a[i]_address = base_address + i * data_type_size

data_type_size 表示数组中每个元素的大小,所举的例子中是 int 类型,所以 data_type_size 大小就为 4 个字节。

通过这个公式,我们很容易就知道了为什么数组能实现随机访问。另外,如果我们要访问第一个元素的时候,i 的值为 0,这就是为什么下标基本都是从 0 开始的原因。

可能有人会说,把公式变成 a[i]_address = base_address + (i - 1) * data_type_size,这样下标不就可以按照人类数数的习惯,直接从 1 开始了吗。但这会有一个小问题,就是多了的 -1 操作是有效率损耗的,毕竟多做了一步操作。

插入操作

上面我们提到,由于数组的连续特性,导致插入操作会比较麻烦,有什么改进的办法吗?

比如我们现在要在第 k 个位置插入一个元素,需要把 k 位以后的所有数据都依次往后挪。假如一开始一共有 n 个元素,那么需要移动 n-k 个元素。最好的情况是直接在数组末尾增加一个元素,此时的时间复杂度很明显是 O(1)。最坏情况就是在数组开头插入一个元素,这时时间复杂度为 O(n)。因为每个位置插入的元素的概率是一样的,所以平均时间复杂度: (1+2+..+n)/n,为 O(n) 的时间复杂度。

如果我们对于数组元素的顺序没有要求,那么在 k 位置插入元素可以这么优化:先把原来第 k 位的元素移动到数组末尾,然后在 k 位插入新的数据。这样能把时间复杂度将为 O(1)。快排中就用到了这个思想。

删除操作

删除操作和插入操作类似,为了内存的连续性,也需要搬迁数据。

如果删除的是末尾数据,则是最好的情况,时间复杂度为 O(1);如果删除的是头部数据,则是最坏情况,时间复杂度为 O(n);平均复杂度同样也是 O(n)。

在某些特定的场景下,如果对数组数据的连续性没有要求,那么可以将多次的删除操作合并起来。大概流程是这样的:当我们想要删除某个元素的时候,可以先把这个元素做个标记,表示已经删除了,但实际还未删除(软删除操作),然后等攒到一定数量或者存储空间不够之后之后再统一一起删除。

这个听起来不就是标记清除法的核心思想吗。算法与数据结构的魅力就在于此,其背后的思想和处理技巧这些东西才是最有价值的。