第1章　链表

1.1　何谓链表

我们知道，数组一般需要先定义长度（事先预估数组元素个数），但这在解决某些问题时并不是特别适用。例如，记录不同学校的学生时，由于各校人数不同，开辟过大的数组会导致存储空间浪费，开辟过小的数组会导致数组元素不够用。

链表可以根据需要动态开辟内存单元，是一种常见的重要数据结构。图1.1所示为最简单的一种链表。

图1.1

链表如同铁链，一环扣一环，中间是不能断开的。例如，幼儿园教师带领小朋友出来散步，教师牵着第一个小朋友的手，第一个小朋友牵着第二个小朋友的手……最后一个小朋友的一只手是空的，这就是一个“链”。

教师即“头指针”变量，即图1.1中的“Head”，它用于存放一个地址。链表中的每一个元素被称为一个“节点”，每个节点都包含两部分：一部分是存储数据元素的数据域，另一部分是存储下一个节点地址的指针域。

最后一个元素的指针域不指向其他节点，它被称为“表尾”，以“NULL”表示。“NULL”在C++里指向“空地址”。

显然，链表使用结构体和指针变量实现是十分合适的。

由于NOIP已允许使用C++的STL（Standard Template Library，标准模板库），因此本书中许多数据结构的实现都可以使用STL轻松实现，例如队列可以使用STL的queue实现，堆栈可以使用STL的stack实现……此外，使用效率更高的数组仿真也是不错的选择。对学习时间不充裕的读者来说，本章的链表内容可以略过不看，但如果想要对数据结构有更深刻的理解以应对更高层次的挑战，建议读者还是认认真真把基础夯实。