数据结构为什么如此重要？( 三 ) _数据结构

于是，一个5 格的数组，其线性查找的步数最大值是5，而对于一个500 格的数组，则是500 。
以此类推，一个N 格的数组，其线性查找的最多步数是N（N 可以是任何自然数）。
可见，无论是多长的数组，查找都比读取要慢，因为读取永远都只需要一步，而查找却可能需要多步。
接下来，我们再研究一下插入，准确地说，是插入一个新值到数组之中。
3.插入
往数组里插入一个新元素的速度，取决于你想把它插入到哪个位置上。
假设我们想要在购物清单的末尾插入"figs" 。那么只需一步。因为之前说过了，计算机知道数组开头的内存地址，也知道数组包含多少个元素，所以可以算出要插入的内存地址，然后一步跳到那里插入就行了。图示如下。

文章插图
但在数组开头或中间插入，就另当别论了。这种情况下，我们需要移动其他元素以腾出空间，于是得花费额外的步数。
例如往索引2 处插入"figs"，如下所示。

文章插图
为了达到目的，我们必须先把"cucumbers"、"dates"和"elderberries"往右移，以便空出索引2 。而这也不是一步就能移好，因为我们首先要将"elderberries"右移一格，以空出位置给"dates"，然后再将"dates"右移，以空出位置给"cucumbers"，下面来演示这个过程。
第1 步："elderberries"右移。

文章插图
第2 步："date"右移。

文章插图
第3 步："cucembers"右移。

文章插图
第4 步：至此，可以在索引2 处插入"figs"了。

文章插图
如上所示，整个过程有4 步，开始3 步都是在移动数据，剩下1 步才是真正的插入数据。
最低效（花费最多步数）的插入是插入在数组开头。因为这时候需要把数组所有的元素都往右移。于是，一个含有N 个元素的数组，其插入数据的最坏情况会花费N + 1 步。即插入在数组开头，导致N 次移动，加上一次插入。
最后要说的“删除”，则相当于插入的反向操作。
4.删除
数组的删除就是消掉其某个索引上的数据。
我们找回最开始的那个数组，删除索引2 上的值，即"cucumbers" 。
第1 步：删除"cucumbers" 。

文章插图
虽然删除"cucumbers"好像一步就搞定了，但这带来了新的问题：数组中间空出了一个格子。因为数组中间是不应该有空格的，所以，我们得把"dates"和"elderberries"往左移。
第2 步：将"dates"左移。

文章插图
第3 步：将"elderberries"左移。

文章插图
结果，整个删除操作花了3 步。其中第1 步是真正的删除，剩下的2 步是移数据去填空格。
所以，删除本身只需要1 步，但接下来需要额外的步骤将数据左移以填补删除所带来的空隙。
跟插入一样，删除的最坏情况就是删掉数组的第一个元素。因为数组不允许空元素，当索引0 空出，那么剩下的所有元素都要往左移去填空。
对于含有5 个元素的数组，删除第一个元素需要1 步，左移剩余的元素需要4 步。而对于500个元素的数组，删除第一个元素需要1 步，左移剩余的元素需要499 步。可以推出，对于含有N个元素的数组，删除操作最多需要N 步。
既然学会了如何分析数据结构的时间复杂度，那就可以开始探索各种数据结构的性能差异了。了解这些非常重要，因为数据结构的性能差异会直接造成程序的性能差异。
下一个要介绍的数据结构是集合，它跟数组似乎很像，甚至让人以为就是同一种东西。然而，我们将会看到它跟数组在性能上是有区别的。
集合：一条规则决定性能来看看另一种数据结构：集合。它是一种不允许元素重复的数据结构。
其实集合是有不同形式的，但现在我们只讨论基于数组的那种。这种集合跟数组差不多，都是一个普通的元素列表，唯一的区别在于，集合不允许插入重复的值。