前言引入
之前我们学习了数组这一概念，使用数组可以在编程时增加程序的灵活性。但在c语言中不允许定义动态数组的类型也不能随意调整数组的大小，往往会导致内存空间的浪费。由此我们推出链表。链表是动态进行内存分配的一种结构，它可以随时为其结点分配需要的存储空间也方便插入新的节点，把不再使用的空间回收待用。
链表的概念
链表是一种动态数据结构,它使用随机分配的内存单元来存放数据,这些内存单元可以
是连续的,也可以是不连续的。链表是由若干个相同结构类型的元素依次串接面成的.它使用指针来表示两个元素之间的前后关系。链表中的每个元素称为一个“结点”。结点是结构类型,其成员由两部分组成:①用户需要使用的数据(称为数据成员或数据域):②下一个结点的地址(称为指针域,为指向自身结构类型的指针)。链表对各结点的访问需从第一个结点开始。根据第一个结点的指针域找到第二个结点,再根据第二个结点的指针域找到第三个结点,以此方法可以访问到链表中的所有结点。链表的尾结点由于无后续结点,在其指针域放一个NULL(表示空地址)表明链表到此结束。
根据结点之间的相互关系,链表分为:单链表、双链表、循环链表。单链表的每个结点中只包含一个指针域,该指针域中存放的是其后继结点的地址,这样的链表称为单链表如下图
通常使用结构的嵌套来定义单链表结点的数据类型,定义形式如下:
struct 结构名
{类型名成员名1;类型名成员名2;
.....
类型名成员名n;
struct 结构名 *指针名1,*指针名2,……,*指针名 n;
};
