5.5　链表

第3章中已经介绍过数组的概念，数组对应着一个连续存储的内存块，将同类型的元素一个个地排列起来，实际上还可以利用指向变量的指针把一系列的变量组织起来，形成一种新的数据结构，称之为链表。

5.5.1　链表的结构

链表元素常称为链表节点，每一个节点包含两个域即数据域和指针域。数据域保存数据，指针域连接该节点到下一个节点。可以看出，节点数据是一种复合类型即结构以及在第三篇中要介绍的类的对象，每一个节点占用一块存储单元，当要在链表中增加一个节点时，可动态地为该节点分配一个存储单元；当要在链表中删除一个节点时，也可释放该节点的存储单元。

图5.2为3个节点（A、B和C）互相链接形成链表的示意图，其特点是每个节点最多只有一个先驱节点和一个后继节点，首节点A只有一个后继节点，没有前驱节点，而最终节点C只有一个前驱节点没有后继节点，中间的节点B既有一个前驱节点又有一个后继节点。每个节点都由两部分组成，一是用来存放各种实际数据的数据域，另一个是指针域，存放下一个节点的首地址。例如，A的地址域中存放的是B的地址＆B。

图　5.2　链表结构图

另外，每个链表都有一个头指针head，存放的是链表首节点的地址。可以通过链表的head指针找到链表的首节点，由首节点的指针域找到下一个节点的首地址，依次类推，可以找到该链表的所有节点。需要注意的是最终节点的指针域为NULL，据此可以判断一个链表是否结束。如果表节点个数为0，我们称之为空表，此时head指针为NULL。

节点的数据类型可以相同，也可以不同。当节点的类型相同时，形成同质链表，否则形成异质链表。在实际应用中常用的是同质链表。