【数据结构和算法】5.超详解析，带你手撕单向链表（图文解析，附带源码）

���迎来sobercq的博客喔，本期系列为【数据结构和算法】5.超详解析，带你手撕单向链表（图文解析，附带源码），带大家理解单向链表在内存中的分布，以及链表的实现，最后还会有源码分享，感谢观看，支持的可以给个赞哇。

前言

在上一篇我们知道了线性表中顺序表的问题，本期我们将讨论线性表的另一种结构，链表，由于它不要求像顺序表一样开辟连续的物理空间，并且要求逻辑上相邻的元素在物理位置上也顺序存储，也因此链表不需要移动大量的数据，但同时也失去了随机下标访问的优势。

一、链表的概念及结构

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

结构：

对链表中的数据元素来说，除了存储其本身的信息外，还需存储一个指示其后继的信息（地址），这两部分信息组成数据元素的存储映像，称为节点或者结点。它在内存中有两个域，其中存储数据元素本身的信息的域叫做数据域，存储后继位置地址的域称为指针域。指针域中存储的信息就叫做指针或链。n个结点链结成链表，因为链表中的每个结点只包含一个指针域，故又称为线性链表或者单链表。

二、单向链表的结构

定义链表结构，我们使用一个头指针phead指向链表的起始位置，在一个结点中的指针域，也就是next，让其指向下一个结点的起始位置，在单向链表的末端，也就是最后一个结点，让它的next指向NULL，这样一个单向链表的结构定义就完成了。

 链表的结构如下图所示：

typedef int SLNDataType;typedef struct SListNode{SLNDataType val;struct SListNode* next;}SLNode;

单向链表的存取必须从头指针开始进行（头指针指示链表中的第一个结点的存储位置）同时，最后一个结点的指针为“空”（NULL）（因为最后一个数据元素没有直接后继）。

三、单向链表功能实现

(1).单向链表的打印

在打印单向链表，我们通过指针next来找到下一个结点，然后打印这一个结点的值。但是注意一点，我们是不碰原先链表中的next的，所以在寻找链表的时候，需要定义一个指针cur来遍历链表，当cur指向到链表末尾的时候，这时候cur为NULL，也就意味着指针遍历结束。

单向链表逻辑结构上的打印：（逻辑结构和物理结构看第五大点）

//打印单向链表void SLTPrint(SLNode* phead){SLNode* cur = phead;while (cur != NULL){printf("%d ", cur->val);cur = cur->next;}}

(2).单向链表的尾插 

为了插入数据元素x，我们首先要找到单向链表的“尾巴”，其次要开辟一个结点，其数据为x，然后插入单向链表中。并且要修改原先单向链表上一个结点的指针，使其指向新开辟出来的val为x的结点，让val为x的结点的指针next为"空"（NULL），这样就完成了尾插的操作。

找单向链表的尾巴：

我们定义一个tail来存储头部指针phead，接着去遍历单向链表。

找尾中可能出现的问题 

请看下列两个代码，并思考有何区别？

SLNode* tail = phead;//找尾while (tail->next != NULL){tail = tail->next;}

SLNode* tail = phead;//找尾while (tail != NULL){tail = tail->next;}

 在找尾部的时候，我们需要判断的是tail->next后的指针是否为空指针，在第二个代码中，其找尾部的最后结果通常是把NULL赋值给tail，而不是我们想要的把新创建的结点地址给到tail。因此需要提前判断tail的下一个结点是否为空指针。

逻辑结构如下图所示：

创建新的结点 ：

我们用newnode来表示新结点，注意newnode不能在尾插当中直接创建（因为是局部变量的关系，局部变量出了作用域就销毁了），在函数外，我们创建一个新函数，并且通过创建内存空间来创建一个新结点。

//创建一个新结点SLNode* CreateNode(SLNDataType x){SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));if (newNode == NULL){perror("malloc fail");exit(-1);}newNode->val = x;newNode->next = NULL;return newNode;}

 插入结点：

//尾插void SLTPushBack(SLNode* phead, SLNDataType x){//找尾SLNode* tail = phead;while (tail->next != NULL){tail = tail->next;}//创建新结点SLNode* newnode = CreateNode(x);//插入结点tail->next = newnode;}

如果链表开始为空怎么办？

我们需要先判断链表的状态，那么单向链表为空的时候，其实就是phead为空。

//判断链表是否为空if (phead == NULL){phead = newnode;}

最后梳理后，我们在代码中要先创建结点，然后判断链表状态，最后是插入。

//尾插void SLTPushBack(SLNode* phead, SLNDataType x){//创建新结点SLNode* newnode = CreateNode(x);//判断链表是否为空if (phead == NULL){phead = newnode;}else{//找尾SLNode* tail = phead;while (tail->next != NULL){tail = tail->next;}//插入结点tail->next = newnode;}}

尾插测试 

int main(){SLNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);return 0;}

我们在测试的时候发现问题，屏幕居然什么也没打印，回顾后发现，其实也就是当我传plist的时候，本意是想通过phead操作plist，但我们只拷贝了plist而并没有对plist进行操作，所以对原先一级指针phead要进行部分调整（尾插和头插的SLNode* phead就要改成SLNode** pphead）

 改完后的代码如下：

int main(){SLNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);return 0;}//尾插void SLTPushBack(SLNode** pphead, SLNDataType x){//创建新结点SLNode* newnode = CreateNode(x);//判断链表是否为空if (*pphead == NULL){*pphead = newnode;}else{//找尾SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}//插入结点tail->next = newnode;}}//头插void SLTPushFront(SLNode** pphead, SLNDataType x){;}void SLTPushBack(SLNode** pphead, SLNDataType x);//尾插void SLTPushFront(SLNode** pphead, SLNDataType x);//头插

测试效果如下图所示：

至此，尾插的功能就完成了。

(3) .单向链表的头插

为了插入数据元素x，我们首先要创建一个结点，其数据为x，然后将phead指向新结点。并且要修改结点，使其指向原先单向链表的第一个val的结点。这样就完成了头插的操作。

//头插void SLTPushFront(SLNode** pphead, SLNDataType x){SLNode* newnode = CreateNode(x);newnode->next = *pphead;*pphead = newnode;}

 头插测试

int main(){SLNode* plist = NULL;//尾插测试SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//头插测试SLTPushFront(&plist, 5);SLTPushFront(&plist, 6);SLTPushFront(&plist, 7);SLTPushFront(&plist, 8);SLTPrint(plist);return 0;}

可以看到如下结果： 

 

(4).单向链表的尾删

 为在单向链表中删除结点的时候，我们仅仅只需要修改上一个结点的指针域即可，而不需要对数据进行操作。尾删仍然需要找到尾巴，并且要判断链表是否只有一个结点。

 我们要对一个结点和多个结点的情况分类讨论。当我们只有一个结点的时候。在采取同样对多节点的时候会导致prev的指向。在删除的时候，我们还是需要对指针进行检查。

这里就不展开详细讲解了，代码如下所示： 

void SLTPopBack(SLNode** pphead){assert(*pphead);//找尾if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* prev = NULL;SLNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}}

尾删的另外一种写法，我们知道tail用来表示一结点的起始位置，其中的next是下一个结点，而我们在这个前面的代码中，要找到tail的上一个结点，也就是要间隔一个结点判断是否为链表末端所以可以用如下代码：

void SLTPopBack(SLNode** pphead){assert(*pphead);SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}

 结果如下所示：

(5).单向链表的头删

在单向链表中删除结点的时候，从头部开始，我们需要修改下一个结点的指针域，让其赋值给pphead，这样就完成了头删的操作。

plist是我们传入的指针，*pphead是plist的二级指针。

操作过程逻辑结构如下图所示：

对第一个结点free了，然后让*pphead指向下一个结点。 

void SLTPopFront(SLNode** pphead){assert(*pphead);SLNode* tmp = (*pphead)->next;free(*pphead);*pphead = tmp;}

删除测试 

//删除测试void Test2(){SLNode* plist = NULL;//尾部插入四个数据SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//尾删测试SLTPopBack(&plist);SLTPrint(plist);//尾删测试SLTPopBack(&plist);SLTPrint(plist);//头删测试SLTPopFront(&plist);SLTPrint(plist);}

结果如下图所示： 

(6).单向链表的查找 

用cur指针遍历链表，比对每个结点的值，如果值相等，则返回cur，如果cur遍历到NULL，也就是链表末尾，则返回NULL

//链表查找SLNode* SLTFind(SLNode* phead, SLNDataType x){SLNode* cur = phead;while (cur){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;}

 查找测试

//查找测试void Test3(){SLNode* plist = NULL;//尾部插入一个数据SLTPushBack(&plist, 1);if (SLTFind(plist, 3))printf("找到了");elseprintf("找不到");if (SLTFind(plist, 1))printf("找到了");elseprintf("找不到");}

 结果如下图所示：

(7). 在pos位置之前插入一个结点

 对pos的位置进行讨论，我们发现pos位置有三种情况，一中是头结点，一种是中间结点，还有一种是尾结点。

 在插入前需要对指针进行检查，assert也有几种情况

一种是对三个都检查一遍

    assert(pphead);//有必要断言，防止乱传

    assert(*pphead);//可以不断言

    assert(pos);

另外一种是 

    //宽松的条件

    //pos 和 *pphead 要么都是空要么都不是

    assert((!pos && !(*pphead))||(pos && *pphead));

第一种断言主要是针对pos，严格限制pos一定是链表里的一个有效节点 ，第二种就会稍微宽松点。

为pos的位置进行讨论后发现中间结点和尾结点都一样，所以将头结点和后面的两种情况进行探讨。

假设pos指向头结点

针对头结点或者是开始链表为空的情况，发现pos和pphead指向的都是第一个结点，所以条件为二者相等的情况。即pphead == pos 这种情况同样也能解决二者都为空的情况，这样使用头插就能解决

假设pos指向中间结点或者尾结点

 我们需要找到pos的上一个结点（这是单向链表的缺陷）然后让上一个prev结点指向下一个新结点，下一个结点指向pos结点。

//在pos之前插入void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x){//限制pos一定是链表里的一个有效节点assert(pphead);//有必要断言，防止乱传//assert(*pphead);//可以不断言//assert(pos);//宽松的条件//pos 和 *pphead 要么都是空要么都不是assert((!pos && !(*pphead))||(pos && *pphead));//头插if (*pphead == pos)//也能解决两个都为空的情况{SLTPushFront(pphead, x);}else{//找前一个结点位置SLNode* prev = *pphead;SLNode* newnode = CreateNode(x);while (prev->next != pos){prev = prev->next;}//插入prev->next = newnode;newnode->next = pos;}}

插入测试 

//插入测试void Test4(){SLNode* plist = NULL;//第一种情况，plist和pos都为空SLTInsert(&plist,NULL,3);//尾部插入四个数据SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLNode* pos = SLTFind(plist, 4);SLTInsert(&plist, pos, 40);//报错测试//pos = SLTFind(plist, 400);//SLTInsert(&plist, pos, 40);//打印SLTPrint(plist);}

 结果如下图所示

 

 (8).删除pos结点

 删除pos结点还是得分情况，一种是只有一个结点，一种是多个结点，因为当只有一个结点的时候，prev其实会走到空。

//删除pos结点void SLTErase(SLNode** pphead, SLNode* pos){//针对pphead是每个都要检查的assert(pphead);assert(*pphead);assert(pos);//删除pos结点仍然需要找到pos的前一个位置if (*pphead == pos){//头删SLTPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}

(9). 在pos位置后插入

在pos位置后插入删除，修改pos位置的指针即可，跟plist没什么关系，不需要修改plist 

在这里需要先让newnode指向下一个结点，然后再让pos指向新节点。 

//在pos位置后插入void SLTInsertAfter(SLNode* pos, SLNDataType x){assert(pos);SLNode* newnode = CreateNode(x);newnode->next = pos->next;pos->next = newnode;}

(10).在pos位置后删除

删除pos后的位置，用一个游标cur保存一下也可以

 但是这里存在空指针的情况，有可能pos->next为空指针，也有可能pos->next->next为空。所以还是需要对pos->next进行相对应的检查。

//删除在pos位置后void SLTEraseAfter(SLNode* pos){assert(pos);SLNode* cur = pos->next;pos->next = pos->next->next;free(cur);cur = NULL;}

在pos位置后的插入和删除测试 

void Test6(){SLNode* plist = NULL;//尾部插入四个数据SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//在pos后插入SLNode* pos = SLTFind(plist, 2);SLTInsertAfter(pos,5);SLTPrint(plist);//在pos后插入pos = SLTFind(plist, 5);SLTInsertAfter(pos, 6);SLTPrint(plist);//在pos后删除pos = SLTFind(plist, 2);SLTEraseAfter(pos);pos = SLTFind(plist, 3);SLTEraseAfter(pos);//报错测试/*pos = SLTFind(plist, 3);SLTEraseAfter(pos);*/SLTPrint(plist);}

 结果如下图所示：

(11).链表的销毁

 链表的销毁，用游标遍历链表，然后不断释放空间，最后将这个头指针置空。 

那在这里要注意保存地址。 

//销毁void SLTDestroy(SLNode** pphead){assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* tmp = cur->next;free(cur);cur = tmp;}*pphead = NULL;}

 (12).完善代码，进行补全断言的操作

 不详细展开了，把pphead的断言补上，包括一些其他的断言检查补全就好了。

四、物理结构和逻辑结构

在涉及到单向链表的打印的时候，我们看到链表打印的逻辑结构如下图所示：

那什么是逻辑结构？

就是我们把链表画成用箭头相链接的结点的序列，结点之间用箭头表示链域中的指针。

为什么用逻辑结构表示链表？

这是因为我们在使用链表的时候，关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。

那链表的物理结构是什么样子的呢？

链表的物理结构如下图所示：

实际上是每个指针都有一个地址，然后内存空间也有一个结点地址，指针先去找结点地址，通过结点中的指针而找到下一个结点。

五、总结以及单向链表的源码分享

断言：这个值不能为空就断言 

单向链表的优劣性 

优势：

不需要移动大量的数据 

劣势：

失去了随机下标访问的优势。

单向链表的尾插尾删效率不好

单向链表在某些功能上如果要找到上一个结点的画，需要用到另外一个指针，降低效率。

那代码的话仍然是分为三个文件，SList.h，SList.c，test.c

SList.h的代码如下：

#pragma once#include#include#includetypedef int SLNDataType;typedef struct SListNode{SLNDataType val;struct SListNode* next;}SLNode;void SLTPrint(SLNode* phead);void SLTPushBack(SLNode** pphead, SLNDataType x);void SLTPushFront(SLNode** pphead, SLNDataType x);void SLTPopBack(SLNode** pphead);void SLTPopFront(SLNode** pphead);SLNode* SLTFind(SLNode* phead, SLNDataType x);void SLTInsert(SLNode**pphead,SLNode* pos, SLNDataType x);void SLTInsertAfter(SLNode* pos, SLNDataType x);void SLTErase(SLNode** pphead, SLNode* pos);void SLTEraseAfter(SLNode* pos);void SLTDestroy(SLNode** pphead);

 SList.c的代码如下：

#include"SList.h"void SLTPrint(SLNode* phead){SLNode* cur = phead;while (cur != NULL){printf("%d ", cur->val);cur = cur->next;}printf("\n");}SLNode* CreateNode(SLNDataType x){SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));if (newNode == NULL){perror("malloc fail");exit(-1);}newNode->val = x;newNode->next = NULL;return newNode;}void SLTPushBack(SLNode** pphead, SLNDataType x){assert(pphead);SLNode* newnode = CreateNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}void SLTPushFront(SLNode** pphead, SLNDataType x){assert(pphead);SLNode* newnode = CreateNode(x);newnode->next = *pphead;*pphead = newnode;}void SLTPopBack(SLNode** pphead){assert(pphead);assert(*pphead);SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}void SLTPopFront(SLNode** pphead){assert(*pphead);SLNode* tmp = (*pphead)->next;free(*pphead);*pphead = tmp;}SLNode* SLTFind(SLNode* phead, SLNDataType x){SLNode* cur = phead;while (cur){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;}void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x){assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){SLTPushFront(pphead, x);}else{SLNode* prev = *pphead;SLNode* newnode = CreateNode(x);while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}}void SLTErase(SLNode** pphead, SLNode* pos){assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}void SLTInsertAfter(SLNode* pos, SLNDataType x){assert(pos);SLNode* newnode = CreateNode(x);newnode->next = pos->next;pos->next = newnode;}void SLTEraseAfter(SLNode* pos){assert(pos);assert(pos->next);SLNode* cur = pos->next;pos->next = pos->next->next;free(cur);cur = NULL;}void SLTDestroy(SLNode** pphead){assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* tmp = cur->next;free(cur);cur = tmp;}*pphead = NULL;}

test.c的代码如下：

#include"SList.h"//插入测试void Test1(){SLNode* plist = NULL;//尾插测试SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//头插测试SLTPushFront(&plist, 5);SLTPushFront(&plist, 6);SLTPushFront(&plist, 7);SLTPushFront(&plist, 8);//打印SLTPrint(plist);}//删除测试void Test2(){SLNode* plist = NULL;//尾部插入四个数据SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//尾删测试SLTPopBack(&plist);SLTPrint(plist);//尾删测试SLTPopBack(&plist);SLTPrint(plist);//头删测试SLTPopFront(&plist);SLTPrint(plist);}//查找测试void Test3(){SLNode* plist = NULL;//尾部插入一个数据SLTPushBack(&plist, 1);if (SLTFind(plist, 3))printf("找到了");elseprintf("找不到");if (SLTFind(plist, 1))printf("找到了");elseprintf("找不到");}//插入测试void Test4(){SLNode* plist = NULL;//第一种情况，plist和pos都为空SLTInsert(&plist,NULL,3);//尾部插入四个数据SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLNode* pos = SLTFind(plist, 4);SLTInsert(&plist, pos, 40);//报错测试//pos = SLTFind(plist, 400);//SLTInsert(&plist, pos, 40);//打印SLTPrint(plist);}//删除测试void Test5(){SLNode* plist = NULL;//尾部插入四个数据SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLNode* pos = SLTFind(plist, 3);SLTErase(&plist, pos);pos = SLTFind(plist, 1);SLTErase(&plist, pos);pos = SLTFind(plist, 4);SLTErase(&plist, pos);//打印SLTPrint(plist);}void Test6(){SLNode* plist = NULL;//尾部插入四个数据SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//在pos后插入SLNode* pos = SLTFind(plist, 2);SLTInsertAfter(pos,5);SLTPrint(plist);//在pos后插入pos = SLTFind(plist, 5);SLTInsertAfter(pos, 6);SLTPrint(plist);//在pos后删除pos = SLTFind(plist, 2);SLTEraseAfter(pos);pos = SLTFind(plist, 3);SLTEraseAfter(pos);//报错测试/*pos = SLTFind(plist, 3);SLTEraseAfter(pos);*/    //销毁测试SLTDestroy(&plist);SLTPrint(plist);}int main(){//Test1();//Test2();//Test3();//Test4();//Test5();Test6();return 0;}

感谢各位同伴的支持，本期单链表讲解就结束啦，在文章的末尾有源代码分享，有需要的小伙伴可自取哈。

下期预告：【数据结构与算法】第六篇双向链表