本篇主要总结单链表是如何实现的，数据结构是如何管理数据的，详细的介绍每一步是如何实现以及各种注意事项。
🚀1.单链表的实现🚀
单链表能实现什么功能呢？数据结构对数据的管理无外乎增删查改，让我们一一实现它吧！
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTData;//在单链表要使用的数据类型，可根据需要改动 typedef struct SLTNode 重定义单链表类型名 { SLTData data;//单链表中结点一般都含有两个元素，一个数据 struct SLTNode* next;//一个指向该该结点类型的指针 }SLTNode;//结点 SLTNode* BuySLTNode(SLTData x);//生成新结点的函数 void SLTPrint(SLTNode* pphead);//单链表的打印 void SLTPushBack(SLTNode** pphead,SLTData x);//单链表的尾插 void SLTPushFront(SLTNode** pphead, SLTData x);//单链表的头插 void SLTPopBack(SLTNode** pphead);//单链表的尾删 void SLTPopFront(SLTNode** pphead);//单链表的头删 SLTNode* SLTFind(SLTNode** pphead, SLTData x);//单链表的查找 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTData x);//在pos位置前面插入 void SLTErase(SLTNode** pphead, SLTNode* pos);//在pos位置之前删除 void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTData x);//在pos位置之后插入 void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);//在pos位置之后删除
🍭1.1单链表的尾插
单链表的尾插。我们要注意到我们传给尾插函数的是二级指针，也就是指向链表的指针的指针，为什么要传二级指针呢？
因为我们要在该函数内部修改指向链表的指针，让它指向别的的地方去，这就将它修改了，要想将该变量真正的修改成功，从内到外都要修改我们就得传它的指针，不然在函数内部修改成功，但在函数外部没有修改那又有什么用呢？
其实这就是典型的形参的改变不影响实参，只不过如果这里的实参是指向结点的指针，然后尾插函数接收参数也是指向结点的指针，那修改形参就无法改变实参，必须将指向结点的指针的地址传过去，然后用二级指针来接收，这样对形参的修改才可以改变实参。
并且一开始我们还要进行对该二级指针断言，防止有人传错指针，又传入一级指针类型。
好，让我们回到这个尾插函数。
尾插一个结点，我们首先要需要生成一个新的结点newnode.
我们首先想前面有一系列结点，而尾插只要在最后一个结点的后面接上即可，这时我们需要是最后一个结点的地址。
所以我们需要找尾。注意找尾while里进行的条件是tail->next!=NULL,这样才能找到最后一个结点
而不能写成while(tail!=NULL),这样找到的不是最后一个结点而是最后一个结点的后面。
接着我们再分析如果前面没有结点，那么直接将新生成的结点与指向链表的指针链接起来即可。
void SLTPushBack(SLTNode** pphead, SLTData x)//尾插 { assert(pphead); SLTNode* newNode = BuySLTNode(x);//生成一个新结点 //如果前面没有结点 if (*pphead == NULL) { *pphead = newNode;//直接将新结点赋给指向链表的指针 } else { //假设前面有结点 //找尾 SLTNode* tail = *pphead; while(tail->next!= NULL) { tail = tail->next;//往后走 } tail->next = newNode;//最后将新结点与最后一个结点链接 } }
🍭1.2单链表的头插
单链表的头插。
首先对二级指针断言，看是否合法
先假设前面有结点，然后生成新结点进行头插。
头插就是将指向链表的指针一开始指向新结点，再让原先第一个结点与新结点链接起来。
然后再假设前面没有结点，分析没有结点和有结点都可以。
void SLTPushFront(SLTNode** pphead, SLTData x)//头插 { assert(pphead);//断言判断 SLTNode* newNode = BuySLTNode(x);//生成新结点 //假设前面有结点.发现有结点和没有结点一样 newNode->next = *pphead;//将原先第一个结点与新结点链接起来 *pphead = newNode;//再让新结点与指向链表的指针连接起来 }
🍭1.3单链表的打印
单链表的打印。
其实本质也是循环打印，只不过不同与顺序表的下标循环，链表是没有顺序的，根据结点的next来进行循环
我们一般不让形参改动，而是重新将形参赋给给一个新元素，这样使用起来更好，因为如果在使用的过程中，又需要头地址的地方，就可以直接使用。
利用cur进行遍历。注意这里循环的条件是cur！=NULL
而不能写成cur->next!=NULL,如果写成这样那么最后一个元素就无法打印出来了，因为最后一个结点的next就为NULL
到最后一个结点就结束了
void SLTPrint(SLTNode* phead)//打印单链表 { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data);//打印每个结点的数据 cur = cur->next; } printf("NULL\n"); }
🍭1.4单链表的尾删
单链表的尾删。
我们要想删除数据就要进行判断是否删除过头，每次删除之前都要进行断言判断，一旦删除过头就立刻停止。
所以这里我们除了对二级指针断言之外，还需要对指向链表的指针进行断言也就是一级指针，对二级指针解引用即可。
首先我们假设前面有结点，然后尾删也就是删除最后一个结点，同时还需要将前一个结点的next置NULL
不然就变成野指针了。
这里有两种方法来找到前面一个结点的next。
一种是再定义一个指针prev来记录tail遍历链表的前面结点的位置。
最后tail找到尾结点释放tail，再将prev的next置为NULL，即可。
另一种是通过不去找真正的尾结点而实现。
也就是while(tail->next->next)
这里找的不是真正尾结点，而是尾结点前面的。
最后释放tail->next即可
再将tail->next置为NULL.
接着就是假设前面只要一个结点时，该怎么删呢？直接释放即可。
void SLTPopBack(SLTNode** pphead)//尾删 { assert(pphead); //暴力检查是否删过头 assert(*pphead); //假设前面只有一个结点时。 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tail = *pphead; SLTNode* prev = NULL; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); prev->next = NULL; } }
🍭1.5单链表的头删
头删与尾删一样都需要对二级指针和一级指针进行断言判断。
假设前面有结点，进行头删，就是让指向链表的指针指向第二个结点，将第一个结点删除掉。
假设前面没有结点，分析发现都适用。
void SLTPopFront(SLTNode** pphead)//头删 { assert(pphead); assert(*pphead);//暴力检查 //假设前面只有一个结点 //和 //假设前面有结点 SLTNode* first = *pphead; *pphead = first->next;//将第二个结点与指向链表的指针链接 free(first);//删除第一个结点 first = NULL; }
🍭1.6单链表的查找
单链表的查找，就是根据所给的数据进行遍历，没有什么好的方法
如果与给的数据相同则返回该地址。如果找不到就返回NULL。
通常查找与修改连在一起，先查找到该结点的数据，然后对该数据进行修改。
SLTNode* SLTFind(SLTNode** pphead, SLTData x)//查找 { assert(pphead); SLTNode* cur = *pphead; while (cur) { if (cur->next == x) { return cur; } cur = cur->next; } return NULL; }
🍭1.7单链表的插入
与上面的讲的单链表的头插和尾插不一样，这里讲的是给定位置pos，然后将数据插入想要插入的位置，不过对于单链表的插入，通常都是在位置pos的前面插入数据，而不是在pos的后面插入数据，我们分别来看看这两种插入的不同
在pos前面插入就想要pos前面结点的地址了，并且遍历循环的条件也发生变化。
插在pos的前面
1.如果链表有结点，那我们将新结点与pos位置前面的结点链接起来，再让pos与新结点链接起来。
如果没有结点就相当于头插了。
2.插在pos的后面
插在后面都不要遍历找了，直接将新结点放在pos的后面，将pos的next与新结点链接，再将新结点与pos链接
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTData x)//在pos位置前面插入 { assert(pphead); assert(pos); //如果没有结点 if (pos == *pphead) { SLTpushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySLTNode(x); prev->next = newnode; newnode->next = pos; } } void SLTInsertAfter( SLTNode* pos, SLTData x)//在pos位置之后插入 { assert(pos); SLTNode* newnode = BuySLTNode(x); newnode->next = pos->next; pos->next = newnode; }
🍭1.8单链表的删除
单链表的删除分为在pos位置的前面删除还是在后面删除
不过首先都需要对二级指针和一级指针断言。
1.在pos位置之前删除
假设前面有结点，删除pos前面的结点，需要前面结点位置的地址
找到后将该结点点释放。
假设前面只有一个结点，相当于头删。
2.在pos位置之后删除
首先要将pos后面的结点的位置记录下来
然后将后面的结点与pos链接起来将pos后面的结点释放
void SLTErase(SLTNode** pphead, SLTNode* pos)//在pos位置之前删除 { assert(pphead); assert(pos); if (*pphead == pos) { SLTpopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev->next = pos->next; } free(pos); pos = NULL; } } void SLTEraseAfter( SLTNode* pos)//在pos位置之后删除 { assert(pos); SLTNode* del = pos->next; pos->next = del->next; free(del); del = NULL; }
