⚠️ 这两天实在过于忙碌，以至于没有学习的时间，今天闲下来，立刻恢复更新，有等待我最新文章的小伙伴实在抱歉！
⚠️ 另外，有喜欢我笔记的小伙伴可以订阅我的《数据结构》专栏，该专栏收录在我的大专栏《cs-self-learning》中，也可以订阅，日后会有更多有用的技能、笔记全部收录在大专栏里面，谢谢支持！
定义
每个节点除了存放数据之外，还要存储指向下一个节点的指针
- 优点：不要求大片连续空间，改变容量方便
- 缺点：不可随机存取，要耗费一定空间存放指针
用代码定义一个单链表
struct LNode{ //定义单链表节点类型
ElemType data; //每个结点存放一个数据元素
struct LNode *next;//指针指向下一个节点
}
struct LNode *p = (struct LNode *) malloc (sizeof(struct LNode));
//增加一个新的结点：在内存中申请一个结点所需空间，并用指针p指向这个结点
/*
* LNode是结点
* data是数据域
* next是指针域
*/
typedef的用法：
typedef <数据类型> <别名>
通过typedef的用法，我们可以将上面的struct LNode写得更简洁一点
——> typedef struct LNode LNode;
然后就可以将上述代码简写为
——> LNode *p=(LNode *) malloc (sizeof(LNode));
同理，以下代码：
typedef struct LNode{//定义单链表结点类型
ElemType data;//每个结点存放一个数据元素
struct LNode *next;//指针指向下一个结点
}LNode, *LinkList;//LinkList意思是单链表
可以简写为下面这种形式：
struct LNode{
ElemType data;
struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;
要声明一个单链表时，只需声明一个头指针L，指向单链表的第一个结点
由于各个结点是由next指针连起来的，所以知道了第一个结点就相当于找到了整个单链表
不带头结点的单链表
如何初始化一个单链表
typedef struct LNode{
Elemtype data;
struct LNode *next;
}LNode, *LinkList;
//初始化一个空的单链表
bool InitList(LinkList &L){
L = NULL;//空表——暂时没有任何节点（目的：防止脏数据）
return true;
}
void test(){
LinkList L;//声明一个指向单链表的指针
InitList(L);//初始化一个空表
//……后续代码……
}
//判断单链表是否为空
bool Empty(LinkList L){
if(L == NULL)
return true;
else
return false;
}
/*
* 或者可以写成
* bool Empty(LinkList L){
* return(L == NULL);
* }
*/
带头结点的情况
typedef struct LNode{
Elemtype data;
struct LNode *next;
}LNode, *LinkList;
//初始化一个单链表（带头结点）
bool LinkList(LinkList &L){
L = (LNode *) malloc (sizeof(LNode));//分配一个头结点
if(L == NULL)
return false;
L->next = NULL;//头节点之后还暂时没有结点
return true;
}
void test(){
LinkList L;//声明一个指向单链表的指针
//初始化一个空表
InitList(L);
//……后续代码……
}
这个next头结点是不存储数据的，只是为了之后实现某些基本操作的时候会更方便一些
要判断这个单链表是否为空，我们要判断的就是这个头结点next指针域是否为NULL，如果是NULL，就是空的。
不带头结点VS带头结点
- 带头结点——写代码更方便
- 不带头结点——写代码更麻烦
对于这一部分，需要注意的是： - 不带头结点，头指针指向的下一个结点是实际用于存放数据的结点
- 带头结点，头指针指向的下一个结点是不存放数据的，只有这个头结点之后的下一个结点才会用于存放数据