单链表的实现（C语言）

单链表的结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

链表就好比是一辆火车，有很多的车厢，在链表中，被称为节点。节点由数据加指向下一个节点的指针构成。

//创建节点
typedef int SLDataTpye;
typedef struct SlistNode
{SLDataTpye data;struct SListNode* next;
}SLNode;

当创建一个新的节点时，你需要为这个节点分配内存，并初始化它的数据部分。同时，因为开始时这个节点是孤立的，它后面没有其他节点，所以next指针应该指向NULL，表示链表的结束。

我们先来创建几个节点并让它们连接起来。

void test()
{//创建几个节点SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));node1->data = 1;SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));node2->data = 2;SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));node3->data = 3;SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));node4->data = 4;//将节点连接起来node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;
}int main()
{test();return 0;
}

node1的下一个节点指向node2，node2的下一个节点指向node3，node3的下一个节点指向node4，node4的下一个节点指向空，结束链表。

如此链表算是创建成功了。我们接下来在控制台上打印出链表。

//打印链表
void SLPrint(SLNode* phead); //创建一个指向节点的指针,让它先置为空void SLPrint(SLNode* phead)
{SLNode* pcur = phead;while (pcur)  //pcur != NULL{printf("%d->", pcur->data);pcur = pcur->next; //移向下一个节点}printf("NULL\n");
}

SLNode* plist = node1;
SLPrint(plist);

创建了一个结构体指针 plist 指向node1，然后将实参 pilst 传递给 形参 phead，此时phead等于node1，然后将phead赋给结构体指针pcur。

 单链表的增加

如果我们要再给链表插入一些值该怎么办？有两种方法：头插和尾插

尾插

//新增节点
SLNode* SLBuyNode(SLDataTpye x)
{//申请空间给新的节点SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));//判断申请空间是否成功if (newnode == NULL){perror("malloc error");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//尾插
void SLPushBack(SLNode** pphead, SLDataTpye x);void SLPushBack(SLNode** pphead, SLDataTpye x)
{assert(pphead);//新增节点SLNode* newnode = SLBuyNode(x);SLNode* ptail = *pphead;  //*pphead  指向第一个节点的指针，所以让ptail指向第一个节点//两种情况  空链表和非空链表// 判断是否为空if (*pphead == NULL){*pphead = newnode;}else{//要先找到尾while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}

要尾插一个数据首先要先增加一个节点，我将增加节点重新封装成一个函数，新申请一个节点空间，然后将要加入的数据存储再节点的data里面，然后将节点的下一个指针指向空。最后返回新增的节点。

刚开始链表有两种情况，一种是空链表，没有数据，一种是非空链表，链表中有数据。如果指向第一个节点的指针为空，那么将指向第一个节点的指针指向新增的节点newnode。创建一个指针 ptail 让它指向链表的头节点，如果链表不为空，就找到链表的尾部，只需要 ptail 的下一个节点为空，那么此时ptail就是链表的尾部，然后让 ptail 的下一个节点指向新增节点newnode就完成了尾插操作。

这里为什么要传 plist 的地址？ 因为形参的改变要影响实参，‌实参必须传地址。‌这里创建了一个空链表进行尾插操作，当完成尾插操作时链表发生了改变，也就是形参发生了改变。形参的改变要影响实参，‌实参必须传地址，此时形参和实参共用一块内存空间。如果不传地址，形参的改变无法影响到实参，那么函数调用结束时，实际上链表没有变化，

实参传递一个一级指针的地址时，‌形参需要用二级指针来接收。‌在C语言中，‌当需要传递一个一级指针的地址作为参数时，‌形参必须使用二级指针来接收。‌这是因为一级指针本身已经是一个地址，‌而当我们需要传递这个地址的地址（‌即一级指针的指针）‌时，‌就需要使用二级指针。‌二级指针可以看作是指向一级指针的指针，‌它能够接收实参传递的一级指针的地址，‌从而实现对一级指针的修改或操作。‌

 这里用assert断言一下，是因为指向第一个节点的指针的地址不能为空，为空就不能对其进行解引用，找不到第一个节点了。

头插

//头插
void SLPushFront(SLNode** pphead, SLDataTpye x)
{//二级指针传的不能为空assert(pphead);SLNode* newnode = SLBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

相较与尾插相比，头插就简单多了。新增一个节点，让新节点的下一个指针指向头节点。然后让新节点成为头节点。如果链表是空链表也可以这样。

单链表的删除

 单链表的删除也可以分为头删和尾删。

尾删

//尾删
void SLPopBack(SLNode** pphead)
{//指向第一个节点的指针不能为空，指向第一个节点的指针的地址不能为空assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* prev = *pphead;SLNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}//将删除的空间置为空prev->next = NULL;}
}

尾删也同样分一个节点还是多个节点。若是只有一个节点，即头节点，将这个节点的空间释放掉，然后将头节点置为空。这里要注意 * 的优先级要小于 -> 。

若是多个节点， 首先要先找到尾节点。但是找到尾节点后要删除尾节点，那么怎么将尾节点的那块空间置为空呢？这里创建两个指针，一个用来记录尾节点，另一个用来记录尾节点的前一个节点。找到尾之后，直接将尾节点的那块空间置为空就行了。

这里断言一下，二级指针不能为空，另外指向头节点的指针不能为空，为空那还删什么呢？

头删

//头删
void SLPopFront(SLNode** pphead)
{assert(pphead && *pphead);SLNode* last = (*pphead)->next;//last用于指向头节点的下一个节点free(*pphead);*pphead = last;
}

头删就不用分什么一个节点还是多个节点了，因为有头就行。

创建一个指针使其指向头节点的下一个节点，释放掉头节点的空间，然后last节点成为新的头节点。

单链表的查找

//查找
SLNode* SLFind(SLNode* phead, SLDataTpye x)
{SLNode* pcur = phead;if (pcur->data == x){return pcur;}else{pcur = pcur->next;}return pcur;
}

因为是在链表中查找数据，并不需要对链表进行修改，说以传递第一个节点的指针就行了，用一级指针接收。返回类型是 SLNode* 类型，说明返回的是一个节点。

在指定位置之前插入数据

//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataTpye x)
{//二级指针不能传空，链表不能为空assert(pphead && *pphead);//*pphead 为空说明指向第一个节点的指针为空，链表为空assert(pos);//指定位置不能为空SLNode* newnode = SLBuyNode(x);//*pphead = posif (pos == *pphead){//头插SLPushFront(pphead, x);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}

要在指定位置之前插入数据，就要知道指定位置的节点和它的前一个节点的位置。 二级指针不能传空，链表不能为空。指定位置不能为空。

假设要在3这个位置之前插入一个数据，那么先用SLFind函数查找到3这个节点，然后将这个节点返回给pos，这样就知道了指定位置在链表的那个地方。然后创建一个指向头节点的指针，遍历链表，通过while循环这个指针的下一个节点不指向pos，那么循环结束的时候它就是pos的前一个节点。

新增一个要插入数据的节点，先让新增节点的下一个指针指向pos，然后让pos的前一个节点指向新增节点。

如果指定位置为头节点，那么直接进行头插即可。

在指定位置之后插入数据

//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataTpye x)
{assert(pos);SLNode* newnode = SLBuyNode(x);newnode->next = pos;pos->next = newnode;//这两个顺序不能倒，倒了相当于newnode节点指向newnode节点
}

在指定位置之后插入数据，就要知道指定位置的节点和它的下一个节点，指定位置的节点可以通过SLFind函数查找后返回。所以只需要断言一下指定位置不能为空。

图中的这两个1和2位置顺序不能反，如果先2后1，那么就找不到指定位置的下一个节点了。另外，如果指定位置为尾节点，这个代码也没有什么问题。

删除指定位置

//删除指定位置
void SLErase(SLNode** pphead, SLNode* pos)
{//二级指针不能传空，链表不能为空,指定位置不能为空assert(pphead && *pphead && pos);SLNode* prev = *pphead;if (pos == *pphead){SLPopFront(pphead);}else{while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

要删除指定位置，就要知道指定位置的前一个节点和后一个节点。指定位置已经被传过来，那么它的下一个节点也可以知道。它的前一个节点就需要用循环去遍历。另外，如果指定位置在头节点的话，直接调用头删函数即可。

删除指定位置之后的节点

//删除指定位置之后的节点
void SLEraseAfter(SLNode* pos)
{assert(pos && pos->next);//pos->next是避免pos为尾节点,尾节点之后没有节点可删SLNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

要删除指定位置之后的节点就要知道指定位置和它的后一个节点。它被传过来了很容易知道。

让指定位置的节点指向它的下下个节点，同时将它的下个节点的空间释放掉，就完成了。另外，如果指定位置的下一个节点的位置为空的话，实现不了删除操作，所以我们要断言一下。

单链表的销毁

//销毁链表
void SLDesTory(SLNode** pphead)
{assert(pphead && *pphead);SLNode* pcur = *pphead;while (pcur){SLNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

 链表的销毁首先，链表不能不为空，链表为空就不用进行销毁了，还有二级指针不能为空。所以要断言一下。

从头开始销毁链表是最好的，创建一个指针指向头节点的下一个节点，然后销毁头节点，最后让头节点的下一个指针成为新的头节点，遍历销毁链表。最后还有将链表置为空。

测试代码

#define _CRT_SECURE_NO_WARNINGS 1#include "Slist.h"void test1()
{//创建几个节点SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));node1->data = 1;SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));node2->data = 2;SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));node3->data = 3;SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));node4->data = 4;//将节点连接起来node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;//打印链表SLNode* plist = node1;SLPrint(plist);
}void test2()
{SLNode* plist = NULL;printf("尾插\n");SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLPrint(plist);printf("\n");printf("头插\n");SLPushFront(&plist, 5);SLPushFront(&plist, 6);SLPushFront(&plist, 7);SLPushFront(&plist, 8);SLPrint(plist);printf("\n");printf("尾删\n");SLPopBack(&plist);SLPopBack(&plist);SLPrint(plist);printf("\n");printf("头删\n");SLPopFront(&plist);SLPopFront(&plist);SLPrint(plist);printf("\n");printf("查找\n");SLNode* find1 = SLFind(plist, 6);if (find1 == NULL){printf("不存在\n");}else{printf("存在\n");}printf("在指定位置之前插入数据\n");SLInsert(&plist, find1, 11);SLPrint(plist);printf("\n");printf("在指定位置之后插入数据\n");SLInsertAfter(find1, 99);SLPrint(plist);printf("\n");printf("删除指定位置的节点\n");SLErase(&plist, find1);SLPrint(plist);printf("\n");printf("删除指定位置之后的节点\n");SLNode* find2 = SLFind(plist, 5);SLEraseAfter(find2);SLPrint(plist);printf("\n");SLDesTory(&plist);
}int main()
{//test1();test2();return 0;
}