单链表

单链表指的是线性表的每个结点分散地存储在内存空间中，先后依次用一个指针串联起来。

单链表可以分为：不带表头结点和带表头结点两种。

不带表头结点的单链表

其中：data称为数据域（用来存储所需要存储的数据元素），next称为指针域/链域（存储数据元素之间的链接信息即下一个结点地址部分）。当head==NULL时（就是头指针为空，没有指向下一个结点），为空表；否则为非空表，当为一个非空表时，在首结点*head中会存放数据。

带表头结点的单链表

其中：head指向表头结点，head->data不放元素，head->next指向首结点a1，当head->next==NULL（就是头结点指向的表头结点的指针域为空，没有指向下一个结点）,为空表；否则为非空表。

ps:我们一般采用带表头结点的单链表，用起来会比较方便。

单链表的结点定义

第一种:

struct node{
    ElemType data;	//data为抽象元素类型
    struct node *next;	//next为指针类型
};
/*指向结点的指针变量head，p，q说明：
struct node *head,*p,*q;
*/

第二种：

typeddef struct node{    
    ElemType data;  //data为抽象元素类型
    struct node *next;  //next为指针类型
	}node,*Linklist;
/*指针变量head，p，q说明：
Linklist node head,p,q;
*/