数组是C语言中按顺序管理大量数据的一种方法，数组的元素都是按顺序存放在内存的一块连续空间中的（见图（a））。数组在定义时需要说明数组的大小，这样一来，如果数组定义大了，就会有大量空闲存储单元，定义小了，又会在运行中发生数组下标越界的错误，这是静态存储分配的局限性。
利用定义为指向结构体类型的指针，可以构造简单而实用的动态存储分配结构——链表结构。链表也是C语言中按顺序管理大量数据的一种方法，但它与数据在内存中的存放位置无关，即不需要按顺序存放在连续的内存空间中。链表的一个结点（数据元素，相当于数组中的数组元素）可以单独存放在内存的任意位置，并用指针来连接这些在内存中不连续的数据并管理这些数据的顺序（见图（b））。
图 数组和链表在内存中的不同存储方式
知识点总结
链表利用指针连接内存中非连续存放的数据并管理这些数据的顺序。
链表中的一个结点元素就是一个结构体对象。
单向链表的结点由数据和指向下一个结点的指针（后继结点）构成。
可以用如下代码所示构造一个单向链表结构（见图（b））：
链表中的一个结点元素就是一个结构体对象，而且其中总有一个结构体对象成员被定义为指向该结构体类型的一个指针（如*next）。在单向链表中，这个指针指向下一个结点，被称为结点的后继指针。
如图（a）所示，单向链表的结点由两部分组成，其中一部分专门用来存储其后继指针，称为指针域，另一部分用于存储其他数据（该结构体对象的其他成员），称为数值域。
链表的长度（结点的多少）是有弹性的，其最后一个结点的后续指针指向为NULL即表示到达链表的尾部，无须像数组一样事先指定大小。但是C语言中，所有的数据必须存储在指定大小的内存空间中，所以，我们在建立链表时，每新增一个结点，就用C语言提供的内存分配函数malloc（size）向系统申请一块内存空间用于存储该结点数据。同样地，在删除一个结点以后，也用函数free（指针名）释放它所占用的内存空间。因而，我们把链表结构称为是一种动态存储分配结构。
malloc（size）和free（指针名）都存放在malloc.h中，因此在调用时，要在程序开始加上#include<malloc.h>。
函数malloc（size）向系统申请size字节的连续内存空间，如果申请成功则返回连续空间起始地址的指针。通常用函数sizeof（x）来确定size的大小，其中的x是一个变量名或类型名，该函数返回的是x变量或类型在内存中占用空间的大小。
例如：sizeof（int）返回的就是一个int类型的数据所占字节的大小。
因此，可以如下面代码所示在定义一个链表结点后，用函数malloc（size）为它申请相应大小的内存空间：
而free（head）;则可以释放指针head指向的结点所占用的内存空间。
图 单向链表结构
