链表的C++实现
+++++++++++++

本节我们将使用C++语言实现单链表和双链表结构。作为数据结构这一领域的学习，我们将使用C++模板技术实现标准的链表ADT，可以接受任意类型的元素，具有以下标准功能：

1. 基本功能：

   1. 获取链表长度，即表中元素的数量；
   2. 判断链表是否为空；

2. 迭代访问：

   1. 获取链表首元素节点的指针，请注意是首元素的节点，不是头部的哑节点指针；
   2. 获取双链表的尾部指针，请注意是尾部的哑节点指针，不是尾元素的节点指针；
   3. 向后移动节点指针；
   4. 向前移动双链表节点指针。

3. 元素访问：

   1. 按照元素下标获取元素值；
   2. 根据节点指针获取元素值；
   3. 获取链表首元素；
   4. 获取双链表尾元素；
   5. 修改指定下标处的元素值；
   6. 修改给定节点（由指针给定）处的元素值。

4. 元素增删：

   1. 在链表头部插入新元素；
   2. 在双链表尾部添加新元素；
   3. 新元素插入为单链表给定节点（由指针给定）的后继；
   4. 新元素插入为双链表给定节点（由指针给定）的前驱，类似于顺序表中在指定元素位置处插入新元素；
   5. 删除链表首元素；
   6. 删除双链表的尾元素；
   7. 删除单链表给定节点（由指针给定）的后继；
   8. 删除双链表给定节点（由指针给定）本身。
   9. 清空链表。

以上是链表的常见标准功能，在学习数据结构时应全部予以掌握，在实际编程中可能会有所取舍或改变。本节详细介绍单链表的完整实现代码，双链表只做简单说明，代码实现将作为本节的练习。

.. attention::

   这一章是学习数据结构，在编写每一种数据结构的实现代码时我们都会用最接近面向对象的风格和工程编程的要求来编写一个比较完美的、甚至可以直接当做类库使用的抽象数据类型。这样的代码会比较繁琐，代码量大，在算法问题编程的时候如果要自己实现一些数据结构，不需要这样写，应该根据问题的要求，编写简化版的ADT，我们在这一章中的例题中会看到各种简化版代码。

单链表的实现
^^^^^^^^^^^^

**1、基本结构**

我们先定义好链表的基本结构形态，实现元素访问、迭代和其他一些基本功能。

首先我们需要设计一个用来存放元素节点的结构，为了可以适用于任何类型的元素，这里要用模板结构。如同上一节所述，常见的写法如下：

.. code-block:: c++

   template<typename T>
   struct Node {
           T _value;            // 元素值
           Node<T> *_next;      // 后继链指针

           // 构造函数
           Node() { _next = NULL; }                             // 默认构造函数
           Node(const T &val) { _value = val; _next = NULL; }   // 指定元素值的构造器
   };

这样就可以了，我们在成员变量的名称前加上下划线 ``'_'`` 只是为了表示数据封装的惯例，提醒编程人员不要在外部程序中直接访问使用这些成员变量。比如像下面这样的传统写法，现代程序设计理念认为是恶劣的：

.. code-block:: c++

   Node<int> n1(10), n2(11);
   int v = n1._value;
   n1._next = &n2;
   n2._value = v - 1;

但是如果外部程序代码遵循数据封装的惯例，不直接访问成员变量，那么外部程序要怎么才能获得结构里的元素值和后继指针呢？最常规的做法是给结构添加\ :strong:`访问器函数`\ （accessor），像下面这样：

.. code-block:: c++

   template<typename T>
   struct Node {
           T _value;            // 元素值
           Node<T> *_next;      // 后继链指针

           // 构造函数
           Node() { _next = NULL; }                             // 默认构造函数
           Node(const T &val) { _value = val; _next = NULL; }   // 指定元素值的构造器
           // 访问器函数
           T &value() { return _value; }                        // 访问元素值
           Node<T> *next() { return _next; }                    // 返回后继指针
	   void set_next(Node<T> *next) { _next = next; }       // 设置后继指针
   };

这是数据封装原则下的常规写法。

元素值的访问器 ``value()`` 返回的是成员变量 ``_value`` 的引用，所以只要这一个访问器就能同时满足外部程序对元素值进行读写的功能要求，例如：

.. code-block:: c++

   Node<int> n(2);      // 创建一个元素值为2的节点
   int v = n.value();   // 读取元素值
   n.value()--;         // 元素值减一
   n.value() = 3 * 3;   // 设置元素值

后继指针是一个指针类型，不能返回引用，所以需要有一读一写两个访问器，可以这样使用：

.. code-block:: c++

   Node<int> n1(1), n2(2), n3(3);
   n1.set_next(&n2);            // n1的后继设置为n2
   n3.set_next(n1.next());      // n3的后继设置为n1的后继

通常，这样写就很好了，大多数数据结构教程上就是这么写的。但是我们不打算采用这种风格，我们可以做得更酷炫，具体怎么做过一会儿再讲。

.. hint::

   算法问题编程时甚至往往会直接访问成员变量，连访问器都不用。如果那样的话，成员变量就不要用 ``'_'`` 来开头了，写写都挺麻烦的。

下面我们先来定义单链表结构，暂时先不要去管成员函数，先把成员变量和构造器设计好，通常是下面这样的形式：

.. code-block:: c++

   template<typename T>
   struct LinkedList {
           Node<T> *_head;      // 头指针，指向头部哑节点
           int _size;           // 链表长度

           // 构造函数
           LinkedList() { _size = 0; _head = new Node<T>; }
   };

但是这样还不够好！我们现在向使用者（比如利用这个单链表结构来进行算法编程的人）开放出了两个结构类型，一个是单链表本身 ``LinkedList``\ ，另一个是元素节点 ``Node``\ 。这样就出现了一个问题，使用者需要关心或者需要直接生成单独的元素节点吗？是不需要的，也是不应该的。

STL库有一个双链表容器 ``list``\ ，使用这个容器，通过迭代器、成员函数等方式可以像在 ``vector`` 容器或者最简单的数组里一样直接访问到元素值，而不是先要返回一个节点或者节点指针。换句话说，\ ``list`` 容器在实现的时候把节点这个中间环节向使用者隐藏了起来，它不光实现了把元素值和元素之间的链隐藏在节点里，而且连节点本身也被隐藏了。我们也打算这样做，做法是把 ``Node`` 结构定义到 ``LinkedList`` 结构内部去，形成一种嵌套的结构定义，内层的结构是外层结构的子结构。在把元素节点定义成单链表结构的子结构后，为了表示这个节点结构是给单链表结构私人定制的，外部使用者不得使用，我们也按惯例在它的名称之前加上下划线。所以现在我们的单链表结构变成下面这个样子：

.. code-block:: c++

   template<typename T>
   struct LinkedList {
           // 节点结构，内部结构
           struct _Node {
                   T _value;            // 元素值
                   Node<T> *_next;      // 后继链指针

                   // 构造函数
                   Node() { _next = NULL; }                             // 默认构造函数
                   Node(const &T val) { _value = val; _next = NULL; }   // 指定元素值的构造器
           };

           LinkedList<T>::_Node *_head; // 头指针
           int _size;                   // 表长度

           // 构造函数
           LinkedList() { _size = 0; _head = new LinkedList<T>::_Node; }
   };

.. note::

   1、把节点定义为内部结构之后，模板整个加载在外部结构 ``LinkedList`` 之上，所以节点结构 ``_Node`` 就不需要使用 ``<T>`` 的模板标注了，一律加在最外层的结构名后面，例如链表构造函数中的写法；
   
   2、代码中若要使用 ``_Node`` 结构，现在就必须使用全名 ``LinkedList<T>::_Node``\ ，即在它前面加上外层结构的名称并使用名称限定符 ``::`` 连接起来。

所以现在外部的使用者可以不用关心节点是怎么回事情了。

.. warning::

   事实上，STL的 ``list`` 容器是用类（class）来构造的，类有严格的访问控制机制，所以能够真正做到把内部结构或者内部类对外隐藏起来。但是我们是用结构（struct）来模仿，并没有真正地把 ``_Node`` 结构隐藏起来，外部使用者如果一定要自己创建节点，完全可以使用结构的全名自己创建，例如 ``LinkedList<int>::_Node my_node(17)`` 这样子。和成员变量一样，名称之前加一个下划线只是惯例，不是规则。

   其实类的访问控制机制也完全可以用于结构，但是面向对象不是我们现在要学的内容，而且太复杂，现在不要去管它，先模仿着就可以了。

接下来回到我们前面提过的要怎么不使用访问器，酷炫地访问节点里的元素值的问题。事实上，我们现在已经把节点结构封装隐藏起来了，哪怕它有访问器，遵守惯例的外部使用者也已经不能使用它们了。那么怎么办？

还记得我们曾经说过的STL库三大组成部分吗？其中有一个部分是迭代器：:ref:`ref-2562`\ 。我们说过，迭代器实际上是一个包装过的指针，可以像指针一样 ``++,--`` 前后移动，用解指针运算 ``*`` 来获取其中的内容。但是任何一种STL容器的迭代器都不会把节点这种中间结构暴露给使用者，例如 ``list`` 容器的迭代器 ``list<T>::iterator``\ ，我们可以像一个指针一样使用它，但是它的前移运算 ``--`` 是沿着双链表的前驱链移动，后移运算 ``++`` 是沿着后继链移动，解指针之后得到的也不是 ``list`` 的节点，而是直接得到节点里的元素值。

所以我们要做的就是仿造一个迭代器，当然就是把节点的指针再次包装一下变成一个名字听起来很高端的新类型，比如就叫它指示器（Indicator）吧。这个指示器无非是把节点指针包装成一个新的结构类型，并且通过运算符重载让它支持后移 ``++`` 和解指针 ``*`` 两个运算，如果是双链表，那么还应该重载一下前移 ``--`` 运算。由于单链表没有尾指针，但是尾节点的后继指针一定为空指针，所以为了判断一个指示器是否已经沿着后继链走到了终点，需要判断它内部那个指针是不是变成了空指针。我们需要给指示器结构增加一个判断指针是否为 ``NULL`` 的成员函数，以便今后用来迭代遍历元素时可以判断是不是已经走到了底。

当然了，我们还要模仿STL容器那样，给 ``LinkedList`` 结构增加一个返回首元素指示器的成员函数。现在我们的 ``LinkedList`` 结构定义已经发展壮大到下面这样了：

.. literalinclude:: ../../codes/318_linkedlist.cpp
   :language: c++
   :lines: 3-38, 42-43, 55

.. note::

   1、符号 ``NULL`` 在以下这几个库中定义：\ ``cstddef, cstdio, cstdlib, cstring, ctime``\ ，如果程序中没有引入任何一个，那么就请用数字0来代替，或者至少引入其中一个，比如 ``cstddef``\ 。

   2、指示器结构重载的 ``++`` 运算符实现节点指针沿着后链移动到当前节点的后继，如果当前的节点指针就是 ``NULL``\ ，那么访问其后继就会出现空指针访问的错误，所以在移动的时候用一个三元运算来判断当前指针是不是为空，如果不空就将其改为自己的后继，否则继续为空指针 ``NULL`` 不变，这里注意指针为空判断表达式的书写方式。

   3、注意指示器结构重载的前置和后置两种 ``++`` 运算，回顾一下它们之间的相同点和不同点；注意其重载的解指针运算 ``*`` 是采用传引用的方式来返回节点中的元素的，不是传值，所以我们不光可以通过指示器获得元素值，而且可以直接修改它们！

   4、注意链表结构的构造函数，它会在构造新链表的时候就动态生成一个节点，并让头指针指向它，这个就是头部哑节点，头指针将永远指向它不变。

   5、注意链表结构的 ``begin()`` 函数，它生成一个临时的指示器并以传值的方式返回出来，其指向的是链表头指针所指向节点的后继节点，不是头指针所指向的节点！头指针所指向的是头部哑节点，它的后继才是真正的首元素节点。如果链表是空的，那么 ``begin()`` 返回的指示器内部会是一个空指针。

现在，外部使用者可以利用指示器来迭代访问我们这个单链表结构里的元素，假如已经有了一个单链表 ``LinkedList<int> lst``\ ，里面已经存有若干个整数元素，那么就可以像下面这样做：

.. code-block:: c++

   for (LinkedList<int>::Indicator id = lst.begin(); !id.end(); ++id)
           printf("%d\n", *id);
   
或者这样：

.. code-block:: c++

   LinkedList<int>::Indicator id = lst.begin();
   while (!id.end()) {
           *id += 1;
           id++;
   }

是不是很酷炫？看起来和STL容器迭代器的用法几乎是一样的。

但是还不够完美，因为现在我们还只能使用指示器来访问链表元素，指示器有时候写写比较麻烦，很多时候我们还是希望能够直接使用下标，像数组一样访问元素。所以接下来我们再重载一下 ``LinkedList`` 结构的下标运算 ``[]``\ 。方便起见，我们单独提供一个直接访问首元素的成员函数。另外为了便于编写循环条件，我们再模仿STL容器提供获取链表长度和判断链表是否为空的两个基本功能成员函数。下面给出相应的代码，为了减少篇幅，我们接下来只给出与成员函数相关的代码：

.. literalinclude:: ../../codes/318_linkedlist.cpp
   :language: c++
   :lines: 3, 4, 39-41, 44-46, 55-63

这两个函数的代码都比较简单，其中按下标访问的代码略长一些，所以没有写在结构内部，采用了声明与定义分开的方式。

.. warning::

   在下标运算符重载函数中，我们只是简单地从首元素节点开始，按照给出的下标值向后移动到指定下标处，由于下标从0开始编号，所以下标是多少就移动多少步。这里我们并没有考虑下标超限的问题，如果参数给出的下标值是超限的，那么一定会出现移动到空指针上的情况，也就是移动到了尾元素的后继指针上。然后要么在下一次移动时，要么在返回元素值时引发访问空指针的错误。

   对这样的错误，我们秉承C/C++语言一贯的风范，不予处理！是否会超限的问题留给外部使用者自己去考虑，这是程序员的事情，不是库设计者的事情。

现在我们可以完全像使用数组一样使用这个单链表里的元素了，如果总是操作链表的首元素，那么也可以直接调用 ``front()`` 成员函数来获取首元素的引用。例如下面的样子：

.. code-block:: c++

   printf("%d\n", lst.front());
   lst.front() = 0;
   for (int i = 0; i < lst.size(); ++i)
         lst[i]++;

.. hint::

   在算法编程中，有大量仅在一个线性表的头部或尾部操作的场景，因此对于单链表，单独提供一个 ``front()`` 成员函数是很有必要的。

.. warning::

   虽然提供了按下标访问的功能，但是一定要知道，链表是不提倡按下标值随机访问元素的，这样做的效率非常低。如果可能的话，尽量使用指示器（简化版直接使用节点指针）或仅在一头进行操作。

**2、元素增删**

我们的单链表结构已经具备了看上去很美的元素访问功能，可是元素呢？元素怎么放进链表里去？对，接下来就必须要实现元素的增加功能了。我们同样模仿 ``list`` 容器，提供两种添加元素的功能，一是在表头处添加，即新元素总是添加为首元素，另一种是添加为某个指示器所指向的元素的后继，即在指示器所指的位置之后插入新元素。

.. attention::

   要小心，在指示器 ``begin()`` 之后插入，并不是插入为首元素，而是首元素的后继。

由于使用了头部哑节点，所以在头部添加元素其实就是添加为哑节点的后继，不会改变头指针 ``LinkedList<T>::_head`` 的值，这个头指针自从链表被构造开始就永远指向头部哑节点不变。

在某个节点之后添加新节点的方法在上一节已经介绍过，这里只要按部就班地实现就可以了。只是需要注意，根据指示器插入元素时，编程者必须自己确保传入的指示器参数的正确性，如果这个指示器指向的是一个空指针或不正确的内存地址，成员函数不会多加检查，而是直接引发段错误。

.. literalinclude:: ../../codes/318_linkedlist.cpp
   :language: c++
   :lines: 3, 4, 47-49, 55, 64-81

.. warning::

   请注意到一个很重要的要点，链表是一种动态的数据结构，它内部的每一个节点都是按需使用 ``new`` 运算动态创建出来的，包括在新建一个单链表结构变量的时候由构造函数 ``new`` 出来的头部哑节点。

有了添加，就一定要有删除，哪一种数据结构不需要有删除其中元素的功能呢？单链表结构也不可能例外，我们还是模仿 ``list`` 容器为 ``LinkedList`` 结构添加三种删除元素的功能：删除首元素、删除指示器所指元素的后继元素、整表清空。

删除首元素其实就是删除头部哑节点的后继，删除一个节点的后继的方法在上一节已经学习过了，这里照样子实现就行了。为了避免出现空指针访问引发段错误，我们对这些情况进行特判处理。删除首元素时如果链表为空，或者删除指示器所指元素的后继时，指示器本身指向空指针或其指向的元素没有后继，出现这两种情况的时候直接返回，不做任何操作。

.. literalinclude:: ../../codes/318_linkedlist.cpp
   :language: c++
   :lines: 3, 4, 50-52, 55, 82-114

在清空链表的成员函数 ``clear()`` 中，我们对要删除的节点指针在循环条件中做了是否为空的判断，所以即使时空表时也不会引发错误，这时候循环根本就进不去。

.. hint::

   到这里为止，我们可以看到，与所有节点都是由 ``LinkedList`` 结构的成员函数默默地 ``new`` 出来的这个特点相对应，每一次删除元素，也都由相应的成员函数默默地将这些节点 ``delete`` 掉。这样就遵循了C++动态内存管理最重要的两条条原则：

   1. 有借有还，即每一个 ``new`` 都和一个 ``delete`` 对应，不多也不少。
   2. 谁借谁还，即 ``LinkedList`` 结构 ``new`` 的内存，就由 ``LinkedList`` 结构负责 ``delete``\ 。

   这也是封装隐蔽原则不允许外部代码直接使用节点结构的原因，如果允许 ``LinkedList`` 以外的代码可以直接使用节点结构，那么难保有可能会静态声明出一些节点来，并手动挂接到链表里面去。那么在删除这些节点时，由于它们是静态生成在内存里的，所以不能 ``delete``\ ，会导致运行时错误。而负责删除元素的成员函数们根本分不清哪些节点是静态生成的，哪些又是动态 ``new`` 出来的。这就是外部代码和内部逻辑发生耦合之后会导致的混乱，所以面向对象的封装原则不允许把节点结构公布给外部程序代码。

.. warning::

   到此为止，单链表的所有设计功能都已经实现了，而且看上去就像一个真正的STL容器一般。但是，它还存在一个巨大的漏洞，很可能是一个致命的漏洞，如果就这么使用它，它可能会导致内存耗尽！

为什么这个单链表结构有可能会导致内存耗尽？让我们来下面这样一个用例：

假如有这样一个问题，它需要连续输入n组数据，每一组有最多10\ :superscript:`8`\ 个 ``long long`` 型整数，读入的每一组数据需要放入一个单链表中进行相同处理。我们编写了一个函数用来读入一组数据并进行处理，程序的框架如下：

.. code-block:: c++

   typedef long long ll;

   void process(int n); // 读入一组n个数并处理

   int main()
   {
           int m, n;
           scanf("%d", &m);
           for (int i = 0; i < m; ++i) {
                   scanf("%d", &n);
                   process(n);
           }
           return 0;
   }

   void process(int n)
   {
           LinkedList<ll> lst;
           ll data;
           for (int i = 0; i < n; ++i) {
                   scanf("%lld", &data);
                   lst.push_front(data);
           }
           // 算法处理
   }

上面这个程序，每次在调用处理函数 ``process()`` 的时候，都会生成一个局部的单链表变量 ``lst``\ ，读入一组数据并进行处理。处理完之后，\ ``process()`` 函数退出，此时 ``lst`` 作为一个局部变量，会被自动销毁。但是它里面的所有节点都是动态 ``new`` 出来的，它们还没有相应的 ``delete`` 掉，所以它们所占用的内存空间并不会因为局部变量 ``lst`` 被销毁而自动销毁！那些动态生成的节点变量是不会被同时释放的！C++从来不自动做 ``delete`` 这个操作，根据谁借谁还的原则，这是程序员的事情！

更坏的情况是，\ ``lst`` 是 ``process()`` 内部的局部变量，一旦函数退出之后，被自动销毁的 ``lst`` 就再也找不回来了，其内部的成员变量 ``lst._head`` 也一样找不回来了，所以就算想补偿也来不及了。于是随着 ``process()`` 函数被一轮一轮地调用和退出，有借无还的内存空间就越来越多，这个问题的数据量又大得惊人，很可能在m组数据处理完毕之前内存空间就给消耗一空了。

那么如果我们在 ``process()`` 退出之前调用 ``lst.clear()`` 把表清空行不行呢？这当然有点用，但还不够完整，\ ``lst.clear()`` 只是把元素节点都 ``delete`` 了，可是别忘了还有一个头部哑节点存在呢？这样处理一方面增加了代码量，另一方面内存清不干净，所以不是一种完美的解决方案。何况要让编程者牢牢记住每次用完链表都要 ``clear()`` 一下确实也不像一个优秀的方法，怎么看都有应急处理的感觉。

那么完美的解决方案是什么呢？这就需要用到C++给结构新增的一项技能：\ :strong:`析构函数`\ （destructor），也叫做\ :strong:`销毁器`\ 。


**3、新技能：析构函数**

析构函数，是借用自C++类语法的一个技能，适用于自定义结构。顾名思义，它和构造函数（constructor）是一对相反的操作。构造函数用于构造一个新的结构变量，而析构函数用于销毁一个已有的结构变量。

当一个结构变量不再使用将被销毁的时候，如果我们为它定义了析构函数，那么系统在正式销毁它之前会自动调用它的析构函数，让我们可以在析构函数内部进行一些必要的预处理，比如这里可以用来把链表中包括哑节点在内的所有节点 ``delete`` 掉。

.. hint::

   一个结构变量在以下情况下会被系统销毁，从而引发调用其析构函数：

   1. 局部变量退出其有效范围，通常是定义它的函数退出运行，或退出定义它的循环、分支代码块；
   2. 结构变量本身是 ``new`` 出来的动态变量，当运行到销毁它的 ``delete`` 语句时。

   一般情况下，结构并不需要析构函数，但是如果结构中包含有 ``new`` 出来的动态变量，那么一定要定义一个析构函数进行检查和 ``delete``\ 。

和构造函数不同的是，一个结构只能有一个析构函数，而且它不能有参数，也没有返回值和返回类型。析构函数的函数名也是特定的，一定是结构名前加上一个 ``'~'`` 字符。例如我们的 ``LinkedList`` 结构的析构函数就一定是：

.. literalinclude:: ../../codes/318_linkedlist.cpp
   :language: c++
   :lines: 3,4,53-55,115-125

OK！这样就万无一失了。下面是一个完整的单链表及测试程序，程序里定义了一个自定义结构 ``Point``\ ，包含两个 ``double`` 型成员变量，用来表示一个平面点的坐标。程序生成一个存放 ``Point`` 型元素的单链表并对上述这些功能进行了测试，请下载下来编译运行，并尝试自己编写更多的测试用例进行测试：:download:`单链表完整实现代码及测试程序<../../codes/318_linkedlist.cpp>`\ 。

双链表的实现
^^^^^^^^^^^^

看懂学会了单链表的实现之后，照着样子做一个双链表就应该不是特别困难的任务了，这个任务作为本节的练习。

实现双链表，除了增加尾部增删访问元素的功能之外，有以下几个和单链表的不同点需要注意：

1. 节点结构中需要增加一个后继指针 ``_prev``\ ；
2. 指示器不再需要判断是否为 ``NULL`` 的功能，因为双链表在使用指示器进行迭代遍历的时候，可以通过两个迭代器是否相等来判断是不是已经推进到了尾部（或头部）；
3. 相应地，双链表应该提供表尾指示器，可以模仿STL容器提供尾部迭代器的方式，用一个成员函数 ``end()`` 返回尾部指示器，这个指示器应该指向尾部哑节点，而不是尾元素节点；
4. 双链表结构在构造的时候除了生成一个头部哑节点，还应该生成一个尾部哑节点，结构中应该增加一个尾指针 ``_tail`` 始终指向尾部哑节点；
5. 双链表的指示器应该具备向前迭代的功能，即需要重载 ``--`` 运算；
6. 双链表的元素插入不是插入为指示器所指元素的后继，而是所谓在指示器所指示位置处插入，其实就是插入为所指元素的前驱。

下面是一个双链表结构的框架，在练习中请实现其中空余的函数体代码：

.. literalinclude:: ../../codes/318_dbl_linkedlist.cpp
   :language: c++

.. admonition:: 练习

   参照单链表程序，将上面的双链表结构中缺失的代码补齐（有 ``TODO`` 标注的地方），并进行完整地测试。