第一章 链表

何谓链表

我们知道，一般用数组存放一组数据时，必须事先定义固定的长度（即元素个数）。这在某些问题的解决中，并不是特别的适用。例如，记录不同班级的学生数据时，由于各班人数不同，会出现开辟过大的数组导致内存浪费、开辟过小的数组导致数组元素不够用的情况。而链表可以根据需要动态开辟内存单元，是一种常见的重要数据结构。图1.1所示为最简单的一种链表结构。

图1.1

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

老师即“头指针”变量，图1.1中以Head表示，它存放一个地址。链表中每一个元素称为“结点”，每个结点都应该包括两部分：一为实际元素值，一为下一结点的地址。

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

很显然，这种链表的数据结构，必须要用指针变量才能实现。