思考并回答以下问题：

数据结构是什么？为什么重要？举几个数据结构。
内存是什么样子的？
数组读取为什么快？
什么是线性查找？在含有N个元素的数组上进行线性查找最多要多少步呢？
一个含有N个元素的数组，其插入数据的最好情况会花费多少步？最坏呢？
一个含有N个元素的数组，其删除数据的最好情况会花费多少步？最坏呢？
集合作为不重复的数组在插入上与数组有什么区别？
什么是时间复杂度？

本章涵盖：

基础数据结构：数组
- 读取
- 查找
- 插入
- 删除
集合：一条规则决定性能
总结

哪怕只写过几行代码的人都会发现，编程基本上就是在跟数据打交道。计算机程序总是在接收数据、操作数据或返回数据。不管是求两数之和的小程序，还是管理公司的企业级软件，都运行在数据之上。

数据是一个广义的术语，可以指代各种类型的信息，包括最基本的数字和字符串。在经典的“Hello World!”这个简单程序中，字符串“Hello World!”就是一条数据。事实上，无论是多么复杂的数据，我们都可以将其拆成一堆数字和字符串来看待。

数据结构则是指数据的组织形式。看看以下代码。

x = "Hello!"
y = "How are you"
z = "today?"

print(x + y + z)

这个非常简单的程序把3条数据串成了一句连贯的话。如果要描述该程序中的数据结构，我们会说，这里有3个独立的变量，分别引用着3个独立的字符串。

但数据结构不只是用于组织数据，它还极大地影响着代码的运行速度。因为数据结构不同，程序的运行速度可能相差多个数量级。如果你写的程序要处理大量的数据，或者要让数千人同时使用，那么你采用何种数据结构，将决定它是能够运行，还是会因为不堪重负而崩溃。

一旦对各种数据结构有了深刻的理解，并明白它们对程序性能方面的影响，你就能写出快速而优雅的代码，从而使软件运行得快速且流畅。当然，你的编程技能也会更上一层楼。

本章接下来将会分析两种数据结构：数组和集合。它们从表面上看好像差不多，但通过即将介绍的分析工具，你将会观察到它们在性能上的差异。

基础数据结构：数组

数组是计算机科学中最基本的数据结构之一。如果你用过数组，那么应该知道它就是一个含有数据的列表。它有多种用途，适用于各种场景，下面就举个简单的例子。

一个允许用户创建和使用购物清单的食杂店应用软件，其源代码可能会包含以下的片段。

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

这就是一个数组，它刚好包含5个字符串，每个代表我会从超市买的食物。

此外，我们会用一些名为索引的数字来标识每项数据在数组中的位置。

在大多数的编程语言中，索引是从0算起的，因此在这个例子中，“apples”的索引为0，“elderberries”的索引为4，如下所示。

若想了解某个数据结构（例如数组）的性能，得分析程序怎样操作这一数据结构。

一般数据结构都有以下4种操作（或者说用法）。

读取：查看数据结构中某一位置上的数据。对于数组来说，这意味着查看某个索引所指的数据值。例如，查看索引2上有什么食品，就是一种读取。
查找：从数据结构中找出某个数据值的所在。对于数组来说，这意味着检查其是否包含某个值，如果包含，那么还得给出其索引。例如，检查“dates”是否存在于食品清单之中，给出其对应的索引，就是一种查找。
插入：给数据结构增加一个数据值。对于数组来说，这意味着多加一个格子并填入一个值。例如，往购物清单中多加一项“figs”，就是一种插入。
删除：从数据结构中移走一个数据值。对于数组来说，这意味着把数组中的某个数据项移走。例如，把购物清单中的“bananas”移走，就是一种删除。

本章我们将会研究这些操作在数组上的运行速度。

同时，我们也将学到本书的第一个重要理论：操作的速度，并不按时间计算，而是按步数计算。

为什么呢？

因为，你不可能很绝对地说，某项操作要花5秒。它在某台机器上要跑5秒，但换到一台旧一点的机器，可能就要多于5秒，而换到一台未来的超级计算机，运行时间又将显著缩短。所以，受硬件影响的计时方法，非常不可靠。

然而，若按步数来算，则确切得多。如果A操作要5步，B操作要500步，那么我们可以很肯定地说，无论是在什么样的硬件上对比，A都快过B。因此，衡量步数是分析速度的关键。

此外，操作的速度，也常被称为时间复杂度。在本书中，我们会提到速度、时间复杂度、效率、性能，但它们其实指的都是步数。

事不宜迟，我们现在就来探索上述4种操作方式在数组上要花多少步。

读取

首先看看读取，即查看数组中某个索引所指的数据值。

这只要一步就够了，因为计算机本身就有跳到任一索引位置的能力。在 [“apples”, “bananas”, “cucumbers”, “dates”, “elderberries”]的例子中，如果要查看索引2的值，那么计算机就会直接跳到索引2，并告诉你那里有“cucumbers”。

计算机为什么能一步到位呢？原因如下。

计算机的内存可以被看成一堆格子。下图是一片网格，其中有些格子有数据，有些则是空白。

当程序声明一个数组时，它会先划分出一些连续的空格子以备使用。换句话说，如果你想创建一个包含5个元素的数组，计算机就会找出5个排成一行的空格子，将其当成数组。

内存中的每个格子都有各自的地址，就像街道地址，例如大街123号。不过内存地址就只用一个普通的数字来表示。而且，每个格子的内存地址都比前一个大1，如下图所示。

购物清单数组的索引和内存地址，如下图所示。

计算机之所以在读取数组中某个索引所指的值时，能直接跳到那个位置上，是因为它具备以下条件。

(1)计算机可以一步就跳到任意一个内存地址上。（就好比，要是你知道大街123号在哪儿，那么就可以直奔过去。）

(2)数组本身会记有第一个格子的内存地址，因此，计算机知道这个数组的开头在哪里。

(3)数组的索引从0算起。

回到刚才的例子，当我们叫计算机读取索引3的值时，它会做以下演算。

(1)该数组的索引从0算起，其开头的内存地址为1010。

(2)索引3在索引0后的第3个格子上。

(3)于是索引3的内存地址为1013，因为1010 + 3 = 1013。

当计算机一步跳到1013时，我们就能获取到“dates”这个值了。

所以，数组的读取是一种非常高效的操作，因为它只要一步就好。一步自然也是最快的速度。这种一步读取任意索引的能力，也是数组好用的原因之一。

如果我们问的不是“索引3有什么值”，而是“”dates”在不在数组里”，那么这就需要进行查找操作了。下面我们就来看看。

查找

如前所述，对于数组来说，查找就是检查它是否包含某个值，如果包含，还得给出其索引。那么，我们就试试在数组中查找“dates”要用多少步。

对于我们人来说，可以一眼就看到这个购物清单上的“dates”，并数出它的索引为3。但是，计算机并没有眼睛，它只能一步一步地检查整个数组。

想要查找数组中是否存在某个值，计算机会先从索引0开始，检查其值，如果不匹配，则继续下一个索引，以此类推，直至找到为止。

我们用以下图来演示计算机如何从购物清单中查找“dates”。

首先，计算机检查索引0。

因为索引0的值是“apples”，并非我们所要的“dates”，所以计算机跳到下一个索引上。

索引1也不是“dates”，于是计算机再跳到索引2。

但索引2的值仍不匹配，计算机只好再跳到下一格。

啊，真是千辛万苦，我们找到“dates”了，它就在索引3那里。自此，计算机不用再往后跳了，因为结果已经得到。

在这个例子中，因为我们检查了4个格子才找到想要的值，所以这次操作总计是4步。

这种逐个格子去检查的做法，就是最基本的查找方法--线性查找。第2章我们还会学习另一种查找方法。

但在那之前，我们再思考一下，在数组上进行线性查找最多要多少步呢？

如果我们要找的值刚好在数组的最后一个格子里（如本例的elderberries），那么计算机从头到尾检查每个格子，会在最后才找到。同样，如果我们要找的值并不存在于数组中，那么计算机也还是得查遍每个格子，才能确定这个值不在数组中。

于是，一个5格的数组，其线性查找的步数最大值是5，而对于一个500格的数组，则是500。

以此类推，一个N格的数组，其线性查找的最多步数是N（N可以是任何自然数）。

可见，无论是多长的数组，查找都比读取要慢，因为读取永远都只需要一步，而查找却可能需要多步。

接下来，我们再研究一下插入，准确地说，是插入一个新值到数组之中。

插入

往数组里插入一个新元素的速度，取决于你想把它插入到哪个位置上。

假设我们想要在购物清单的末尾插入“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次移动，加上一次插入。

最后要说的“删除”，则相当于插入的反向操作。

删除

数组的删除就是消掉其某个索引上的数据。

我们找回最开始的那个数组，删除索引2上的值，即“cucumbers”。

第1步：删除“cucumbers”。

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

第2步：将”dates”左移。

第3步：将”elderberries”左移。

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

所以，删除本身只需要1步，但接下来需要额外的步骤将数据左移以填补删除所带来的空隙。

跟插入一样，删除的最坏情况就是删掉数组的第一个元素。因为数组不允许空元素，当索引0空出，那么剩下的所有元素都要往左移去填空。

对于含有5个元素的数组，删除第一个元素需要1步，左移剩余的元素需要4步。而对于500个元素的数组，删除第一个元素需要1步，左移剩余的元素需要499步。可以推出，对于含有N个元素的数组，删除操作最多需要N步。

既然学会了如何分析数据结构的时间复杂度，那就可以开始探索各种数据结构的性能差异了。了解这些非常重要，因为数据结构的性能差异会直接造成程序的性能差异。

下一个要介绍的数据结构是集合，它跟数组似乎很像，甚至让人以为就是同一种东西。然而，我们将会看到它跟数组在性能上是有区别的。

集合：一条规则决定性能

来看看另一种数据结构：集合。它是一种不允许元素重复的数据结构。

其实集合是有不同形式的，但现在我们只讨论基于数组的那种。这种集合跟数组差不多，都是一个普通的元素列表，唯一的区别在于，集合不允许插入重复的值。

要是你想往集合[“a”, “b”, “c”]再插入一个“b”，计算机是不会允许的，因为集合中已经有“b”了。

集合就是用于确保数据不重复。

如果你要创建一个线上电话本，你应该不会希望相同的号码出现两次吧。如果这个电话本程序用集合来处理，那就不会搞出这种麻烦了。

总之，集合就是一个带有“不允许重复”这种简单限制的数组。而该限制也导致它在4种基本操作中有1种与数组性能不同。

下面就来分析读取、查找、插入和删除在基于数组的集合上表现如何。

集合的读取跟数组的读取完全一样，计算机只要一步就能获取指定索引上的值。如之前解释的那样，这是因为计算机知道集合开头的内存地址，所以能够一步跳到集合的任意索引。

集合的查找也跟数组的查找无异，需要N步去检查某个值在不在集合当中。删除也是，总共需要N步去删除和左移填空。

但插入就不同了。先看看在集合末尾的插入。对于数组来说，末尾插入是最高效的，它只需要1步。

而对于集合，计算机得先确定要插入的值不存在于其中--因为这就是集合：不允许重复值。于是每次插入都要先来一次查找。

假设我们的购物清单是一个集合--用集合还是不错的，毕竟你不会想买重复的东西。如果当前集合是[“apples”, “bananas”, “cucumbers”, “dates”, “elderberries”]，然后想插入“figs”，那么就需要做一次如下的查找。

第1步：检查索引0有没有“figs”。

没有，不过说不定其他索引会有。为了在真正插入前确保它不存在于任何索引上，我们继续。

第2步：检查索引1。

第3步：检查索引2。

第4步：检查索引3。

第5步：检查索引4。

直到检查完整个集合，才能确定插入“figs”是安全的。于是，到最后一步。

第6步：在集合末尾插入“figs”。

在集合的末尾插入也属于最好的情况，不过对于一个含有5个元素的集合，你仍然要花6步。因为，在最终插入的那一步之前，要把5个元素都检查一遍。

换句话说，在N个元素的集合中进行插入的最好情况需要N+1步--N步去确认被插入的值不在集合中，加上最后插入的1步。

最坏的情况则是在集合的开头插入，这时计算机得检查N个格子以保证集合不包含那个值，然后用N步来把所有值右移，最后再用1步来插入新值。总共2N+1步。

这是否意味着因为它的插入比一般的数组慢，所以就不要用了呢？当然不是。在需要保证数据不重复的场景中，集合是非常重要的。但如果没有这种需求，那么选择插入比集合快的数组会更好一些。具体哪种数据结构更合适，当然要根据你的实际应用场景而定。

总结

理解数据结构的性能，关键在于分析操作所需的步数。采取哪种数据结构将决定你的程序是能够承受住压力，还是崩溃。本章特别讲解了如何通过步数分析来判断某种应用该选择数组还是集合。

不同的数据结构有不同的时间复杂度，类似地，不同的算法（即使是用在同一种数据结构上）也有不同的时间复杂度。既然我们已经学会了时间复杂度的分析方法，那么现在就可以用它来对比各种算法，找出能够发挥代码极限性能的那个。这正是下一章所要讲的。