当前位置：首页 > news >正文

数据结构--图解单链表

news 来源：原创 2024/5/10 4:18:14

学习链表最重要的就是会画图，尤其是要理解链表的逻辑结构和物理结构，理解链表的底层原理才能使用的如鱼得水。希望这篇文章可以帮助各位，记得关注收藏哦；若发现问题希望私信博主，十分感谢。

当然学习链表是需要大家对指针和结构体能够较为熟练的使用，尤其是指针，需要能够理解一级指针和二级指针，所以如果大家对指针不够熟练的话，可以去看一下博主的文章。

链表的概念及结构

概念：链表是一种 物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表

中的 指针链接 次序实现的。

链表的图形化解释

单链表的物理结构

从物理结构中我们可以看出，头节点plist存储的是下一个节点的地址，而下一个节点也通过一种结构去存储了它下一个节点的地址，以此类推，虽然在物理存储结构上是非连续，非顺序的存储方式，但是可以通过其存储的地址精准找到一下个节点，从而得到了整个链表。

从物理结构中可以看出，链表分为两个部分

单链表的逻辑结构

我们可以说链表在逻辑结构上是连续的，但是在现实的物理结构中，是没有箭头这种链接形式，箭头在逻辑结构中主要是为了理解更加方便，从逻辑结构上可以更加清晰的发现，链表之间的链接是通过上一个节点存储的地址去找到下一个节点。

单链表的初始化

从物理结构中可以发现，单链表需要使用到两种数据，一个是Data，类型是根据自己要存储的类型随时改变的，例如int或者float等等。还有一个就是指针类型的数据，用来存储下一个节点位置。

标准的初始化

typedef int SLTDateType;
typedef struct SLTNode
{SLTDateType data;struct SLTNode* next;
}SLTNode;

在之前的文章中，我们也经常使用 typedef 去重命名数据类型，这样做的好处就是，当类型发生改变的时候，我们可以直接在头文件中改变一个 int 就行，否则你就要在所有文件中找到 int 去挨个改变了。
struct SLTNode* next 很多同学非常疑惑，为什么这个指针的类型是结构体类型，这就考验到同学们对于指针类型的理解，其实指针类型的确定是与它指向的类型保持一致，我们是使用结构体创建的链表，那么指针指向的下一个节点也必然是一个结构体。

初始化的经典错误

很多同学在初始化的时候经常会写成这样

typedef int SLTDateType;
typedef struct SLTNode
{SLTDateType data;SLTNode* next;
}SLTNode;

他的想法就是，我已经将结构体命名为SLTNode了，那么就可以使用SLTNode进行命名了，但是问题在于程序是自上而下运行的，先运行结构体，在运行重命名，所以这样写出来之后，结构体内部不会识别出SLTNode这是个结构体。

接口实现

在学会使用链表之前最重要的是要先学会链表的各种接口是如何实现的，比如头插头删，尾插尾删等等，虽然之后大家都是直接调用接口，但是只有先理解基本的实现原理，才会明白哪种接口效率高，什么场景下适合用哪种接口。

创建新节点

因为之后进行尾插头插或者某一个位置插入的程序中，总要创建新的节点，所以我们可以先写一个创建节点的函数，之后直接使用。

SLTNode* BuyListNode(SLTDateType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("fail in malloc");return;}newnode->data = x;newnode->next = NULL;return newnode;
}

创建过程比较简单，就不多赘述了，如果还是对malloc有问题的同学，请看一下这篇文章可参考动态内存管理https://blog.csdn.net/Senyu_nuanshu/article/details/131934727

打印链表

提前写出链表的打印，接口写完之后马上使用打印去判断一下接口是否写错了

void PrintSLT(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL");printf("\n");
}

这里有一个点需要注意，就是尽量不要直接使用头节点，而是创建一个变量保存头节点的地址，使用这个变量实现代码，因为接口有很多种，不可能每次都使用一种，基本都是各种接口的混合使用，当头节点的地址被改变了就会影响下一个接口的使用了

cur = cur->next；会在尾插详细解释

单链表尾插

尾插的逻辑结构

//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* cur = *pphead;while (cur->next){cur = cur->next;}cur->next = newnode;}
}

断言（assret）的意义：接下来看到的接口实现当中，基本上都可以看到断言的存在，那么它存在的意义是什么呢，其实就是一种自我警告，判断一下断言里面的内容是不是空指针，当然，断言不止可以判断指针，别的也可以，详细各位可以去网上搜索一下。在这个断言里面，我们判断的是二级指针pphead是否为空，那么pphead是代表什么的呢？我们知道，一级指针可以代表一个变量或者一个函数的地址，那么二级指针其实就是代表了一级指针的地址，既然有了一级指针为什么呢还要使用二级指针呢？因为接口的本质就是函数之间的调用，而函数的参数又分为形参和实参，如果你使用一级指针传参，又使用一级指针接收，那么接收的一级指针其实是形参，形参的改变不影响实参，而我们插入删除的时候改变的是什么，是一级指针，那你函数内部的改变不影响函数外部，岂不是无用功了。所以我们就需要使用二级指针接收一级指针的传参，让二级指针去改变一级指针，因为二级指针就是一级指针的地址，当我们运行二级指针的时候，他就会自动找到一级指针所在的位置，去改变一级指针了。
cur->next是什么意思：结构体里面有两个变量，next就是其中一个，表示下一个节点的地址，我们让cur = cur->next；其实就是将指针的位置换到了下一个节点中了。
那这段代码的整体逻辑是什么呢：首先第一步就是断言，要判断一下二级指针是不是空指针，因为它存储的是一级指针的地址，它要是空指针，说明开始就是错误的，没存储上，那接下来的所有都无法运行；然后我们要判断一下这个链表是不是空链表，各位要想明白，空链表是可以插入的，如果是空链表，其实尾插就变成头插了，尾插正常逻辑应该是先找到链表的最后一个节点，如何找呢，链表的最后一个节点的特征就是它的next是NULL，如果是空链表，压根就没有next，那按照正常逻辑肯定找不到，所以要先排除这个情况；接下来就是找尾了，同样道理，不要轻易动用头节点，找到尾之后将尾节点next变成newnode的地址。

单链表尾插的经典错误

//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* cur = *pphead;while (cur){cur = cur->next;}cur= newnode;}
}

想要了解这个经典的错误，就要理解单链表的物理结构

尾插的物理结构

首先内存中链表的物理结构是没有箭头的，正常是下面的样子

当上面的代码刚开始运行的时候，在物理结构上是下面的样子；cur存储了头节点的地址，接下来的 cur=cur->next 使得cur不断更新，存储的一直都是下一个节点的地址。

当不断更新之后，当cur的最终结果NULL的时候，跳出循环；此时cur存储的是4这个节点的next

运行cur = newnode；那么就变成下面的情况

从这图中我们可以看出来，cur是逻辑结构里面的连接线吗，其实不是对吧，他就是一个临时变量来存储地址的， cur = newnode；cur确实存储了newnode的地址，但是cur是临时变量，除了函数就被销毁了，4这个节点就很尴尬啊，4想着我把我的地址给你了啊，你怎么还拿着newnode的地址跑了呢。其实尾插的本质是什么，就是将原尾节点中要存储新的尾节点的地址。那么cur的作用应该是什么，通俗一点就是更新链表的作用，4的地址给了cur，cur也判断出这是个尾节点了，那么就应该将4的next变成newnode的地址，就是cur->next = newnode；同时还有一处错误，就是判断条件啊，我们要判断到4这个节点就应该出来了，要是用cur去作为判断条件，最终cur就变成4的next了，它应该是一个桥梁作用，指引着4去找到newnode，不是自己变成newnode。

单链表头插

从图中其实可以看出，头插其实很简单，就是把节点之间的关系换一下

//单链表头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);newnode->next = *pphead;*pphead = newnode;
}

单链表尾删

链表的空间是使用malloc函数开辟出来的，所以在删除的时候就要多考虑一些，而且链表里面都是指针，一旦没有将删除的指针置空，就会导致野指针的出现。

//单链表尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);//链表中只有一个元素的情况if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//链表中的元素大于1个的时候else{SLTNode* cur = *pphead;while (cur->next->next){cur = cur->next;}free(cur->next);cur->next = NULL;}
}

从代码中我们可以看出来，我们要考虑一种特殊情况，就是链表中只有一个元素，因为删完这个元素之后，就剩下头节点了，这个时候头节点如果不置空，就是导致其变成野指针。
如果是大于一个元素，那么尾删还是要先找到尾巴，然后在删除，使用free将空间还给操作系统，最重要的是将其置空。
断言：尾删为什么要断言*pphead，因为单链表为空的时候是不能删除的，啥都没有删除什么，所以断言的用法要灵活，不要找规律，而是要理解。

单链表头删

//单链表头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* prev = *pphead;*pphead = (*pphead)->next;free(prev);prev = NULL;
}

单链表节点查找

//单链表结点查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

指针问题：不是所有的接口实现都需要用到二级指针，只有要修改链表的时候才需要用到，像查找使用一级指针就足够了

单链表结点插入(在pos之前插入)

首先解释一下pos是什么，pos就是单链表节点查找的时候返回的节点位置。

从图中可以发现，从pos之前插入是比较麻烦的，因为你要找到pos的位置，但是你插入的时候还需要pos之前的节点位置才能正常插入，所以这个时候就非常考验大家对链表的理解。
当然还要分成两种情况去考虑，如果pos就是第一个节点，那就变成头插了

//单链表结点插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pphead);assert(pos);SLTNode* newnode = BuyListNode(x);//头插if (*pphead == pos){newnode->next = pos;*pphead = newnode;}//非头插else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}}

空链表可以插入，但是要确保pos的位置是存在链表当中的，其实就是pos不能为NULL，因为我们是使用自己写的查找程序去寻找，当找不到的时候就会返回NULL；

单链表结点插入(在pos之后插入)

void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pos);assert(pphead);SLTNode* newnode = BuyListNode(x);newnode->next = pos->next;pos->next = newnode;
}

最后赋值的顺序千万不能写错，因为要是先写pos->next = newnode;就会将pos->next节点改变了，那再写newnode->next = pos->next，newnode->next其实就变成newnode自己了。

单链表结点删除(删除pos位置的结点)

头节点就是pos
头节点不是pos

头节点如果是pos，那其实就是头删了，但是如果头节点不是pos，就要注意一个问题，就是删除之后，pos前面的节点与后面的节点之间的链接问题。

删除pos

从图中就可以非常清晰的看出如何在删除之后处理节点，其实就是要找到pos的前一个节点，找到它就可以找到后面的节点了

//单链表结点删除(删除pos位置的结点)
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){free(*pphead);*pphead = NULL;}else{SLTNode* plist = *pphead;while (plist->next != pos){plist = plist->next;assert(plist->next);}plist->next = plist->next->next;free(pos);}
}

销毁单链表

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

销毁链表，不能直接free(phead)，因为链表在物理结构上是不连续存储的，销毁链表必须要一个结点一个结点去销毁！！！！最后不要忘记把phead置为NULL。

总代码

头文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SLTNode
{SLTDateType data;struct SLTNode* next;
}SLTNode;
//创建一个结点
SLTNode* BuyListNode(SLTDateType x);
//销毁单链表
void SLTDestory(SLTNode** pphead);
//单链表头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);
//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
//单链表头删
void SLTPopFront(SLTNode** pphead);
//单链表尾删
void SLTPopBack(SLTNode** pphead);
//单链表结点查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x);
//单链表结点删除(删除pos位置的结点)
void SLTErase(SLTNode** pphead, SLTNode* pos);
//单链表结点插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 单链表结点插入(在pos之后插入)
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//打印单链表
void PrintSLT(SLTNode* phead);

节点代码

#define _CRT_SECURE_NO_WARNINGS 1
#include"SL-list.h"void PrintSLT(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL");printf("\n");
}//创建一个结点
SLTNode* BuyListNode(SLTDateType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("fail in malloc");return;}newnode->data = x;newnode->next = NULL;return newnode;
}//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* cur = *pphead;while (cur->next){cur = cur->next;}cur->next = newnode;}
}//单链表头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);SLTNode* cur = *pphead;newnode->next = cur->next;cur = newnode;
}
//单链表头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* prev = *pphead;*pphead = (*pphead)->next;free(prev);prev = NULL;
}
//单链表尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);//链表中只有一个元素的情况if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//链表中的元素大于1个的时候else{SLTNode* cur = *pphead;while (cur->next->next){cur = cur->next;}free(cur->next);cur->next = NULL;}
}//单链表结点查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//单链表结点插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pphead);assert(pos);SLTNode* newnode = BuyListNode(x);//头插if (*pphead == pos){newnode->next = pos;*pphead = newnode;}//非头插else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;assert(prev->next);}newnode->next = pos;prev->next = newnode;}}//单链表结点删除(删除pos位置的结点)
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){free(*pphead);*pphead = NULL;}else{SLTNode* plist = *pphead;while (plist->next != pos){plist = plist->next;assert(plist->next);}plist->next = plist->next->next;free(pos);}
}// 单链表结点插入(在pos之后插入)
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pos);assert(pphead);SLTNode* newnode = BuyListNode(x);newnode->next = pos->next;pos->next = newnode;
}//销毁单链表
void SLTDestory(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

测试程序

#define _CRT_SECURE_NO_WARNINGS 1
#include"SL-list.h"void test1()
{SLTNode* SLT = NULL;SLTPushBack(&SLT, 1);SLTPushBack(&SLT, 2);SLTPushBack(&SLT, 3);SLTPushBack(&SLT, 7);SLTPushBack(&SLT, 8);SLTPushBack(&SLT, 9);SLTPushBack(&SLT, 4);SLTPushFront(&SLT, 1);SLTPopBack(&SLT);SLTPopFront(&SLT);SLTNode* ret = SLTNodeFind(SLT, 3);SLTInsert(&SLT, ret, 20);SLTErase(&SLT, ret);PrintSLT(SLT);SLTNode* PHEAD = SLTNodeFind(SLT, 2);printf("%p ", PHEAD);}
int main()
{test1();return 0;
}