数据结构之数组

在计算机科学中，数组数据结构（Array Data Structure），简称数组（Array），是由相同类型的元素（Element）的集合所组成的数据结构，在存储时使用一块连续的存储空间。利用元素的索引（Index）可以计算出该元素对应的存储地址。

根据维度区分，有两种不同的数组，分别为：

• 一维数组；
• 多维数组（数组中的元素为数组），如二维数组，对应于数学上的矩阵概念，可表示为二维矩形格。

数组是计算机科学中最基本的数据结构之一，其他数据结构，比如栈和队列都是由数组衍生出来的。它有多种用途，适用于各种场景。

特点

1. 数组是相同数据类型的元素的集合。
2. 数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放。
3. 数组中的元素通过它在数组中的顺序位置来表示。如 Array[0] 表示名字为 Array 的数组中的第一个元素。

性能

数组数据结构有以下 4 种操作：

• 读取：查看数据结构中某一位置上的数据。对于数组来说，这意味着查看某个索引所指的数据值。
• 查找：从数据结构中找出某个数据值的所在。对于数组来说，这意味着检查其是否包含某个值，如果包含，返回其索引。
• 插入：给数据结构增加一个数据值。对于数组来说，这意味着增加一块儿空间并填入一个值。
• 删除：从数据结构中移除一个数据值。对于数组来说，这意味着把数组中的某个数据项移除。

我们从一个例子讨论，数组的 4 种操作的复杂度：

下面是一个用户的购物清单：

array = ["apples","bananas","cucumbers","dates","elderberries"]

读取

读取的时间复杂度为 O(1)。因为计算机本身就有跳到任一索引位置的能力（通过程序计数器 PC）。

在上面的例子中，如果想要读取索引 2 的值，计算机会执行如下过程：

1. 找到数组的地址。根据数组名称，找到数组的内存地址，即数组开头的地址 1010；
2. 计算元素的地址。由于索引从 0 算起，索引为 2 的元素在数组的第三个格子上，1010+3=1013；
3. 返回元素的内容。一步跳到 1013，获取到 “dates” 这个值，返回。

查找

查找的时间复杂度为 O(n)。因为计算机在查找数组中是否存在某个值时，会先从索引为 0 的位置开始，检查其值，如果不匹配，则继续下一个索引，以此类推，直至找到或返回不存在。

在上面的例子中，如果想要查找 “dates”，计算机会执行如下过程：

1. 找到数组的地址。根据数组名称，找到数组的内存地址，即数组开头的地址 1010；
2. 对元素的值进行匹配。取出索引为 0 的元素，与待匹配的元素“dates”进行比较，匹配结果为 false，索引加 1，继续取索引为 1 的元素进行匹配，以此类推，直至找到或返回不存在。
3. 返回结果。历尽千幸万苦，终于找到了“dates”，它在索引为 3 那里，自此，计算机不用再往后跳了，因为结果已经得到。

插入

插入的时间复杂度为 O(n)。

插入元素分两种情况

• 往数组的末尾插入元素。这种情况下，计算机知道数组的开头的内存地址，也知道数组中包含多少个元素，所以可算出要插入的内存的地址，然后一步跳到那里插入就可以了。

• 在数组的开头或中间插入元素。这种情况下，我们需要移动其他元素以腾出空间，于是得花费额外的步数。假设我们需要在索引为 2 处插入 “figs”，具体情况如下：

  1. "elderberries"右移；
  2. "dates"右移；
  3. "cucembers"右移;
  4. 在索引 2 处插入"figs”;

  整个过程有 4 步，前 3 步都在移动数据，最后 1 步才是真正的插入数据。

最低效（花费最多步数）的插入是插入在数组开头。这时需要把数组所有的元素都往右移。于是，一个含有 n 各元素的数组，其插入数据的最坏情况会花费 n+1 步。

删除

删除的时间复杂度为 O(n)。

删除的过程相当于插入的反向操作。假设，我们要删除索引为 2 的值，即“cucembers”，执行过程如下：

1. 删除 “cucembers”；
2. 将"dates"左移；
3. 将"elderberries"左移；

整个删除过程花了 3 步，其中，第 1 步是真正的删除，剩下的 2 步是移数据去填空格。

不去填空格可以吗？答案是不行。因为数组是通过索引进行读取的，如果存在空格，数组的读取就会受到影响，其次，当频繁更新时，会产生很多空格，这些空格如果不通过填空格的方式进行“回收再利用”，势必会造成很大的空间浪费。

参考资料：

• 《数据结构与算法图解》
• 维基百科
• 百度百科