算法和数据结构-初级 | 第六课：数据结构之数组和链表(上)

2018-10-01 本文已影响143人程序员联盟

程序 = 数据结构 + 算法

作者谢恩铭转载请注明出处
公众号「程序员联盟」（微信号：ProgrammerLeague ）
原文：https://www.jianshu.com/p/25db724b183a

《算法和数据结构-初级》全系列

内容简介

前言
数组和链表的定义
数组和链表的基本操作
第七课预告

1. 前言

上一课 [算法和数据结构-初级 | 第五课：算法复杂度实践(https://www.jianshu.com/p/060ef52580af) 中，我们做了一些小练习。相信对于算法复杂度，大家应该已经有了不错的理解。我们之后的课程里，算法复杂度也会是“常驻嘉宾”。

既然我们在第一课有略微介绍数据结构，也说算法和数据结构是密不可分的，现在应该是时候请出本课程第二个重要角色：“数据结构” 了。

这一课，我们将学习两个极为常见的数据结构：数组和链表，也会分析这两个数据结构的常用操作的算法复杂度。

我们暂时不会介绍很复杂的概念，会带大家轻松地来慢慢揭开数据结构的面纱。但这一课的知识点还是挺多的，也很有意思，对后续课程会很有用。

读者：“小编，你就说哪一课没有用吧，真的是...”
小编：“是，是。你那么好看，你说什么都对。”

2. 数组和链表的定义

数据结构的主要用途是存储程序员之后想要访问的元素。程序员创建了数据结构，当然要使用它们（似乎是句废话，不过，确实是句废话...），我们把数据结构的可能的使用方式称为“操作”（operation）。

例如，对于数据结构常见的一种操作是“读取”（read）：我们想要获取存储在数据结构中的元素。

其他还有许多操作，例如“添加”（add）/ “插入”（insert）：将新元素添加到数据结构中；或“删除”（delete）：从数据结构中删除元素。

并非所有数据结构都允许相同的操作。更重要的是，即使是同一个操作，对于不同的数据结构，操作的“成本”也不尽相同。

例如，在某些数据结构中，添加/插入元素的操作非常快，而在其他数据结构中添加操作却很困难，甚至可能要求重组此数据结构。

你看到了“操作”，还有“成本”（快不快，困不困难），你想到了什么呢？是的，就是我们之前学习的算法复杂度。在我们这门课程中，我们就用复杂度（Complexity）来度量操作的“成本”。对于我们所用的每一个数据结构，我们都尝试着去了解对其执行的操作的复杂度。

我们为什么需要了解操作数据结构的“成本”呢？有两方面的好处：

当我们的算法使用一种特定的数据结构时，我们需要知道所执行的操作的“成本”（用复杂度来度量），以便进行算法的整体复杂度的评估。更重要的是，当我们对算法所需要的操作有了深入的理解时，我们可以选择最合适的数据结构，使得操作的“成本”最低。
实际上，大多数人使用算法的时候，是用的比较简单的算法（不是基于很复杂的操作），因此选择好的数据结构可以对程序的性能产生至关重要的影响。

数组

数组应该是最常见的数据结构了，至少在 C 语言和从 C语言派生或受其启发的编程语言（比如 C++，Java，PHP，等等）中。

还记得以前初学编程的时候，最先接触的数据结构大概就是数组（那段入门编程的疼痛又美好的时光啊）。如果想学习 C 语言以便入门编程，欢迎看我的系列教程：C语言探索之旅。

数组的原理非常简单：可以想象我们将元素存储在一个个“框”中（这些“框”是内存中的片段的抽象），每个“框”都标有数字（通常称为“下标”/“索引”（index））。我们可以使用下标来访问数组的特定元素。

数组的下标是连续的整数。在大多数编程语言中，我们都认为数组的下标从 0 开始。因此第一个元素的下标是 0，第二个元素的下标是 1，依此类推。如果 N 是数组的大小（元素个数），那么数组的最后一个元素的下标是 N - 1。访问不存在的下标位置会引发常见的错误。

拥有 7 个元素的数组

通常，我们认为数组的大小是已知的（程序员在申请创建数组时必须知道数组的大小）。

创建数组的时间取决于编程语言。一般来说，创建数组时，会在数组的每个“框”中存入一个默认值，这个赋值操作的执行时间和数组的大小成正比（如果数组大小是 N，那么创建数组时的赋值操作所需的时间复杂度是 O(N)）。

但是，在某些编程语言中，可以更快地创建“不需要初始化”的数组（每个“框”里的值是未知的，没有赋初值的操作）。但这种做法可能会有危险，因为这样创建的数组中的值可能没有任何意义。

在本课程中，我们统一认为数组在创建时都会被初始化，因此创建数组的时间复杂度是 O(N)（N 是数组大小）。

链表

链表（Linked List，有时也简写为 List）是一种极其常用的数据结构。特别地，它在 Lisp 语言（Lisp 语言的名字 Lisp 就是 LISt Processor 的缩写，表示“链表处理器”，可见链表在 Lisp 语言中的地位）中发挥了重要作用，并且仍然存在于受 Lisp 语言启发的其他编程语言中。

为了正确描述链表，我不得不稍微偏离纯粹的算法层面的考虑，为的是更详细地说明编程语言是如何管理数据结构的。
我将使用独立于编程语言（语言无关性）的一种描述：我们将讨论具有一个或多个字段/域（field）的单元/单元格（cell）。
你可以把单元格想成一组可以存储数据的“盒子”，每个“盒子”可以通过名称来访问（称为字段的名称，就好比一个表格里的字段）。
例如，我们可以描述一种结构，它将一个人的电话号码和地址存储在拥有三个字段的单元格里，三个字段分别是“人名”、“电话号码”和“地址”。想象一下，是不是和表格类似：

存有人名、电话、地址三个字段的表格/单元格（抽象）

法国的火警电话是 15。

根据你所用的编程语言，单元格将具有不同的形式：C 语言中的 struct（结构体），Java / C++ / Python 等面向对象编程语言中的 object（对象），等等。我们不会讨论这些具体形式的内存组织的底层细节，但我们需要有一个共同的抽象模型以方便讨论。

我们进一步认为，单元格的创建（和销毁）（如果它具有固定数量的字段）以及对一个字段的读取或修改是在恒定时间内完成的。

现在我们来看链表的定义。链表可以是：

空链表：不含任何单元格。
双字段的单元格：一个包含元素的 head（英语“头部”的意思）字段；以及一个包含另一个链表的地址的 tail（英语“尾部”的意思）字段。

换句话说，链表要么是空的，要么是跟着/链接着另一个链表的一个单元。这个定义很有趣，因为它是递归的：使用了“链表”（Linked List，也就是“链接起来的列表”）这个词本身。可以说：链表的定义使用了链表的定义！但是，就像递归程序并非都是无限循环一样，这个定义是非常正确的（你会在之后的使用中体会到）。

链表可以是空的链表（有 0 个单元格），或一个链接着空链表的单元格（1 个单元格），或一个链接着一个链接着空链表（好拗口…）的单元格（2 个单元格），等等。下面展示的是包含三个单元格的链表：

包含三个单元格的链表

我们会说 head 字段中的元素是链表的头部，而 tail 字段中的（另一个）链表是它的尾部。链表的尾部包含除了第一个元素外的其他所有元素。例如，链表 [1; 2; 3] 的尾部是 [2; 3]。

当然，空链表既没有头部也没有尾部：尝试访问其中任意一个字段都会导致错误。

实际上，链表这种结构有很多变种。我在这里介绍最简单的，它也被称为“单链表”。因为链表里的每个单元格只包含一个元素（在 head 字段里）和指向下一个单元格的“箭头”（在 tail 字段里）。

如果有 C/C++ 等语言基础，就会知道这个“箭头”其实就是指针，当然我们不会给大家讲解关于指针的具体概念，大家有兴趣可以去了解（C语言探索之旅 | 第二部分第二课：进击的指针，C语言的王牌！）。这里我们还是着眼于这个抽象的数据结构。

你可以想象这些“箭头”形成了链接，这也是链表这个名称的由来：链接起来的列表（Linked List）。

链表也可以有其他的结构，这样的结构在某些情况下会非常有用。例如，我们可以给每个单元格配备两个箭头，一个指向前一个单元格，一个指向后一个单元格，这就是双向链表。双向链表也是常见的数据结构：

双向链表

实现：
链表的表示在很大程度上取决于编程语言。在函数式编程语言（functional programming language）中，这种类型可能已经被定义了，你直接使用即可。例如在自带链表这个数据结构的 Lisp 语言中：

(list 'a' 'b' 'c')

上面是 Lisp 中定义一个包含 a，b，c 三个元素的链表，示意图如下：

包含 a，b，c 三个元素的链表

在 C 语言中，链表却没有在语言里直接被定义，所以我们得自己去定义链表这样一个数据结构。我们通常会用经典的实现方法：用结构体来构建单元格，用 NULL 指针来代表空链表。例如：

struct list
{
    int value;   // head 字段里的值
    struct list *next;  // tail 字段，包含指向下一个链表（单元格）的指针
};
typedef struct list List;  // 用 typedef 给 list 这个结构体取个别名 List

然后，我们就可以将链表表示为指向单元格的指针，例如：

List *myList;

在 C语言中，我们需要手动分配和释放内存，因此还需要一个释放链表中所有单元格的函数。例如：

void freeList(List *list)
{
    while (list != NULL) { /* 只要链表不是空的 */
        List *cell = list;  // 取到当前的单元格（用 cell 指针来存储）
        list = list->next; // 将链表指针指向下一个单元格
        free(cell);  // 释放当前单元格（cell 指针）
    }
}

在 while 循环的每个阶段，我们将链表的头部存储在 cell 变量中。我们在链表中向下一个单元格移动（list = list->next;）（list 指针指向链表的尾部，也就是下一个单元格（链表）），然后我们释放当前的单元格 cell。我们必须使用 cell 这个中间变量，因为如果我们直接执行 free(list) ，那么 list->next 这个指令将毫无意义（因为 list 已经被删除了），我们就不能移动到链表的后续部分了。

3. 一些基本操作

添加 / 删除

从数组或链表中添加或删除项目的最简单方法是什么？

对于一个链表，这两个操作是比较简单的（我们暂时认为添加和删除操作只在链表的头部进行）：

要删除链表的首元素（第一个单元格的 head 字段里包含的元素），只需用它的 tail 尾部（包含接下去所有元素的子链表）来替换当前链表。
要向头部添加元素，只需创建一个新单元格，将此元素放在新单元格的 head 字段中，将初始（旧）链表放在新单元格的 tail 字段中，如下图：

链表头部添加新元素

这两种操作（删除和添加）都在恒定的时间（删除操作就是读取一个字段（tail 字段）；添加操作就是创建一个新单元格）内完成，因此时间复杂度是 O(1)。

实际上，在链表头部添加新元素的操作（用新元素和旧链表来构建新链表），是操作链表的基础。
这个操作甚至还有一个特定的术语：cons。cons 这个动词只存在于信息技术领域。
如果你有 Lisp 语言的基础，那么你就会知道 cons 其实就是 Lisp 中的 constructor（构造器）的动词形式 construct（构造）的缩写。
因此我们可以重新给链表做一个定义：要么是一个空链表；要么是一个链表的一个 cons（构造）。
很有意思吧，你一旦入门编程，就会发现很多知识点都是融会贯通的。

实现：
对于链表已经被定义好的编程语言，定义 cons 操作比较容易。在 Lisp 语言中，你甚至可以直接使用。例如：

(cons y L)

上面的 Lisp 语句中就使用了 cons 函数，其中 y 是一个 Lisp 对象（对象也可以是一个链表，就相当于我们上面说到的新单元格），L 是一个已经存在的链表（就相当于我们上面说到的旧链表）。函数 cons 会将 y 链接到 L 的头部从而构建一个新的链表。

如果语言中没有自带的链表数据结构，你必须使用自己定义的类型，比如我们之前用 C 语言的结构体定义了 List 这个链表结构。在 C 语言中，cons 操作（函数）可以定义如下：

List *cons(int value, List *list)
{
    List *cell = malloc(sizeof(List)); // 构建一个新的单元格（链表的指针）
    if (NULL == cell) { // 如果 cell 的内存没有分配成功
      exit(EXIT_FAILURE);
    }
    cell->value = value;  // 为新单元格的 head 字段里的元素赋值
    cell->next = list;    // 新单元格的 tail 字段指向旧链表
    return cell;  // 返回新的链表
}

对于数组来说，添加新元素比较麻烦。我们知道数组的大小是预先固定的，不可能添加元素（因为内存中在数组的边缘没有可用空间能够扩大它）。

添加一个（或多个）元素的安全的方法是另外创建一个更大的数组，它包含了足够的空间，能够容纳旧数组的所有元素和要添加的新元素。先把旧数组的所有元素复制到新数组里，再将新元素添加到新数组。这种操作的时间复杂度是 O(N)（其中 N 是插入新元素前的数组大小）。

类似地，数组的大小是预先固定的，不能从中删除元素。

在某些编程语言中，可以尝试在某些情况下即时调整数组的大小，或者删除数组的开头或结尾的元素。但是这样做仍然挺危险，所以我们在本课程中不会考虑对数组的这些操作。

大小

如果要计算数组和链表这两种数据结构的大小（包含元素的数目）：

对于数组，这很简单。我们通常认为数组的大小是已知的，所以不需要计算就可以获得它：它是一个时间复杂度为 O(1) 的操作。

对于链表，我们通常不知道它的大小（特别是如果我们刚刚在链表中添加或删除了单元格的话）。要计算链表的大小，我们可以使用以下算法：

如果是空链表，则其大小为 0。
如果链表不是空的，那么我们计算 tail（尾部）字段指向的链表的大小，再加 1 即可（用了递归的理念）。

因此，我们将遍历链表，直到我们的指针抵达空链表，对每一个遍历过的单元格，我们都将要计算的链表的大小数目加 1。此方法非常有效，但需要遍历整个链表，因此时间复杂度是 O(N)（N 是链表的大小）。

其实链表也可以像数组一样，在这种结构本身里存储链表的大小，而不必每次都计算它：除了 head 和 tail 这两个字段之外，我们可以给链表的单元格添加一个字段 size（英语“大小/尺寸”的意思），它包含链表的大小。
这种方法的问题是，cons（构造）操作的成本将变得更加高昂：当我们要给链表添加新元素时，首先必须像以前那样把新的元素和旧链表相连，接着需要访问旧链表的第一个单元格，读取旧链表的大小 N，最后将 N + 1 放入新单元格的 size 字段中。
这只增加了一个步骤（更准确地说是：两次单元格的读取，一次加法，和一次字段初始化），因此操作的时间复杂度是 O(1)，但这仍然大大减慢了操作，当你经常使用 cons 操作时尤为明显。

在实践中，我们经常要使用 cons 操作，因此这种“优化”并不是那么吸引人，因为它会减慢程序的速度。

但上面的讨论是为了说明一个中心思想：我们应该根据所需的用途选择对应的数据结构，以便使最常见的操作尽可能快地被执行。

访问一个元素

如果我们想要获取/访问链表或数组的任一个元素（比如第 6 个元素），应该怎么做？

对于数组，这很简单：我们获取下标（index）为 5 的元素（注意偏移量，因为数组下标从 0 开始），我们立即就能得到它，该操作的时间复杂度为 O(1)。

对于链表，这就比较困难了：我们一开始能直接访问链表的第一个单元格（指针一开始指向这里），因此我们只知道第一个单元格的 head（头部）字段和 tail（尾部）字段。

但是，我们也可以访问链表的第二个单元格：链表的 tail 字段里面的指针指向的下一个单元格的 head 字段（有点拗口，但我相信配合上面给出的图片和代码，你可以理解），只需把指针移动一次。

也可以访问第三个单元格，用相同的方法，把指针移动两次。

下面是从链表中获取索引为 n 的元素的算法：

如果 n = 0（我们想要访问第一个元素），返回 head 字段中的元素;
否则，返回 tail 字段中指向的链表中索引为 n-1 的元素。

你应该注意到了，我们将链表直接视为单元格：如果链表为空，则无法获取单元格中的元素，因此会返回错误。

要访问链表的一个元素，你必须遍历链表，以到达所需位置。要访问索引为 K 的元素，你必须做大约 K 次操作。此操作的复杂度是什么？正如在之前的课程中所说的，我们必须保持“悲观”，要考虑“在最糟糕的情况下”的算法复杂度：在最坏的情况下，也就是要找寻的元素是链表的最后一个单元格，所以你必须要遍历整个链表。因此，操作的时间复杂度为 O(N)。

你应该已经注意到访问第一个元素和访问任意一个位置的元素这两种操作的差异了。在链表中，访问第一个元素的时间复杂度是 O(1)，访问任意一个位置的元素的时间复杂度是 O(N)。

为了区分它们，计算机科学家用一个特定的术语叫“访问任意元素”：任意地访问。许多数据结构可以非常快速地访问某些“享有特权”的元素，但任意访问的速度较慢。数组具有在恒定时间内访问任意元素的特性，这在某些情况下是非常有用的。

你可能不知道“任意访问”这个术语，但你可能已经遇到过它的英语等价物：随机访问（Random Access）。或者，你从未想过，在摆弄计算机的 RAM（通常指内存）时，RAM 就是 Random Access Memory 的缩写，表示“随机存取存储器”。

访问链表的问题不仅限于在指定位置读取元素，你可能还想在此位置添加或删除元素。这些算法的时间复杂度接近于读取的算法，它们也具有线性复杂度 O(N)。

下一课我们继续学习数组和链表。

4. 第七课预告

今天的课就到这里，一起加油吧！

下一课：算法和数据结构-初级 | 第七课：数据结构之数组和链表（下）

365 天，坚持写作之 6 / 365，爱上你的每一天！

我是谢恩铭，在巴黎奋斗的软件工程师。
热爱生活，喜欢游泳，略懂烹饪。
人生格言：「向着标杆直跑」