2.11 链表
现实生活中存在大量需要动态存储和表示的数据，例如排队、数据排序等，这些问题都需要用链表的方式表示和处理。下面将对链表进行详细的介绍。
2.11.1 链表概述
链表是一种动态的数据结构。它是动态进行存储分配的一种结构。通常，对于大批的数据可以采用数组的方式保存，但使用数组保存存在明显的问题。首先，在C语言中，数组的大小在使用之前必须是确定的，一旦数据增加超过了数组的容量，就会发生数组溢出。为了保证不会发生数组溢出，当使用之前不能确定数组规模时，往往需要开设一个很大的数组，从而造成空间的浪费。如果在程序中采用动态数组的方式，即在数组增长的时候重新分配内存，然后将原始数据复制到新的数组中，这虽然是一种可行的办法，但效率太低。第二，如果要在数组中删除数据，就要将数组中删除点之后的数据向前移动；如果要在数组中插入数据，则必须将插入点后的元素向后移动。这种数据移动方式的效率同样是比较低的。链表正是针对数组的这些缺点而设计的一种存储数据的动态数据结构。
在链表中，所有数据元素都分别保存在一个具有相同数据结构的节点中，节点是链表的基本存储单位，一个节点与一个数据元素对应。每个节点在内存中使用一块连续的存储空间，每个节点可以使用不连续的存储空间，节点之间通过指针连在一起，连接节点的指针也称为链。
节点的存储结构在内存空间中通常分为两个部分：信息数据部分（也称为数据域）和连接节点的指针（也称为指针域）。节点定义采用结构体类型，一般形式为：
- struct node
- {
- datatype data; /*信息数据，根据实际数据定义*/
- struct node * link; /*指向节点node 的指针*/
- };
在这里，节点的数据类型名称是struct node，data 是实际需要的结构成员分量，datatype是实际分量所需要的数据类型，link是一个指向struct node类型的结构指针，即link指向的对象是一个同样类型的数据节点，它是一个动态的指针，用来存放下一个节点的地址，通过link指针，一个个节点被依次连接起来，形成链表。
一个链表一般由3 部分组成，分别为头指针、表头节点和数据节点。它们之间的关系如图2.11 所示。
 |
| （点击查看大图）图 2.11 单链表结构 |