超详细实现单链表的基础增删改查——基于C语言实现

1、链表的概念与分类

1.1 链表的概念

链表是一种在物理结构上不连续、非线性的数据存储结构，但它在逻辑结构上是线性的，这是通过链表中的指针链接次序来实现。

1.2 链表的分类

链表有很多种结构，分别带头和不带头，单向和双向，循环和不循环，以上各种情况组合起来就多达222 = 8种链表结构，分别是：

1. 不带头单向不循环链表
2. 不带头单向循环链表
3. 不带头双向循环链表
4. 不带头双向不循环链表
5. 带头双向循环链表
6. 带头单向循环链表
7. 带头单向不循环链表
8. 带头双向不循环链表

**单向和双向的区别：**单向的链表每个节点只有一个指向下一个节点的指针，而双向链表每个节点有指向下一个节点的指针，也有指向上一个节点的指针。

**带头和不带头的区别：**不带头链表的第一个节点也就是头节点，是第一个存储数据的有效节点，而带头链表的头节点则是不存储数据，也被叫做哨兵位，哨兵位后的第一个节点才开始存储有效数据。

**循环与不循环的区别：**不循环链表的尾节点指向NULL，而循环链表的尾节点指向链表的头节点，构成环。

上面这么多种结构中，我们最常用的是不带头单向不循环链表（简称单链表）和带头双向循环链表。

2、单链表的结构和定义

2.1 单链表的结构

依据前面所提的关于不带头单向不循环链表的结构，我们可以得出，单链表每个节点有两个变量，一个用来存放数据，一个用来指向下一节点，那么我们就可以根据这个结构来定义我们的单链表。

2.2 单链表的定义

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

其中，我们将int重定义为SLTDataType，是为了后续方便我们修改整个链表的数据类型，将struct SListNode重定义为SLTNode，方便我们后面使用。

3、单链表的实现

3.1 创建新节点

因为后续的插入操作都需要创建新节点，为实现代码复用，避免太多重复代码，我们封装一个用于创建新节点的函数。
实现思路：首先创建一个临时的节点并为其开辟空间（提高代码健壮性可以判断是否申请空间成功），然后将传过来的值赋给创建的节点，再将新节点的指针置空，最后返回这个节点。
具体实现代码如下：

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

3.2 头插和尾插的实现

我们给出下面两个函数的声明，分别是实现链表的头插和尾插，注意这里传过去的是二级指针，因为链表头节点本身就是一个一级的结构体指针，我们要修改它的值，就要在这里进行传址操作。

//链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

链表头插的实现思路：首先我们要判断传进来的指针是否为空，可以使用assert断言，如果为空则直接异常中止，如果不为空则创建新节点，并将新节点的指针指向头节点，再将新节点作为新的头节点。
实现代码：

void SListPushFront(SLTNode** pphead, SListDataType x)
{assert(pphead);SLTNode* newNode = SLTBuyNode(x);newNode->next = *pphead;*pphead = newNode;
}

//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);

尾插的实现思路：同样，进来先用断言判断pphead是否为空，然后创建新节点，再判断链表是否为空，如果为空，则将新创建的节点作为头节点，然后返回，如果不为空，则需要遍历当前链表，找到尾节点，将尾节点的next指针指向我们的新节点。
代码实现如下：

//链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空if (*pphead == NULL){*pphead = newnode;return;}//链表不为空，找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;
}

3.3 头删和尾删的实现

函数声明：

//链表的头删
void SLTPopFront(SLTNode** pphead);

头删的实现思路：
头删我们要考虑链表可能存在为空、只有一个节点、有多个节点三种情况，因此我们在用断言判断头节点指针是否为空后要再判断头节点是否为空，再去考虑只有一个节点和多个节点的情况，如果只有一个节点，那么执行完头删后链表为空，我们需要释放头节点的内存，并将头节点置空，然后返回，如果有多个节点，我们则创建一个新的节点，来存放头节点的next指针，也就是第二个节点，再释放头节点的内存（这里就是头删操作），这个时候再将我们创建的新节点赋值给头节点，此时头节点就为原来的第二个节点，完成头删操作。
代码实现如下：

void SLTPopFront(SLTNode** pphead) {assert(pphead);assert(*pphead);//链表只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;}

//链表的尾删
void SLTPopBack(SLTNode** pphead);

尾删的实现思路：
同样，我们还是要考虑链表为空、链表只有一个节点、链表有多个节点的情况，链表为空则无法删，链表只有一个节点那么就和头删一样的处理方式，释放头节点，置空然后返回，如果存在多个节点，我们则需要遍历链表找到为尾节点，不同于头删的是，我们在遍历链表找尾节点的时候，要创建一个临时的变量prev来存放尾节点的前一个节点，然后找到尾节点后释放尾节点，并将prev的next指针置空，再赋值给尾节点，此时就完成了尾删操作。
代码实现如下：

void SLTPopBack(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//链表只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;
}

3.4 链表的查找

函数声明：

//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);

查找的实现思路：这个实现的思路比较简单，首先传进来的pphead不能为空，然后遍历整个链表，用每个节点的data和x进行比较，如果相同则返回当前节点，如果遍历完整个链表找不到和x相同的data，则说明不存在这个节点，那么就返回一个NULL。
代码实现如下：

//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

将SLTNode* 类型作为查找函数的返回类型，可以方便我们后续指定位置进行操作。

3.5 指定位置之前和之后插入数据

函数声明：

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);

指定位置之前插入数据的实现思路：首先我们要考虑传进来的pphead是否为空，删除的节点是否为空，以及链表是否为空的情况，所以一开始要有3次断言，创建一个新节点，然后考虑删除的节点pos正好是头节点的情况，以及pos不是头节点的情况，如果是头节点则直接进行头插操作，不是头节点我们则需要遍历链表找pos节点，这里的循环条件是当前节点prev的下一个节点不为pos，那么循环终止时，当前节点prev就应该是pos的前一个节点，此时我们再让新节点的next指针指向pos，让prev的next指针指向新节点，完成pos前插入数据的操作。
代码实现如下：

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//pos刚好是头节点if (pos == *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头节点的情况SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;
}

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

指定位置之后插入数据的实现思路：
可以看到这个函数的参数只有pos节点和插入数据x，也就是说不需要对整个链表进行操作，具体是如何实现的呢，同样的，我们需要先用断言判断pos节点是否为空，然后创建一个新节点存放插入数据x，我们要在pos节点之后插入数据，这个操作会同时影响到pos和pos的下一个节点，也就是pos->next，我们只需要让新节点的next指针指向pos的下一个节点pos->next,再让pos的next指针指向新节点，即可完成pos后插入数据的操作。
代码实现如下：

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//  pos   newnode   pos->nextnewnode->next = pos->next;pos->next = newnode;
}

3.6 删除指定位置的数据和删除指定位置之后的数据

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);

实现思路：首先我们还是要对pphead、*pphead以及pos进行断言，然后考虑pos节点是否为头节点的情况，如果为头节点，那么我们直接进行头删操作即可，如果不是，我们就要遍历链表，找到pos的前一个节点prev，让prev的next指针指向pos的下一个节点pos->next,再释放pos节点的内存，将pos置空，至此完成删除pos节点操作。
代码实现如下：

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);assert(pos);//pos是头节点if (pos == *pphead){//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);

实现思路：我们要考虑两种情况，pos节点是否为空，以及pos是否为尾节点（如果pos是尾节点就没有删除pos之后节点的说法了），因此我们需要对pos和pos->next进行断言。我们创建一个临时的节点del存放pos的下一个节点，也就是我们要删除的节点，然后让pos的next指针指向del的下一个节点，也就是pos的下下个节点，再释放del，将del置空，这样就完成对pos后的节点删除的操作了。
代码实现：

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;}

3.7 链表的销毁

函数声明：

//销毁链表
void SLTDestroy(SLTNode** pphead);

实现思路：首先还是要对pphead和pphead进行断言，然后就是遍历链表对每个节点依次释放内存，最后要将头节点pphead置空。
代码实现如下：

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

4、单链表与顺序表的区别

单链表和顺序表都是线性表，但顺序表在物理结构上一定连续，因为顺序表的底层结构是数组，数组的存储就是一块连续的空间，而单链表在物理结构上不一定连续，为什么说不一定的，因为每个节点的地址都是随机分配的，无法确定。顺序表相对于单链表而言，它因为底层结构是数组，所以能够做到随机访问，而链表随机访问一个节点都要进行遍历，效率较低，但顺序表插入和删除数据需要对整个数组的元素进行搬移，而链表则只需要修改指针指向，二者各有各的优缺点，这也就给他们带来了不同的应用场景，但你需要频繁访问存储的数据时，可以考虑顺序表作为底层结构，当你需要频繁的删除插入操作时，链表就更加符合你的需求。所以说存在即合理，每个数据结构都有他们的优势和缺陷，没有绝对的谁好谁差的区分。我们要做到的是了解、熟悉每一个数据结构，在未来遇到各种应用场景时，能够根据不同的需求选择最合适的数据结构。

5、结语

这篇文章就讲到这里了，单链表相关功能的测试，大家就自己去尝试一下，如果存在什么错误和纰漏的地方，请及时指出，一定改正，数据结构这部分确实是代码量最多的一部分，不仅要学数据结构，还有各种各样的算法，需要不断地加以练习，后面会开个新专栏用来记录我的刷题，努力学习，共同进步。最后附上完整的代码，希望这篇文章能够给你带来帮助。

6、 完整实现代码

6.1 头文件SList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//链表节点结构typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//打印链表
void SLTPrint(SLTNode* phead);//链表的头插和尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPushBack(SLTNode** pphead, SLTDataType x);//链表的头删和尾删
void SLTPopFront(SLTNode** pphead);
void SLTPopBack(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SLTDestroy(SLTNode** pphead);

6.2 SList.c文件

#include"SList.h"//打印链表
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//创建新节点
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空if (*pphead == NULL){*pphead = newnode;return;}//链表不为空，找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;
}//链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空//链表不为空newnode->next = *pphead;*pphead = newnode;
}//链表的头删和尾删
void SLTPopFront(SLTNode** pphead) {assert(pphead);assert(*pphead);//链表只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;}
void SLTPopBack(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//链表只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;
}//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//pos刚好是头节点if (pos == *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头节点的情况SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;
}//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);assert(pos);//pos是头节点if (pos == *pphead){//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;}//销毁链表
void SLTDestroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}