从0开始创建单链表

前言

       这次我来为大家讲解链表，首先我们来理解一下什么是单链表，我们可以将单链表想象成火车

每一节车厢装着货物和连接下一个车厢的链子，单链表也是如此，它是将一个又一个的数据封装到节点上，节点里不仅包含着数据，还又指向下一个节点的指针。

因此单链表的结构体表示如下：

typedef int SLTDataType;typedef struct SListNode
{int data;struct SListNode* next;
}SListNode;

所以单链表的特点是：

在物理结构上不一定是线性的
在逻辑结构上是线性的

我们通常会将单链表抽象成如下图所示: 这样会方便我们接下来的思考和代码的实现。

单链表代码实现

打印

我们先来写打印代码，这个代码也方便我们后期的测试。

打印单链表，我们需要遍历单链表的所有数据，这个函数的形参传一级指针就可以了，因为打印并不需要改变头指针。

void SListPrint(SListNode* phead)
{SListNode* ptail = phead;while (ptail){printf("%d->", ptail->data);ptail = ptail->next;}printf("NULL\n");
}

这里定义一个变量ptail，是为了不想改变phead，说不定哪天要在这个函数再次使用phead，所以我定义了一个ptail来进行遍历，以便后面想使用phead的时候，可以快速增加代码

创建新节点

鉴于插入数据都需要创建一个新节点，为了方便后面的头插，尾插等各种插入，于是我们来封装一个函数来创建新节点：

SListNode* CreatNewnode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

尾插

尾插需要在单链表的尾部插入一个新的数据，画图理解一下：

需要我们找到单链表原先的尾节点，将尾节点的next指向newnode，于是我们很快就会写出如下的代码：

void SListPushBack(SListNode** pphead, SLTDataType x)//尾插
{assert(pphead);SListNode* newnode = CreatNewnode(x);//找尾节点SListNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = newnode;
}

由于上面的代码是基于链表不为空这一种情况实现的，这时候我们还要思考，如果链表为空的时候，上面的代码还能实现吗？

我们来走一下代码，如果链表为空，pcur==NULL，pcur->next一定会报错，对空指针是不能解引用的，所以上面的代码无法处理链表为空的情况，我们就需要单独进行处理！！！

这个尾插代码应该是这样的：

void SListPushBack(SListNode** pphead, SLTDataType x)//尾插
{assert(pphead);SListNode* newnode = CreatNewnode(x);//如果链表为空if (*pphead == NULL){*pphead = newnode;}else{//找尾节点SListNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}

所以当链表为空的时候，我们需要改变头指针的指向，所以传二级指针！！！

头插

头插需要我们在单链表的最前面插入一个数据，我们画图来理解一下：

头插很显然要改变头指针，所以形参要影响实参需要传二级指针。

这时候是先newnode指向原先的第一个节点，再改变phead？还是先改变phead再将newnode 指向原先的第一个节点？

在不创建另外一个变量的时候，我们要找到原先第一个节点只能通过phead->next，如果先改变了phead 的话，我们就找不到原先的第一个节点了。
所以需要将新节点的next指向原先的第一个节点，然后我们将头指针改变，指向新节点。

void SListPushFront(SListNode** pphead, SLTDataType x)//头插
{assert(pphead);SListNode* newnode = CreatNewnode(x);newnode->next = *pphead;*pphead = newnode;
}

这个时候，由于上面的代码还是基于链表不为空的条件下进行的，所以我们还要考虑链表为空的情况，走一下代码，*pphead == NULL，newnode->next = NULL，*phead = newnode ，很显然这个代码也能处理好链表为空的情况，于是我们不需要任何的改动。

尾删

尾删指删除单链表最后一个节点。画图理解一下：

这时候我们需要找到尾节点和尾节点的前一个节点，将尾节点释放掉，改变现在的尾节点的next指向，置为NULL。

所以我们需要两个临时变量，一个来遍历链表找到尾节点，一个来保存上一个节点！！！

这时我们来写代码：

void SListPopBack(SListNode** pphead)//尾删
{assert(pphead && *pphead);//不能传NULL，链表也不能为空//找尾节点SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);pcur = NULL;prev->next = NULL;}

这里我们需要断言一下，就是链表不能为空，链表为空，删什么？

上面的代码是基于链表至少又两个节点的情况下，如果链表只有一个节点呢？也就是头指针指向的就是你要尾删的节点，走一下代码：*pphead == NULL，pcur = prev =NULL，此时while(pcur->next)，对空指针解引用，直接报错，既然如此，我们就写多一点代码来专门处理只有一个节点的情况。

void SListPopBack(SListNode** pphead)//尾删
{assert(pphead && *pphead);//不能传NULL，链表也不能为空//链表只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找尾节点SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);pcur = NULL;prev->next = NULL;}
}

由于可能会出现只有一个节点的情况，删除的话也需要改变头指针，所以传二级指针。

头删

头删指删除第一个节点。画图理解一下：

我们需要改变头指针的指向，所以必须传二级指针！！！

void SListPopFront(SListNode** pphead)//头删
{assert(pphead && *pphead);//不能传NULL，链表也不能为空SListNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

老规矩，如果链表只有一个节点，走一下代码：SListNode->next = (*pphead) -> next =NULL; 释放掉第一个节点，*pphead = next = NULL，刚好可以处理这种情况，代码不需要修改。

查找

写查找代码也是方便我们后续的指定位置的插入删除作准备。

这个代码和简单，只需要遍历单链表。

SListNode* SListFind(SListNode* phead, SLTDataType x)
{SListNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

删除指定节点

我们画图理解一下：

我们需要改变两个个节点，pos前一个节点的next指向改成pos后一个节点。

void SListPopPos(SListNode** pphead, SListNode* pos)
{assert(pphead && *pphead);assert(pos);SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}

如果pos节点就是第一个节点（即pphead == pos)，我们来走一下代码，在while循环中pcur->next 不会找到pos，因为pcur = *phead = pos，所以循环最后会导致pcur走到NULL，然后发生对空指针的解引用，所以我们需要单独处理这一种情况

void SListPopPos(SListNode** pphead, SListNode* pos)
{assert(pphead && *pphead);assert(pos);if (pos == *pphead){//调用头删SListPopFront(pphead);}else{SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}

由于pos 就是头指针，所以pos的删除就是头删，我们可以调用我们之前写好的头删函数，无论你要不要调用头删函数，都要对头指针进行修改，所以要传二级指针（头指针的地址）。而pos不需要传二级指针是因为一般情况下我们不会再次使用pos，所以我们不需要改变pos的指向，也就不用传pos 的地址过去。

删除指定位置之前的数据

画图理解：

我们需要找到pos前两个节点，释放pos 前一个节点，改变pos前前节点的next 的指向，变为指向pos这个节点。

void SListPopPosFront(SListNode** pphead, SListNode* pos)
{assert(pphead && pos); assert(pos != *pphead);SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next != pos){prev = pcur;pcur = pcur->next;}prev->next = pos;free(pcur);pcur = NULL;}

我们要考虑一下如果pos前面只有一个节点的情况下，我们来走一下代码：当prev->next = pos(pphead = pos)，释放pcur（也就是释放了pphead)。这时候头指针没了，你找不到后面的数据了！！！

所以我们单独处理一下这种情况。

void SListPopPosFront(SListNode** pphead, SListNode* pos)
{assert(pphead && pos); assert(pos != *pphead);if ((*pphead)->next == pos){//头删SListPopFront(pphead);}else{SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next != pos){prev = pcur;pcur = pcur->next;}prev->next = pos;free(pcur);pcur = NULL;}
}

头删，需要改变头指针的指向，所以要用二级指针来接收头指针的地址。

删除指定位置之后的数据

画图理解：

由于我们可以通过pos 就可以找到pos后面的节点，所以我们直接传pos就可以了。

我们需要找到pos后后一个节点，然后改变pos 的next 指向指向后后一个节点，为了方便书写代码，我们可以定义一个临时变量del来保存要删除的节点。

这里要注意，指定位置之后必须要有一个节点，否则删什么？所以这里断言一下。

void SListPopPosAfter(SListNode* pos)
{assert(pos && pos->next);SListNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

我们来考虑一下，如果要删除的节点刚好是尾节点，我们来走一下代码：pos->next = del->next = NULL；free(del)，没有问题，那就不用单独处理。

指定位置前插入

画图理解一下：

我们需要改变前一个节点，为了找到pos 的前一个结点，我们需要传入头指针对链表进行遍历。

void SListPushPosFront(SListNode** pphead, SListNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SListNode* newnode = CreatNewnode(x);SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}newnode->next = pos;pcur->next = newnode;
}

如果pos就是第一个节点，上面的代码中while循环就无法找到pos前一个节点，所以我们要单独处理一下这种情况，这时可以调用一下我们写过的头插函数。

头插，需要改变头指针，所以传二级指针。

void SListPushPosFront(SListNode** pphead, SListNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);if (*pphead == pos){//头插SListPushFront(pphead, x);}else{SListNode* newnode = CreatNewnode(x);SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}newnode->next = pos;pcur->next = newnode;}
}

指定位置之后插入

画图理解一下：

这个代码我们可以通过pos找到pos后一个节点，所以不需要传入头指针。

void SListPushPosAfter(SListNode* pos, SLTDataType x)
{assert(pos);SListNode* newnode = CreatNewnode(x);SListNode* next = pos->next;pos->next = newnode;newnode->next = next;
}

我们来考虑一下pos就是尾节点的情况，能不能走得通，走一下代码，next = pos->next = NULL，pos->next = newnode，newnode->next = next = NULL，可以，没有任何问题，就不需要改代码了。

销毁链表

销毁链表需要一个一个节点依次删除，所以要遍历链表。

void SListDestroy(SListNode** pphead)
{SListNode* pcur = *pphead;while (pcur){SListNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

测试

每写完一个函数，我们就需要进行调试测试来看代码有没有问题，这时一个好的习惯，希望各位也能这样做。

一下是我自己的测试代码：我放在了test.c文件里（就是测试文件）

#include "SList.h"void test1()
{SListNode* plist = NULL;//测试尾插//SListPushBack(&plist, 1);//SListPrint(plist);//SListPushBack(&plist, 2);//SListPrint(plist);//SListPushBack(&plist, 3);//SListPrint(plist);//测试头插SListPushFront(&plist, 10);SListPrint(plist);SListPushFront(&plist, 20);SListPrint(plist);SListPushFront(&plist, 30);SListPrint(plist);//测试尾删/*  SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);*///测试头删//SListPopFront(&plist);//SListPrint(plist);//SListPopFront(&plist);//SListPrint(plist);//SListPopFront(&plist);//SListPrint(plist);//测试查找/*   SListNode* find = NULL;find = SListFind(plist, 30);*//*   if (find == NULL){printf("找不到\n");}else{printf("找到了！%d\n", find->data);}*///测试删除pos节点/*SListPopPos(&plist, find);SListPrint(plist);*///删除指定位置之前的数据//SListPopPosFront(&plist, find);//SListPrint(plist);//删除指定位置之后的数据/* SListPopPosAfter(find);SListPrint(plist);*///指定位置前插入/*   SListPushPosFront(&plist, find, 100);SListPrint(plist);*///指定位置之后插入/*  SListPushPosAfter(find, 100);SListPrint(plist);*/SListDestroy(&plist);SListPrint(plist);
}int main()
{test1();return 0;
}

分装函数

SList.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;typedef struct SListNode
{int data;struct SListNode* next;
}SListNode;//打印
void SListPrint(SListNode* phead);//插入
void SListPushBack(SListNode** pphead, SLTDataType x);//尾插
void SListPushFront(SListNode** pphead, SLTDataType x);//头插//删除
void SListPopBack(SListNode** pphead);//尾删
void SListPopFront(SListNode** pphead);//头删//查找
SListNode* SListFind(SListNode* phead, SLTDataType x);//删除pos节点
void SListPopPos(SListNode** pphead, SListNode* pos);//删除指定位置之前的数据
void SListPopPosFront(SListNode** pphead, SListNode* pos);//删除指定位置之后的数据
void SListPopPosAfter(SListNode* pos);//指定位置前插入
void SListPushPosFront(SListNode** pphead, SListNode* pos, SLTDataType x);//指定位置之后插入
void SListPushPosAfter(SListNode* pos, SLTDataType x);//销毁链表
void SListDestroy(SListNode** pphead);

SList.c

#include "SList.h"//创建新节点
SListNode* CreatNewnode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//打印
void SListPrint(SListNode* phead)
{SListNode* ptail = phead;while (ptail){printf("%d->", ptail->data);ptail = ptail->next;}printf("NULL\n");
}//插入
void SListPushBack(SListNode** pphead, SLTDataType x)//尾插
{assert(pphead);SListNode* newnode = CreatNewnode(x);//如果 *pphead==NULLif (*pphead == NULL){*pphead = newnode;}else{//找尾节点SListNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}void SListPushFront(SListNode** pphead, SLTDataType x)//头插
{assert(pphead);SListNode* newnode = CreatNewnode(x);newnode->next = *pphead;*pphead = newnode;
}void SListPopBack(SListNode** pphead)//尾删
{assert(pphead && *pphead);//不能传NULL，链表也不能为空//链表只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找尾节点SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);pcur = NULL;prev->next = NULL;}
}void SListPopFront(SListNode** pphead)//头删
{assert(pphead && *pphead);//不能传NULL，链表也不能为空SListNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{SListNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//删除pos节点
void SListPopPos(SListNode** pphead, SListNode* pos)
{assert(pphead && *pphead);assert(pos);if (pos == *pphead){//调用头删SListPopFront(pphead);}else{SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}//删除指定位置之前的数据
void SListPopPosFront(SListNode** pphead, SListNode* pos)
{assert(pphead && pos); assert(pos != *pphead);if ((*pphead)->next == pos){//头删SListPopFront(pphead);}else{SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next != pos){prev = pcur;pcur = pcur->next;}prev->next = pos;free(pcur);pcur = NULL;}
}//删除指定位置之后的数据
void SListPopPosAfter(SListNode* pos)
{assert(pos && pos->next);SListNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//指定位置前插入
void SListPushPosFront(SListNode** pphead, SListNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);if (*pphead == pos){//头插SListPushFront(pphead, x);}else{SListNode* newnode = CreatNewnode(x);SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}newnode->next = pos;pcur->next = newnode;}
}//指定位置之后插入
void SListPushPosAfter(SListNode* pos, SLTDataType x)
{assert(pos);SListNode* newnode = CreatNewnode(x);SListNode* next = pos->next;pos->next = newnode;newnode->next = next;
}//销毁链表
void SListDestroy(SListNode** pphead)
{SListNode* pcur = *pphead;while (pcur){SListNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

单链表完结撒花！！！