1.首先认识什么是单链表，知道其基本的定义：
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
结构图如下：
2.了解其来源（背景）
1.在顺序表中，对于整体空间的大小，在一定条件下会出现需要扩容的情况，而之前的顺序表在进行次操作时会出现一定的代价；
2.在对表中的元素进行相应的插入和删除操作时，顺序表往往存在一定的效率缺陷。
3.单链表的实现及其相应的操作，主要包括以下的函数，
// 动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x);
//插入多个同时
SLTNode* CreateSList(int n);
// 单链表打印
void SLTPrint(SLTNode* phead);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SList* plist);
//在pos之前插入
void SListInsert(SListNode* pphead, SListNode* pos, SLTDateType x)；
//删除pos位置
void SListEraseAfter((SListNode** pphead ,SListNode* pos)；
4.具体操作如下：
（1） 动态申请一个节点，次操作相当于对其初始化的操作，我们可以动态对其进行初始化，这样的好处相比静态初始化后期的操作可能会更方便
void SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newHead = (SLTNode*)malloc(sizeof(SLTNode)); if (newHead == NULL) { perror("malloc fail"); exit(-1); } newHead->data = x; newHead->next = NULL; return newHead; }
（2）插入多个同时
SLTNode* CreateSList(int n) { SLTNode* phead = NULL, *ptail = NULL; for (int i - 0; i < n; i++) { SLTNode* newnode = BuySLTNode(i); if (phead == NULL) { ptail = phead = newhead; } else { ptail->next = newnode; ptail = newnode; } } return phead; }
（3） 单链表打印
void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
（4）单链表尾插，在对表链表进行尾删的操作时，只需要两个节点，这里最难的是找尾，我们定义tail->next为尾，同时还要注意链表为空和顺序表为空的区别，同时使用二级指针来进行传递形参指向的内容
// 单链表尾插 void SListPushBack(SListNode** pphead, SLTDateType x) { SLTNode* newnode = BuySLTNode(x); //判链表开始是否为空 if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; // 找尾 while (tail->next) { tail = tail->next; } tail->next = newnode; } }
注意：
1.改变int，传递int*给形参，形参进行交换改变
2.改变int，传递int**给形参，*形参进行交换改变
（5）单链表的头插，创建新节点newnode 指向第一个，对于第一个元素，又可以用地址来找到，这里为空时不需要单独处理
void SListPushFront(SListNode** pphead, SLTDateType x) { SLTNode* newnode = BuySLTNode(x); newnode->next = *pphead; *pphead = newnode; }
（6）
单链表的尾删，这里有两种写法：
1.第一种我们可以在tail在往下继续指向时定义一个prev，双指针，tail再走之前给到prev，在依次执行，最后在找到tail时，tail的前一个也可以找得到（这里不写出来，大家可以试试！）
2.可以直接通过tail->->next来判断，但需要考虑其中tail->为空的情况
void SListPopBack(SListNode** pphead) { // 暴力的检查 assert(*pphead); // 温柔的检查 //if (*pphead == NULL) // return; //判断开始时链表是否只有一个元素 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tail = *pphead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
（7）单链表头删，删除时需要断言一下，不能直接删，不然的话找不到下一个的地址，我们可以保存下一个，之后指向下一个就解决了，这就是单链表的优势所在
// 单链表头删 void SListPopFront(SListNode** pphead) { assert(*pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
（8）单链表查找
// 单链表查找 SListNode* SListFind(SListNode* pphead, SLTDateType x) { SListNode* cur = pphead; while (cur) { if (cur->data == x) return cur; cur = cur->next; } return NULL; }
（9）单链表在pos位置之后插入x，给出的位置不再是下标，而是指针，注意地址的衔接情况，这里可以不用二级指针，这里改变的是结构体，只需要结构体指针就可以了
void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos); SListNode* next = pos->next; // pos newnode next SListNode* newnode = BuySListNode(x); newnode->next = next; pos->next = newnode; }
（10）单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos) { assert(pos); //SListNode* next = pos->next; if (pos->next == NULL) { return; } else { SListNode* nextNode = pos->next; pos->next = nextNode ->next; free(nextNode ); } }
（11） 单链表的销毁
// 单链表的销毁 void SListDestroy(SList* pphead) { SListNode* cur = *pphead; while (cur) { SListNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
（12）在pos之前插入
（13）删除pos位置
//删除pos位置 void SListEraseAfter((SListNode** pphead ,SListNode* pos) { assert(pos); if (pos == *pphead) { SListPopFront(pphead); } else { SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
5.代码块如下：
test.h
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;
6.总结
数据结构与算法比较复杂，需要多画图。链表题多判断边界，勤加练习。
