第1章 数据结构为何重要

数据是一个广义的术语，可以指代各种类型的信息，包括最基本的数字和字符串。

数据结构则是指数据的组织形式。数据结构不只是用于组织数据，它还极大地影响着代码的运行速度。

1.1 基础数据结构：数组

数组是计算机科学中最基本的数据结构之一。

array = [“apples”, “bananas”, “cucumbers”, “dates”, “elderberries”]

这就是一个数组，它刚好包含5个字符串，每个代表从超市买的食物。我们会用一些名为索引的数字来标识每项数据在数组中的位置。在大多数的编程语言中，索引是从0算起的，因此在这个例子中，"apples"的索引为0，"elderberries"的索引为4。

计算机的内存可以被看成一堆格子，其中有些格子有数据，有些则是空白。当程序声明一个数组时，它会先划分出一些连续的空格子以备使用。换句话说，如果你想创建一个包含5个元素的数组，计算机就会找出5个排成一行的空格子，将其当成数组。内存中的每个格子都有各自的地址，就像街道地址，不过内存地址就只用一个普通的数字来表示。而且，每个格子的内存地址都比前一个大1。购物清单数组的索引和内存地址，如下图所示。

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

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

**操作的速度，并不按时间计算，而是按步数计算。**按步数计算可以脱离硬件的影响。操作的速度，也常被称为时间复杂度。在本书中，我们会提到速度、时间复杂度、效率、性能，但它们其实指的都是步数。

1.1.1 读取

读取即查看数组中某个索引所指的数据值。因为计算机本身就有跳到任一索引位置的能力，所以只需要一步就够了。

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

(1) 计算机可以一步就跳到任意一个内存地址上。

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

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

1.1.2 查找

对于数组来说，查找就是检查它是否包含某个值，如果包含，给出其索引。

如果要在在数组中查找"dates"，只能一步一步地检查整个数组，计算机会先从索引0开始，检查其值，如果不匹配，则继续下一个索引，以此类推，直至找到为止。

这种逐个格子去检查的做法，就是最基本的查找方法——线性查找。在数组上进行线性查找最多要多少步呢？如果我们要找的值刚好在数组的最后一个格子里，那么计算机从头到尾检查每个格子，会在最后才找到。同样，如果我们要找的值并不存在于数组中，那么计算机也还是得查遍每个格子，才能确定这个值不在数组中。于是一个N格的数组，其线性查找的最多步数是N（N可以是任何自然数）。

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

1.1.3 插入

往数组里插入一个新元素的速度，取决于你想把它插入到哪个位置上。假设我们想要在购物清单的末尾插入"figs"，因为计算机知道数组开头的内存地址，也知道数组包含多少个元素，所以可以算出要插入的内存地址，然后一步跳到那里插入就行了。最低效（花费最多步数）的插入是插入在数组开头。因为这时候需要把数组所有的元素都往右移。于是，一个含有N个元素的数组，其插入数据的最坏情况会花费N + 1步。即插入在数组开头，导致N次移动，加上一次插入。

1.1.4 删除

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

删除本身只需要1步，但接下来需要额外的步骤将数据左移以填补删除所带来的空隙。跟插入一样，删除的最坏情况就是删掉数组的第一个元素。因为数组不允许空元素，当索引0空出，那么剩下的所有元素都要往左移去填空。对于含有N个元素的数组，删除操作最多需要N步。

1.2 集合：一条规则决定性能

集合是一种不允许元素重复的数据结构。

集合是有不同形式的，但现在我们只讨论基于数组的那种。这种集合跟数组差不多，都是一个普通的元素列表，唯一的区别在于，集合不允许插入重复的值。总之，集合就是一个带有“不允许重复”这种简单限制的数组。而该限制也导致它在4种基本操作中有1种与数组性能不同。

1. 集合的读取跟数组的读取完全一样，计算机只要一步就能获取指定索引上的值。
2. 集合的查找也跟数组的查找无异，需要N步去检查某个值在不在集合当中。
3. 删除也是，总共需要N步去删除和左移填空。
4. 但插入就不同了。先看看在集合末尾的插入。对于数组来说，末尾插入是最高效的，它只需要1步。而对于集合，计算机得先确定要插入的值不存在于其中（因为集合不允许重复值）。于是每次插入都要先来一次查找。在N个元素的集合中进行插入的最好情况（在集合的末尾插入）需要N + 1步——N步去确认被插入的值不在集合中，加上最后插入的1步。最坏的情况则是在集合的开头插入，这时计算机得检查N个格子以保证集合不包含那个值，然后用N步来把所有值右移，最后再用1步来插入新值。总共2N + 1步。

在需要保证数据不重复的场景中，集合是非常重要的。但如果没有这种需求，那么选择插入比集合快的数组会更好一些。具体哪种数据结构更合适，要根据实际应用场景而定。了解这些非常重要，因为数据结构的性能差异会直接造成程序的性能差异。

1.3 总结

理解数据结构的性能，关键在于分析操作所需的步数。采取哪种数据结构将决定你的程序是能够承受住压力，还是崩溃。不同的数据结构有不同的时间复杂度，类似地，不同的算法（即使是用在同一种数据结构上）也有不同的时间复杂度。既然我们已经学会了时间复杂度的分析方法，那么就可以用它来对比各种算法，找出能够发挥代码极限性能的那个。