目录
1、介绍
1、单链表是线性表的另一种表现形式：链式存储。
2、特点：每一个结点逻辑关系相邻（由指针串联成一串），但在内存中位置不一定相邻（每个结点在需要时被单独malloc()，与前一个结点的内存距离不确定）。
3、概念：用一组任意的存储单元存储线性表的数据元素（这组数据可以连续，也可以不连续）。所以，为了表示每个结点 An 和其后继节点 An+1 之间的逻辑关系，每一个结点不仅需要保存自己的有效值（数据域），还需要保存下一个结点的地址（指针域）。
4、头结点：浪费掉数据域，作为链表的头部，在进行头插和头删时，起辅助作用。一个链表可有头结点，也可以没有，有了更方便一点。对于在写习题时，如果题中给的链表无头结点的，我们可以额外申请一个结点链在链表头部，作辅助。（本文描述的链表都带有头结点）
其结构形如：
2、单链表结构体设计
typedef int ELEM_TYPE;//数据类型泛化
typedef struct Node
{
ELEM_TYPE data;//数据域(保存数据的有效值)
struct Node* next;//指针域（保存着下一个有效节点的地址）
}Node, * PNode;typedef int ELEM_TYPE：作数据类型泛化，在上一篇笔记中讲过数据结构之顺序表。
结构体中成员变量 data 保存我们想要保存的数据；next指针指向下一个保存数据的结点（地址）。头结点未使用数据域，使用了指针域；尾结点使用了数据域，使指针域指向NULL，表示后续无有效结点。
3、单链表相关函数
需要将链表传入函数的话，全是将链表的头结点的指针传入函数。这样就可以遍历链表或解引用访问链表。
在函数中，如果我们要多次用到头结点，那我们就不能直接对传入的头结点指针进行操作（头结点指针要保存链表的起始地址，保护链表起始地址不丢失），在函数中，每次都要用一个新指针指向头结点，再以新指针遍历链表；如果我们只会用到头结点一次，就可以直接使用函数传入的链表头结点指针，不必使用一个新指针。
3.1、链表初始化
void Init_list(struct Node* plist)
{
//安全性检验，判断plist是否为NULL地址
assert(plist != NULL);
//plist->data; 头结点的数据域不使用
plist->next = NULL;
}链表刚开始只有一个头结点，等待新结点向其身后挂载。目前就只将链表的头结点的指针域置为NULL，忽略数据域data，因为头结点用不到。
3.2、插入数据
●在我们想插入数据时，先购买一个新结点（malloc一个），将数据赋值给新结点的数据域data；
●如果想将数据插入到某个位置，我们就需要（1）找到这个位置的前驱结点；（2）将新结点的next指向前驱结点的next结点；（3）使前驱结点的next指向新结点。
●如此操作，我们就完成了将一个新结点，插入到原链表的链式结构中。这就是链表结点的插入方法。
3.2.1、在插入数据时，是否需要对链表进行判满？
在上一篇顺序表中，在插入数据时，我们需要先对顺序表进行判满，然而在链表插入数据时，我们是否需要进行链表判满呢？
在1.2链表特点中，我们提到链表的结点是在需要的时候被一个个malloc出来的，结点被malloc出来后进行赋值，在将其串联到链表表体上。顺序表是提前开辟好一段连续的存储空间，等待数据存入，当数据存满时，进行扩容；而此时，链表结点本身已经开辟好存储空间，所以链表无需判满，只要堆区中有足够空间，我们就能申请开辟一个新结点，将其链接在链表上。
3.2.2、头插
注意，头结点永远是链表的头部，想要在链表头部插入数据，就是插入在链表头结点之后。
bool Insert_head(PNode plist, ELEM_TYPE val)
{
//0.安全性处理
assert(plist != NULL);
//1.购买新节点
struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
assert(pnewnode != NULL);
pnewnode->data = val;
//2.找到合适的插入位置
//因为是头插，永远都是插入在头结点后面，所以不用找 直接用plist即可
//3.插入
//操作（2）将新结点的next指向前驱结点的next结点；
pnewnode->next = plist->next;
//操作（3）使前驱结点的next指向新结点。
plist->next = pnewnode;
return true;
}3.2.3、尾插
向链表尾部插入数据（一个新结点），我们就要找到尾结点。在链表中，当一个结点的next域指向NULL时，这个结点就是尾结点。
找到尾结点的方法：对链表结点进行遍历，若该结点的next == NULL，则该结点就是尾结点；否则，移动至下一个结点（如：指针p指向链表，p = p->next;）。
bool Insert_tail(PNode plist, ELEM_TYPE val) {
assert(plist != NULL);
//购买新结点
PNode newNode = (PNode)malloc(sizeof(Node));
assert(newNode != NULL);
//新结点保存数据
newNode->data = val;
//1.使用新指针指向链表头部
//进行遍历链表
/*PNode n = plist;
//循环直到找到尾结点
while (n->next != NULL) n = n->next;
newNode->next = n->next;
n->next = newNode;*/
//2.直接使用plist进行链表遍历
while(plist->next!=NULL){
plist=plist->next;
}
newNode->next = plist->next;
plist->next = newNode;
return 1;
}3.2.4、按位置插入
在插入数据时，我们还可以选择给定一个长度pos，将数据插入到从链表头部起，长度为给定长度的结点位置。假设给定长度pos小于0或比链表长度长为无效插入。
bool Insert_pos(PNode plist, int pos, ELEM_TYPE val) {
assert(plist != NULL&&pos>=0);
//遍历链表
while (pos > 0 && plist->next != NULL) {
--pos;
plist = plist->next;
}
//若pos>0，则要插入的位置比链表长，无效
if (pos > 0) return 0;
PNode newNode = (PNode)malloc(sizeof(Node));
assert(newNode != NULL);
newNode->data = val;
newNode->next = plist->next;
plist->next = newNode;
return 1;
}当pos == 0 时，就是头插；当pos == 链表长度时，就是尾插。所以头插和尾插可以直接由按位置插入函数特殊实现。
3.3、删除数据
删除数据，也就是删除链表中一个保存数据的有效结点。我们找到待删除结点的前驱结点，使前驱结点的next域不再指向待删除结点，而是指向待删除结点的下一个结点。这样就完成了将待删除结点从链表中删除。
但只是将待删除结点从链表中删除是不够的。将待删除结点删除，也就意味着这个结点没用了，并且不要忘记链表中的结点都是由我们malloc来的，所以不要忘记对被删除结点进行free。
3.3.1、链表判空
当链表没有有效结点时，也就是头结点next域指向的结点为空时，我们就无需进行删除，所以在删除前需要进行判空操作。
bool IsEmpty(PNode plist) {
return plist->next == NULL;
}根据分析，我们只需要判断头结点的next是否为空就可以了。
3.3.2、头删
也就是删除头结点之后的第一个有效结点。
bool Del_head(PNode plist) {
//0.安全性处理 不仅仅判断头结点是否存在，还需要判断是否是空链表
//如果不是空链表，则代表至少有一个有效节点
assert(plist != NULL);
if (IsEmpty(plist)) return 0;
//1.用一个指针指向待删除结点
PNode n = plist->next;
//2.跨越指向，完成从链表中删除该结点
plist->next = n->next;
//释放内存
free(n);
return 1;
}3.3.3、尾删
1、我们可以先找到尾结点，在去找尾结点的前驱结点。
bool Del_tail(PNode plist)
{
assert(plist != NULL);
if(IsEmpty(plist)) return 0;
//1.申请一个临时指针p指向待删除节点 p指向倒数第一个节点(尾结点)
struct Node *p = plist;
for(; p->next!=NULL; p=p->next);
//此时，for循环执行结束，指针p指向尾结点
//2.申请一个临时指针q指向待删除节点的上一个节点(前驱) q指向倒数第二个节点
struct Node *q = plist;
for(; q->next!=p; q=q->next);
//3.跨越指向
q->next = p->next;
//4.释放待删除节点
free(p);
return 1;
}2、直接判断 plist ->next ->next 是否等于 NULL，来寻找尾结点的前驱结点。当plist ->next ->next ==NULL时，plist ->next 就是尾结点，所以此时 plist 就是尾结点的前驱结点。
bool Del_tail(PNode plist) {
assert(plist != NULL);
if (IsEmpty(plist)) return 0;
while (plist->next->next != NULL) {
plist = plist->next;
}
//指向待删除结点
PNode p = plist->next;
//跨越指向
plist->next = p->next;
//释放待删除结点内存
free(p);
return 1;
}3.3.4、按位置删除
我们也可以选择直接删除链表上某个位置pos的结点，并且位置pos需要>=0 并且 <= 链表的长度-1。
当pos为0时，是删除第一个有效结点，就是头删；当pos 为 链表长度 -1 时，是删除最后一个有效结点，就是尾删，而在插入数据时，当pos 为 链表长度 时，才是尾插，这是插入和删除数据时的区别，读者可多练习验证。
bool Del_pos(PNode plist, int pos) {
//安全检测
assert(plist != NULL && pos >= 0);
if (IsEmpty(plist)) return 0;
//我们直接向当前结点的后两个结点进行了空判断
while (pos > 0 && plist->next->next != NULL) {
--pos;
plist = plist->next;
}
//如果此时pos>0,
//pos原本大小就是>=链表长度
if (pos > 0) return 0;
PNode p = plist->next;
plist->next = p->next;
free(p);
return 1;
}与插入数据类似，当pos==0时，为尾删；当pos==链表长度-1时，为尾删。
3.3.5、按值删除
在某些场景下，需要我们对保存特定数据值的结点进行删除。此处假设只删除第一个对于数据值的结点，读者可对功能进行扩充。
bool Del_val(PNode plist, ELEM_TYPE val) {
assert(plist != NULL);
if (IsEmpty(plist)) return 0;
//判断下一个结点不为空
while (plist->next != NULL) {
//判断下一个结点的值，是否为指定数据值
//此时本结点，就是待删除数据的前驱结点
if (plist->next->data == val) {
PNode p = plist->next;
plist->next = p->next;
free(p);
return 1;
}
plist = plist->next;
}
//如果没有成功删除，
//就是链表中没有保存该val值的结点
return 0;
}3.4、链表结点查找
根据给定数据值，遍历链表结点，判断是否有链表结点数据值与给定值相同，若有，则返回该结点的地址（指针）。
struct Node* Search(PNode plist, ELEM_TYPE val)
{
for(struct Node *p=plist->next; p!=NULL; p=p->next)
{
if(p->data == val)
{
return p;
}
}
return NULL;
}3.5、销毁链表
由于链表除头结点以外的结点都是由动态内存开辟获得，所以我们需要对头结点以外的所有结点进行free。
销毁链表有两种方式：
1、借助头删函数方法，无限头删，直到删完所有有效结点。
//无限头删(只要单链表不空，则头删一个节点，无限循环，直到单链表空了)
void Destroy(PNode plist)
{
assert(plist!=NULL);
/*while(!IsEmpty(plist))
{
Del_head(plist);
}*/
//plist一直是头结点
while(plist->next != NULL)
{
//指针记录第一个有效结点
struct Node *p = plist->next;
//跨越指向（删除）
plist->next = p->next;
//释放结点
free(p);
}
}2、两个指针相互合作。从链表第一个有效结点开始，
（1）一个指针 p 指向待删除结点，
（2）一个指针 q 指向待删结点的后续结点，
（3）将 p 结点释放掉之后，使p 再指向 q 指向的链表剩余结点。
重复上述操作，直到p指向的结点为空，也就是将有效结点全删完了。
void Destroy2(PNode plist)
{
//0.安全性处理
assert(plist!=NULL);
//1.定义两个指针p和q p指向第一个有效节点 q先不要赋值
struct Node *p = plist->next;
struct Node *q = NULL;
//2.断开头结点，不用借助头结点，
//所以一开始就将头结点变成最终销毁完成后的样子
plist->next = NULL;
//3.两个指针p和q合作，循环释放后续节点
while(p != NULL)
{
q = p->next;
free(p);
p = q;
}
}3.6、获取链表长度（有效值个数）
如果我们想要知道链表的长度（不包括头结点）或者记录的有效值的个数，只需遍历一次链表就可以了。
int GetLength(PNode plist)
{
assert(plist!=NULL);
int count = 0;
//让指针p指向第一个有效节点
for(struct Node *p=plist->next; p!=NULL; p=p->next)
{
count++;
}
return count;
}3.7、打印链表所有有效值
void Show(PNode plist)
{
assert(plist!=NULL);
for(struct Node *p=plist->next; p!=NULL; p=p->next)
{
printf("%d ", p->data);
}
printf("\n");
}4、单向循环链表
单向循环链表是单链表的特殊形式（环形），其尾结点的next域不再指向 NULL ，而是指向头结点。
1、单向循环链表的存在的意义就是可以在任意一个结点开始，都可以遍历整个链表。所以，此时我们判断循环链表是否被遍历完一个循环的条件就不再是当前结点指针是否指向NULL或当前结点的next是否指向NULL，而是在遍历开始前，用一个指针start记录下遍历开始的结点，在遍历的过程中判断该结点是否== start指向的结点。若等于，则已经遍历完整个循环链表。
2、单向循环链表的实现与普通单链表无较大区别，只是尾结点的next指针域指向了头结点，还有判断是否遍历完整个链表的条件发生了改变。
5、总结
1、遍历链表的方式
本文中遍历链表的方式分为两种：
（1）：直接从头结点开始，以判断当前结点的next 结点是否满足条件作为循环终止条件。如：
struct Node *p = plist;
for(;p->next!=NULL;p=p->next);这种遍历方式的适用情况是：当我们需要获取到目标结点的前驱结点时。此时，才以 p ->next 是否满足条件作为循环停止条件的。例如，在插入和删除操作时，我们需要获取到待插入位置和待删除结点的前驱结点。
（2）：从第一个有效结点开始，以判断当前结点自身是否满足条件作为循环终止条件。如：
struct Node *p = plist;
for(;p!=NULL;p=p->next);这种遍历方式的适用情况是：当我们需要直接访问有效结点本身时。例如，按值查找结点、打印链表结点值、销毁链表时。
2、顺序表和单链表的区别
| 顺序表 | 链表 | |
| 底层实现 | 在堆区利用动态内存开辟的数组 | 在堆区利用动态内存开辟的的动态链表 |
| 空间利用率 | 提前开辟好一段空间，不够时扩容。空间大概率放不满，空间利用率第。 | 插入一个数据，开辟一个结点，不会造成浪费。 |
| 访问元素的速度 | O(1)：直接利用下标，解引用访问 | O(n)：需要从头开始遍历链表 |
| 插入和删除 | 因为顺序表插入和删除数据时需要移动数据，所以只有尾部操作时才是O(1)，其他情况都是O(n)。 | 单链表的结点通过指针链接，不需要挪动元素，所以插入和删除的时间复杂度都是O(1)（忽略寻找结点的时间） |