单链表逻辑结构梳理

1.1链表的概念及结构

概念：链表是一种物理存储结构上的非连续，非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的种类包含：单向，双向，带头，不带头，循环，非循环。在八种链表结构中最常用的包含无头单向非循环链表，以及带头双向循环链表。

无头单项非循环链表：结构简单，一般不会单独来存储数据。实际中更多是作为其他数据结构的子结构，入哈希桶，图的邻接表等等

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。虽然这个结构复杂，但是使用代码以后会发现该结构会带来很多优势。

在SList.h该文件中写文件声明以及结构体的定义

#include<stdlib.h> #include<assert.h> #include<stdio.h> //定义结点的结构 //数据+指向下一个节点的指针 typedef int SLDataType; typedef struct SListNode { SLDataType data; struct SListNode* next; }SLTNode; void SLTPrint(SLTNode*pphead); //尾插 void SLTPushBack(SLTNode**pphead, SLDataType x); //头插 void SLTPushFront(SLTNode**pphead, SLDataType x); void SLTPopBack(SLTNode** pphead); //头删 void SLPopFront(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode* phead, SLDataType x); //在指定位置之前插入数据 void SLTInsert(SLTNode**pphead, SLTNode* pos, SLDataType x); //在指定位置之后插入数据 void SLTInsertAter(SLTNode* pos, SLDataType x); //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos); // 删除pos 之后的节点 void SLTEraseAfter(SLTNode * pos); void SListDesTroy(SLTNode** pphead);

在这里使用typedef重新定义int类型，在之后对于链表的使用如果存储其他类型的数据的时候就可以直接在这里修改，定义变量的时候就使用SLDatatype。使用struct结构体，成员变量分为data以及SListNode*next。前者是在链表节点中存储的数据，而后者则是用来链接节点之间的桥梁。

在具体解释各个接口之前，要解释的是如何在使用之前创建节点

SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode)); node1->data = 1; SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode)); node2->data = 2; SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode)); node3->data = 3; SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode)); node4->data = 4;//建立了四个节点并储存从1到4，四个数字 //将四个节点连接起来 node1->next = node2; node2->next = node3; node3->next = node4; node4->next = NULL;

在这里首先定义SLTNode*类型的node1变量，该指针指向的是malloc后的空间的地址，然后解引用该地址将成员变量data进行赋值（将数据存储在节点中），然后将节点链接在一起，将后一个节点的地址赋值给前一个节点的成员变量（next）。
链表数据的打印

void SLTPrint(SLTNode* phead) {
SLTNode* pcur = phead;
while (pcur)//pcur!=NULL
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");

}

该接口使用传地址修改的方式，然后将传参地址重新赋给一个新的SLTNode*pcur来接收地址，避免对原地址进行修改。尾节点的next指针最终指向NULL，所以在这里的while循环结束条件就是当pcur最终指向空，然后是对pcur循环赋值更新，不断将下一节点的地址赋值给pcur。

对于创建新的节点以及赋值接口

SLTNode* SLTBuyNode(SLDataType x) {
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//因为malloc返回的是申请的空间的地址，要使用指针来进行解引用
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
在这里SLTNode*是返回的值newnode的类型，在这里先通过malloc 来在堆上，然后再进行if判断新节点是否为空，如果为空则证明申请空间失败通过perror来打印出错误。如果是exit（0）证明程序正常结束，然后返回0给操作系统。如果是非0则程序异常退出，告知系统运行错误。

然后将传递的参数x赋值给这个新节点，然后将next赋值为NULL,最后再返回这个新的指针的地址

节点的尾插

//在这里进行二级指针的传参，有两方面的考虑，一方面是为了防止出函数后，堆内存销毁，所以在这里要进行传地址，&plist传递的是这个给变量本身的地址，然后*plist得到的就是这个节点的地址。
//然而在这SLTNode**pphead是为了保证类型匹配 SLTNode* ptail = *pphead;在这里*pphead就是SLTNode*类型从而实现类型匹配进行赋值运算

void SLTPushBack(SLTNode** pphead, SLDataType x) {

assert(pphead);//增加断言不能为空，无法解引用空指针
SLTNode* newnode = SLTBuyNode(x);//申请新的 节点
//SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));//在这里定义插入新的节点
//在这里先找到尾结点，再将尾节点和新节点连接在一起

//空链表和非空链表
if (*pphead == NULL) {
*pphead = newnode;
}

else{
SLTNode* ptail = *pphead;
while (ptail->next != NULL) {//在这里的循环判断表达式节点中储存的下一个结点的地址不为空
ptail = ptail->next;
}//patil指向的就是尾节点
ptail->next = newnode;
}

}

在这里使用二级指针传参，一方面考虑的是类型匹配问题，另一方面则是为了保证传地址修改。使用断言，保证传参地址不为空，然后使用SLTBuyNode函数来申请新的节点。接下来进行判断传参地址表示的是空链表还是非空链表，如果是空链表，就使得新节点作为该链表的头节点，如果为非空链表，则使用while循环来找到尾节点，然后将新节点插入到尾节点之后。

头插节点接口

void SLTPushFront(SLTNode** pphead, SLDataType x) {
assert(pphead);
SLTNode* newnode = SLTBuyNode（x）;
//newnode *pphead
newnode->next = *pphead;//将新节点与原本的第一个节点相连接
*pphead = newnode;//在使得该指针指向第一个节点 在这里*pphead相当于一个用来遍历每一个节点的指针，在这里插入新的节点后要使得这个指针指向头节点
}

在这里传参使用二级指针的目的与尾插的目的相同，另外直接将新节点插入链表开头，即将新节点的成员变量next储存*pphead该节点的地址，使得插入节点与原头节点相连。在这里*pphead始终是指向头节点的指针变量，所以对其进行重新赋值，使其指向新的头节点。

删除节点接口

void SLTPopBack(SLTNode** pphead) {
assert(pphead && *pphead);
//链表不能为空

//链表只有一个节点
if ((*pphead)->next == NULL)//->的优先级高于*
{
free(*pphead);
*pphead = NULL;
}

else {
SLTNode* prev = *pphead;
SLTNode* ptail = *pphead;
while (ptail->next) {
prev = ptail;//在这里循环从前往后推移，直到patil指向最后一个节点而prev为上一个节点
ptail = ptail->next;
}
//在这里prev为删除的那个节点的上一个节点中存储的地址，因为最后一个节点被删除，所以prev->next应该指向NULL
//prev patil
//释放
free(ptail);
ptail = NULL;
prev->next = NULL;//在这里之所以要设置两个指针前后遍历，因为在尾删这一块，不仅仅是要free尾节点，也要使得上一个节点的next为NULL,从而要得到尾节点的上一个节点的地址
}
}
在这里断言链表不能为空，且指向头节点的指针不能为空。然后使用if判断分支，当链表只有一个节点的情况，以及当链表不是只有一个节点的情况。当只有单个节点的时候，直接将该节点free掉，将堆上内存还回去。然后将指向头节点的指针置为空，避免野指针的出现。当不是单个节点的情况下，先定义两个SLTNode*类型的指针，一个指向尾节点，而另一个指向该尾节点的前一个节点，具体操作逻辑是，使用while循环，终止条件是当ptail中的成员变量next为空。然后进行遍历循环，从头节点开始。然后同样进行free将堆上内存释放，再者将尾节点置为空，将前一个节点的成员变量next置为空。

头删接口

void SLPopFront(SLTNode** pphead) {//既可以处理多节点的情况也可以处理单个节点的情况
//链表不能为空
assert(pphead && *pphead);
//在这里next只是一个临时的变量，来存储指向第二个节点的地址
SLTNode* next = (*pphead)->next;//->优先级高于*

free(*pphead);
//在这里使得next中的地址转移给*pphead来作为头节点
*pphead = next;//使得*pphead指向第二个节点，让第二个节点成为头节点
}

在这里为避免删除头节点之后而找不到新的链表的头节点的地址，先定义一个指针来直线头节点的下一个节点，然后将原头节点堆上空间释放。然后将指向头节点的指针指向新的头节点。

节点查找接口

SLTNode* SLTFind(SLTNode* phead, SLDataType x) {
//在链表中查找节点中存储的数据
SLTNode* pcur = phead;//为了不修改phead这个指针，因为在最后pcur最后会为空
while (pcur)//等价于pcur!=NULL;
{
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;//在这里通过不断把下个节点的地址赋值给指针从而借助while循环实现遍历
}
//pcur==NULL;在这里pcur可能最后为NULL,为此在这使用pcur指针代替指针phead;
return 0;

}//在这里**pphead是有可能值被改变的，而pos是指拿来使用而不会被改变

因为最后pcur会为空，如果直接在原来指向头节点的指针上修改则会被修改，所以在这里设置一个临时变量。使用while循环，当节点中的成员变量正好等于数据x的时候就直接返回该节点的地址，在循环过程中pcur指针是不断更新，指向下一个节点的。当最终没有查找到对应的值的时候就直接结束。

在指定的节点前插入新的节点的接口

void SLTInsert(SLTNode** pphead,SLTNode *pos, SLDataType x) {
assert(pphead && *pphead);//在这里因为要找到对应的所要找到的节点的位置不为空
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//若pos==*pphead;说明是头插
if (pos == *pphead) {
SLTPushFront(pphead, x);
}
else{
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos) {
prev = prev->next;

}
//要让prev ->newnode -> pos 三者手牵手，然后地址相连接
newnode->next = pos;
prev->next = newnode;
}

}

同样在这里通过断言保证链表以及头节点指针不为空，以及所查找的节点的地址不为空。然后使用if判断如果目标节点是头节点的情况下就直接调用头插函数，如果不是头节点的情况下创建一个新的指针变量先储存头节点的地址，避免对链表原头节点的地址进行修改。然后进行while循环来找到目标节点的前一个节点，然后让该节点的成员变量next等于插入的新的节点的地址，然后让该新节点的next保存目标节点的地址，然后最后通过next，串联起来，使得三个节点实现了链接。

在目标节点之后插入新的节点

//在指定位置之后插入数据
void SLTInsertAter(SLTNode* pos, SLDataType x)//为什么没有头节点
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next=pos->next;
pos->next = newnode;

}

在这里先assert断言避免目标节点的地址为空，然后创建一个新的节点，使其成员变量next与目标节点的next相等，表示为新的节点代替目标节点来指向下一个节点，然后再将新的节点与目标节点相连，pos->next=newnode，实现原目标节点与新节点的相连，与目标节点的下一个节点的相连。

删除节点操作接口

void SLTErase(SLTNode** pphead, SLTNode* pos) {
assert(pphead && *pphead);
//pos是头节点
if (pos == *pphead) {
SLPopFront(pphead);
}

else {
SLTNode* prev = *pphead;
while (prev->next != pos) {
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}

在该接口中传参头节点地址，然后分支进行判断，如果目标节点等于头节点，就直接进行头删操作，else则将头节点地址赋值给一个新的指针变量，避免堆原头节点的地址的修改。然后通过while循环来遍历到目标节点的前一个节点。然后先将目标价节点的下一个节点的地址赋值给目标节点的前一个节点的成员变量next，目的是将目标节点删除后依旧可以保证链表的连续性，然后再进行空间释放操作以及赋空操作

删除目标节点之后的节点的接口

void SLTEraseAfter(SLTNode* pos) {


assert(pos && pos->next);
SLTNode* del = pos->next;
//pos del del->next就相当于pos->next->next
pos->next = del->next;
free(del);
del = NULL;
}

删除目标节点，先将目标节点下一个节点的地址赋值给新的指针变量，来避免数据的丢失，然后再将目标前一个节点的成员变量next被赋值为目标节点的下一个节点的地址，实现节点直接的相连。在保证目标节点前后的节点相连后才能对目标节点进行空间释放及赋空。

销毁链表操作接口

void SListDesTroy(SLTNode** pphead) {
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur) {
SLTNode* next = pcur->next;
free (pcur);
pcur = next;
}
//pcur
*pphead = NULL;//在这里使得头节点为空
}

在实现链表的销毁的操作过程中，是节点逐个销毁的过程，将后一个节点的地址赋值给新定义的相同类型的指针变量，然后再对pcur这个指向节点的指针进行释放，之后再将保留下一个节点的地址的next赋值给pcur，来进行循环，直到pcur指针为空则标志着销毁完成，在进行free销毁后，*pphead这个指向头节点的指针赋值为空，避免野指针。

结言：对于单链表的解释和一些说法可能不够清楚犀利，个人的见解和认识，也是在数据结构的学习的开始时写的，如果有错误和解释有误的地方，欢迎指出