假设需要登记每个班级的学生姓名，有的班级总人数为 35，有的班级总人数为 90，则用数组存放数据时，需要将数组的大小设为 90。若班级的人数无法确定，则需要将数组的大小设的足够大，但这样会浪费内存空间。
相比数组，链表就没有这种缺点，链表可以根据需要开辟内存空间。与数组不同的是，数组在内存中按顺序依次存储（线性），而链表在内存中是非线性存储的。
链表的创建
链表是一种数据结构，一般使用结构体变量作为链表的元素，也叫节点（Node）。因此，链表的基本构成包含指针变量和结构体变量。
在 int main() 函数外，先创建结构体类型，代码如下：
struct int_node {
int val;
struct int_node *next; //next是结构体指针变量，指向下一个结构体变量
};
这样创建了 int_node 结构体类型，这个结构体类型与之前的结构类型体不同，这个结构体类型有一个指向结构体变量的成员，这个成员是指针变量，用于存储下一个结构体变量的位置，该成员是创建链表最重要的部分。
在 int main() 函数里，创建头指针变量 head，指针变量 p 和结构体变量 a、b、c 代码如下：
struct int_node *head,*p,a,b,c;
对结构体变量 a、b、c 的 val 成员分别赋值 1、2、3，代码如下：
a.val = 1;
b.val = 2;
c.val = 3;
代码运行后，形成的数据初始结构如下图所示。
图 1 数据初始结构
接下来做以下几步操作：
将结构体变量 a 的起始地址赋给头指针变量 head；
结构体变量 b 的起始地址赋给结构体变量 a 的 next 成员；
将结构体变量 c 的起始地址赋给结构体变量 b 的 next 成员；
为结构体变量 c 的 next 成员赋值为 NULL。
具体代码如下：
head = &a;
a.next = &b;
b.next = &c;
c.next = NULL; //指向空
到这一步，已经创建好了链表。指针变量 head 指向结构体变量 a 的地址，然后通过 a.next 指向结构体变量 b 的地址，再通过 b.next 指向结构体变量 c 的地址，最后 c.next 指向空。这样就将 3 个结构体变量串连起来，形成了链表其数据结构如下图所示。
图 2 形成链表的数据结构
下面进行遍历链表操作，先将指针变量 p 指向链表的首地址，代码如下：
p = head;
从头到尾，对链表进行访问，依次输出链表中 val 的值，代码如下：
do
{
printf("%d\n",p->val);
p = p->next;
}while(p! = NULL);
创建链表的完整代码如下：
#include
struct int_node {
int val;
struct int_node *next;
};
int main()
{
struct int_node *head,*p,a,b,c;
a.val = 1;
b.val = 2;
c.val = 3;
head = &a;
a.next = &b;
b.next = &c;
c.next = NULL;
p = head;
while(p != NULL)
{
printf("%d\n",p->val);
p = p->next;
}
return 0;
}
编译运行，结果如下：
1 2 3
注意，上面创建的是静态链表，即所有节点（也就是结构体变量）都已在程序中事先定义好的，而不是根据需要动态定义的。
链表的基本操作
接下来我们创建的链表，是在程序运行过程中从无到有地建立链表，也就是根据需要申请新节点，并将新节点从头到尾链接起来。
1) 创建链表
创建动态单向链表，能够输入学生的学号、成绩。代码如下：
#include
#include
#define LEN sizeof(struct stu) //获取字节数
//构造节点
struct stu
{
long id; //学号
float score; //成绩
struct stu *next;
};
int n; //全局变量n，保存节点总数
//创建链表
struct stu *create(void)
{
struct stu *head = NULL, *p1, *p2;
n = 0;
p1 = p2 = (struct stu*)malloc(LEN); //申请新节点
scanf("%ld %f",&p1->id,&p1->score); //输入学生的学号和成绩
while(p1->id != 0) //学号不等于0继续创建
{
n = n+1;
if(n == 1) head = p1; //head指向第一个节点
else p2->next = p1;
p2 = p1;
p1 = (struct stu*)malloc(LEN); //继续申请新节点
scanf("%ld %f",&p1->id,&p1->score);
}
p2->next = NULL; //指向空
return(head); //返回头节点
}
int main()
{
struct stu *pt;
pt = create();
return 0;
}
编译运行，结果如下：
1 80
2 90
3 70
4 86
5 78
0 0
可以看出，程序的第 3 行定义 LEN 存储 struct stu 类型数据的字节数，sizeof 是“字节数运算符”。
下面对 create() 函数进行解析：
1) 先定义指向 struct stu 类型数据的指针变量 head、p1、p2。n 赋值为 0，表示没有节点。
2) create() 函数中的第 4 行，malloc(LEN) 的作用是开辟一个长度为 LEN 字节的内存空间。malloc() 函数返回的是不指向任何类型数据的指针（void 型），而 p1 和 p2 是指向 struct stu 类型数据的指针变量，因此在 malloc(LEN) 之前添加“(struct stu *)”，对其类型进行强制转换。
3) malloc() 函数开辟第一个节点后，用 p1 和 p2 指向它，如下图所示。
图 3 动态链表创建（只有一个节点）
4) 从键盘输入一个学生的学号、成绩给 p1 所指的节点。如果输入的学号不为 0，则执行 n = n+1，n 的值为 1。如果判断出 n==1，即判断是第一个节点，则 head = p1，即将 head 指向第一个节点如图 3 所示（程序中始终将 head 指向第一个节点）。执行 p2 = p1，让 p2 也指向第一个节点。用 malloc() 函数开辟第二个节点，并将 p1 指向它（图 4 所示的第一步）。然后从键盘输入一个学生的学号、成绩给 p1 所指向的新节点。
图 4 动态单向链表（包含5个节点）
5) 若学号为 0，则退出循环，执行 p2−>next=NULL（让链表最后的节点指向空），执行 return 语句返回链表的头指针 head。这样 p1 开辟的新节点不会链接到链表中。至此，完成了动态单向链表的创建。
创建的链表如图 3（只有一个节点）和图 4 所示（包含 5 个节点）。
与 malloc() 函数不同的是，calloc() 函数进行了初始化，calloc() 函数分配的空间全部初始化为 0。
char* p;
p=(char*)calloc(40,sizeof(char));
realloc() 函数用法为 realloc(void *p,unsigned size)，将指针变量 p 指向的已分配的内存空间的大小改为 size。
p=(char*)realloc(p,20);
2) 遍历链表
在前面程序的基础上添加自定义的 print() 函数，完成链表的遍历，具体代码如下：
//链表的输出
void print(struct stu *head)
{
struct stu *p; //声明指针变量p
printf("id \t score\n"); //\t 表示跳格，即留8个空格
p = head;
while(p != NULL)
{
printf("%ld\t%f\n",p->id,p->score);
p = p->next;
}
}
分析print()函数的功能：
先将链表头指针作为参数，在函数中声明了指针变量 p，将链表的头指针参数赋值给指针变量 p；
然后执行 while 循环，若指针变量 p 非为空，则输出指针变量 p 所指向节点的数据。再执行 p = p−>next，让指针变量 p 指向链表的下一个节点。
若指针变量 p 为空，则表明指针变量 p 已经指向链表的尾部，链表的遍历已完成。
链表的遍历如下图所示。
图 5 链表的遍历
3) 查找节点
下面的 find() 函数是从链表中查找与 id 值相同的节点，代码如下：
struct stu *find(struct stu *head,long a)
{
struct stu *temp;
temp = head;
if(temp == NULL) //如果原来链表是空表
return NULL;
else
{
//查找id值不等于链表中节点值且没有到达链表末端，则后移
while (( temp->id != a) && (temp->next != NULL))
temp = temp->next; //p1后移一个节点
}
return temp;
}
查找节点比较简单，就是匹配对应的 id 值，如果不相等且没有到达链表末端，则将链表指针不断后移，直到找到相等的值或到达链表末端为止。
4) 删除节点
下面的 del() 函数是从链表中删除与 id 值相同的节点，代码如下：
struct stu *del(struct stu *head,long id)
{
struct stu *p1,*p2;
if(head == NULL) //判断是否为空链表
{
printf("是空链表");
return head;
}
p1 = head; //p1指向第一个节点
//p1指向的不是要找的节点，且后面还有节点
while(id != p1->id && p1->next != NULL)
{
p2 = p1;
p1 = p1->next; //p1后移节点
}
if(id == p1->id) //找到了对应的节点
{
if(p1 == head) //如果p1是首节点，把第二个节点给head
head = p1->next;
else
p2->next = p1->next; //下一个节点地址赋给前一个节点
printf("已删除:%ld\n",id);
free(p1); //释放p1节点空间
//n为全局变量，含义为节点数，不在本函数内定义
n = n-1; //节点数n-1
}
else
printf("链表中找不到对应节点");
return head;
}
在 del() 函数中，包含 head 和 id 两个参数，参数值通过主程序中头节点和待删除学生的学号传递过来。
代码先判断该链表是否为空，如果为空，则无法删除并返回主函数。然后执行 while 循环找匹配的节点，先判断查找学号是否与链表当前节点的学生学号相等，或者链表是否到达链表末端，如果查找到匹配学号或者到达链表末端，则停止循环，否则链表指针不断移向下一个节点。
此时，p2 指针跟着 p1 指针移动，且在 p1 指针后面。如果找到匹配节点，则判断匹配节点是否恰好是头节点，即判断 p1 是否是首节点，如果是则将第二个节点地址赋值给 head，否则将前一个节点 p1 的下一个节点地址赋值给前一个节点 p2 指向的下一个节点地址，即将 p1 节点从链表中移除，并将 p1 节点空间释放，然后执行 n=n−1，将总节点数减 1。
动态删除链表节点过程如下图所示。
图 6 动态删除链表节点
5) 插入节点
向链表中插入节点，对应的 insert() 函数代码如下，其中参数 stud 为待插入节点的地址或指针：
struct stu *insert(struct stu *head, struct stu *stud)
{
struct stu *p0, *p1, *p2;
p1 = head; //p1指向头节点
p0 = stud; //p0指向要插入的新节点
if(head == NULL) //如果原来链表是空表
{
head = p0; //头节点指向新节点p0,只有1个节点
p0->next = NULL; //p0指向空
}
else
{
//新添加节点p0的id值如果大于链表中节点的id值，则后移
while ((p0->id > p1->id) && (p1->next != NULL))
{
p2 = p1; //p2指向p1所指向的节点，跟着p1移动
p1 = p1->next; //p1后移一个节点
}
if(p0->id < p1->id) //p0->id的值比当前的p1->id的值小，插入节点
{
if(head == p1)
head = p0; //在头节点前插入新节点
else
p2->next = p0; //p2接入新节点
p0->next = p1; //新节点接向p1,原来p2的下一个节点
}
else //新节点p0的id值大于链表中任一个节点的id值,在链表最后插入节点
{
p1->next = p0;
p0->next = NULL;
}
}
//n为节点数，全局变量
n = n+1; //节点数加1
return head;
}
下面通过重新插入 id=2，score=88 的节点来描述节点的插入过程。插入节点与删除节点的代码前面略相同。先判断链表是否是空表，如果非空，则通过 while 循环找到插入节点的位置 p1。在找到插入位置 p1 后，判断 head 是否等于 p1，如果是则把 p0 赋值给 p1，即将 p0 作为新的头节点，否则将 p0 赋值给 p2 的下一个节点，即将 p2 的下一个节点指向 p0，如下图中的第一步所示。
图 7 动态单向链表节点的插入
然后将 p0 的下一个节点指向 p1，即将新节点 p0 指向原来的 p1，完成节点的插入，如图 7 中的第二步所示。
如果新节点 p0 的 id 值大于链表中任一个节点的 id 值，则在链表最后插入节点，先将 p1 的下一个节点指向 p0，再将 p0 的下一个节点指向空。
调用 del() 函数和 insert() 函数的主函数代码如下：
int main()
{
struct stu *head,*temp;
head = create(); //创建
print(head); //遍历
printf("删除链表id为2的节点\n");
head = del(head,2);
print(head); //遍历
printf("重新输入新节点学号2和成绩88\n");
//重新开辟一个新节点
temp = (struct stu*)malloc(LEN);
scanf("%ld %f",&temp->id,&temp->score);
head = insert(head,temp);
print(head); //遍历
return 0;
}