【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】

web/2025/9/26 15:18:01/文章来源:href="https://blog.51cto.com/u_17153208/14134124" target="_blank"

hi ！

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_链表

前言：

1、链表的概念和结构

2、单链表（Single List，简写SList）的实现

2.1 定义链表（结点）的结构

2.2 创建一个链表

2.3 打印链表

2.4 尾插

2.5 头插

2.6 尾删

2.7 头删

2.8 查找

2.9 在指定位置之前插入数据

2.10 在指定位置之后插入数据

2.11 删除pos结点

2.12 删除pos之后的结点

2.13 销毁链表

———————————————— 《你的名字》 ————————————————

正文开始——

前言：

前面我们学习了顺序表，实现了对数组内容增删查改等操作，但是顺序表仍然存在一些缺陷。

中间/头部的插入删除，时间复杂度为O(N)；
增容需要申请新空间，拷贝数据，释放旧空间，这是不小的消耗；
增容一般是成2倍的增长，大概率会有一些空间的浪费。

那我们该如何解决上面的问题呢？下面我们来学习一下链表。

1、链表的概念和结构

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

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_开发语言_02

2、单链表（Single List，简写SList）的实现

上面我们了解了链表的概念和结构，链表又分为很多种，今天我们先学习链表之一单链表。

2.1 定义链表（结点）的结构

//定义链表（结点）的结构typedef int SLTDataType;
typedef struct SListNode {SLTDataType data;  struct SListNode* next;
}SLTNode;

2.2 创建一个链表

这里申请空间使用 malloc，在链表里面不存在增容的操作，想插入数据直接申请一个新的结点即可！用 calloc 也可以，calloc会让申请空间的内容初始化为0。

【代码】

test.c

//创建一个链表
void creatSList()
{//链表是由一个一个的结点组成的SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node4->data = 4;//将结点之间连接起来node1->next=node2;node2->next=node3;node3->next=node4;node4->next = NULL;}

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_链表_03

2.3 打印链表

【思路图解】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_开发语言_04

【代码】

//链表的打印void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

2.4 尾插

【思路图解】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_结点_05

【代码】

SList.c

//申请一个新结点
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc file!");exit(1);}node->data = x;node->next = NULL;return node;
}//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//申请一个新结点SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* pcur = *pphead;//找尾结点while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}

test.c

void SListTest01()
{SLTNode* plist = NULL;//plist为指向第一个结点的指针SLTPushBack(&plist,100);SLTPrint(plist);
}int main()
{SListTest01();return 0;
}

【验证】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_开发语言_06

【注意】

在 test.c 里面尾插时传的是&plist ，而不是 plist。我们希望形参的改变影响实参，所以我们取实参的地址。plist 作为参数传的是一个指针变量而不是一个地址，只有 &plist （有&）才算是真正的取地址使得形参的改变影响实参。用二级指针来接收。
找尾结点。循环的条件是 pcur->next，而不是 pcur。因为 pcur->next 为NULL跳出循环时，说明 pcur 为尾结点，当 pcur 为空跳出循环时，说明 pcur 是尾结点的下一个节点，而不是尾结点。
pphead==&plist；*pphead==plist（指向第一个结点的指针）。
assert (pphead)；传过来的地址不能为空。

【细细品味】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_开发语言_07

后知后觉，还是那个问题，为什么要传二级指针呢？
plist里面保存的地址，所以我们需要传这个指针的地址，才用二级指针的；比如单链表的头插，就是会改变头结点指针的指向，所以需要二级指针；而双向链表，是带头的，有哨兵位，无论怎么插入和删除，都是不会改变哨兵位结点指针的指向的，所以就没有必要传递二级指针，改变其内部的prev和next，这是可以通过改变指针来找到并改变的，并没有改变哨兵位结点指针的本身。
用二级指针，是因为我们链表插入的时候，一般是把头结点的指针传进去，而尾插，非第一次插入，是不影响头结点的指向的；但是头插，每一次都是改变头结点指针的指向，所以二级指针是为了更改实参头结点指针的值。
（当时不理解，后来再思考就慢慢理解了，当时很困难没关系，但是一定要撑到最后，知识真是常回看常新）

2.5 头插

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_结点_08

【代码】

SList.c

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//申请一个新结点SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

test.c

void SListTest01()
{//验证尾插SLTNode* plist = NULL;SLTPushBack(&plist,1);SLTPushBack(&plist,2);SLTPushBack(&plist,3);SLTPushBack(&plist,4);SLTPushBack(&plist,100);SLTPrint(plist);//验证头插SLTPushFront(&plist, 200);SLTPrint(plist);
}int main()
{SListTest01();return 0;
}

【验证】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_结点_09

2.6 尾删

各结点的地址应为0x0012FF...，在此纠正下面的错误。谅解哈~~~

【思路图解】

当链表内不止一个结点时

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_链表_10

当链表内只有一个结点时

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_结点_11

【代码】

SList.c

//尾删
void SLTPopBack(SLTNode** pphead)
{//链表为空，不可删除assert(pphead && *pphead);//处理只有一个结点的情况，要删除的就是头结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找 ptail 和 prevSLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}

test.c

void SListTest01()
{SLTNode* plist = NULL;SLTPushBack(&plist,1);SLTPushBack(&plist,2);SLTPushBack(&plist,3);SLTPushBack(&plist,4);SLTPushBack(&plist,100);SLTPrint(plist);/*SLTPushFront(&plist, 200);SLTPrint(plist);*/SLTPopBack(&plist);SLTPrint(plist);
}int main()
{/*createSList();*/SListTest01();return 0;
}

【验证】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_头结点_12

2.7 头删

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_结点_13

【代码】

SList.c

//头删
void SLTPopFront(SLTNode** pphead)
{//链表不为空assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

test.c

void SListTest01()
{SLTNode* plist = NULL;SLTPushBack(&plist,1);SLTPushBack(&plist,2);SLTPushBack(&plist,3);SLTPushBack(&plist,4);SLTPushBack(&plist,100);SLTPrint(plist);/*SLTPushFront(&plist, 200);SLTPrint(plist);*//*SLTPopBack(&plist);*//*SLTPrint(plist);*/SLTPopFront(&plist);SLTPrint(plist);}int main()
{/*createSList();*/SListTest01();return 0;
}

【验证】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_链表_14

2.8 查找

各结点的地址应为0x0012FF...，在此纠正下面的错误。

思路简单，直接上代码：

SList.c

//查找
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

【注意】SLTNode* pcur = phead，重新定义一个指针变量 pcur 指向第一个结点，让 pcur 来遍历链表，防止头结点丢失。

test.c

void SListTest01()
{SLTNode* plist = NULL;SLTPushBack(&plist,1);SLTPushBack(&plist,2);SLTPushBack(&plist,3);SLTPushBack(&plist,4);SLTPushBack(&plist,100);SLTPrint(plist);/*SLTPushFront(&plist, 200);SLTPrint(plist);*//*SLTPopBack(&plist);*//*SLTPrint(plist);*/SLTPopFront(&plist);SLTPrint(plist);SLTNode* find = SLTFind(plist, 2);if (find == NULL){printf("没找到\n");}else{printf("找到了\n");}
}

【验证】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_结点_15

2.9 在指定位置之前插入数据

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_头结点_16

【代码】

SList.c

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);if (pos == *pphead){SLTPushFront(pphead, x);}else{//申请一个新的结点SLTNode* newnode = SLTBuyNode(x);//找pos的前一个结点prevSLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}

test.c

void SListTest01()
{SLTNode* plist = NULL;SLTPushBack(&plist,1);SLTPushBack(&plist,2);SLTPushBack(&plist,3);SLTPushBack(&plist,4);SLTPrint(plist);/*SLTPushFront(&plist, 200);SLTPrint(plist);*//*SLTPopBack(&plist);*//*SLTPrint(plist);*///SLTPopFront(&plist);//SLTPrint(plist);//SLTNode* find = SLTFind(plist, 2);/*///*if (find == NULL){printf("没找到\n");}else{printf("找到了\n");//}*/SLTNode* find = SLTFind(plist, 2);SLTInsert(&plist, find, 100);SLTPrint(plist);}

【验证】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_头结点_17

2.10 在指定位置之后插入数据

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_开发语言_18

【代码】

SList.c

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

test.c

void SListTest01()
{SLTNode* plist = NULL;SLTPushBack(&plist,1);SLTPushBack(&plist,2);SLTPushBack(&plist,3);SLTPushBack(&plist,4);SLTPrint(plist);/*SLTPushFront(&plist, 200);SLTPrint(plist);*//*SLTPopBack(&plist);*//*SLTPrint(plist);*///SLTPopFront(&plist);//SLTPrint(plist);//SLTNode* find = SLTFind(plist, 2);/*///*if (find == NULL){printf("没找到\n");}else{printf("找到了\n");//}*//*SLTNode* find = SLTFind(plist, 2);SLTInsert(&plist, find, 100);SLTPrint(plist);*/SLTNode* find = SLTFind(plist, 2);SLTInsertAfter(find, 100);SLTPrint(plist); }

【验证】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_数据结构_19

2.11 删除pos结点

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_结点_20

【代码】

SList.c

//删除pos结点
void SLTErase(SLTNode** pphead,SLTNode* pos)
{assert(pphead && *pphead);//这里对pos进行限制，链表中必须有pos这个结点，在查找中若没有pos结点则返回NULLassert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{//找到prev：pos的前结点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

test.c

void SListTest01()
{SLTNode* plist = NULL;SLTPushBack(&plist,1);SLTPushBack(&plist,2);SLTPushBack(&plist,3);SLTPushBack(&plist,4);SLTPrint(plist);/*SLTPushFront(&plist, 200);SLTPrint(plist);*//*SLTPopBack(&plist);*//*SLTPrint(plist);*///SLTPopFront(&plist);//SLTPrint(plist);//SLTNode* find = SLTFind(plist, 2);/*///*if (find == NULL){printf("没找到\n");}else{printf("找到了\n");//}*//*SLTNode* find = SLTFind(plist, 2);SLTInsert(&plist, find, 100);SLTPrint(plist);*//*SLTNode* find = SLTFind(plist, 2);SLTInsertAfter(find, 100);SLTPrint(plist); */SLTNode* find = SLTFind(plist, 2);SLTErase(&plist, find);//这里的find由pos接收，SLTFind若没找到存储2这个结点则返回NULLSLTPrint(plist); }

【验证】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_数据结构_21

2.12 删除pos之后的结点

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_头结点_22

【代码】

SList.c

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

test.c

void SListTest01()
{SLTNode* plist = NULL;SLTPushBack(&plist,1);SLTPushBack(&plist,2);SLTPushBack(&plist,3);SLTPushBack(&plist,4);SLTPrint(plist);/*SLTPushFront(&plist, 200);SLTPrint(plist);*//*SLTPopBack(&plist);*//*SLTPrint(plist);*///SLTPopFront(&plist);//SLTPrint(plist);//SLTNode* find = SLTFind(plist, 2);/*///*if (find == NULL){printf("没找到\n");}else{printf("找到了\n");//}*//*SLTNode* find = SLTFind(plist, 2);SLTInsert(&plist, find, 100);SLTPrint(plist);*//*SLTNode* find = SLTFind(plist, 2);SLTInsertAfter(find, 100);SLTPrint(plist); *///SLTNode* find = SLTFind(plist, 2);//SLTErase(&plist, find);//SLTPrint(plist); SLTNode* find = SLTFind(plist, 2);SLTEraseAfter(find);SLTPrint(plist); }

【验证】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_链表_23

2.13 销毁链表

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_头结点_24

【代码】

SList.c

//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}//*pphead=plist，链表为空，也要把*pphead置为空*pphead = NULL;
}

【验证】

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_开发语言_25

今天单链表的深度学习就结束啦，拜拜~~~

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_头结点_26

完——

———————————————— 《你的名字》 ————————————————

重要的人，不能忘记的人，不想忘记的人，你，是谁？

不管在哪里，不管过多久，不管是要跨过高山，还是跨过湖海，我一定会去见你一面。

スパークル_RADWIMPS_高音质在线试听_スパークル歌词|歌曲下载_酷狗音乐酷狗音乐为您提供由RADWIMPS演唱的高清音质无损スパークルmp3在线听,听スパークル,只来酷狗音乐!https://t4.kugou.com/song.html?id=avhoFadCPV2https://t4.kugou.com/song.html?id=avhoFadCPV2https://t4.kugou.com/song.html?id=avhoFadCPV2

【数据结构初阶(第四节)】一篇文章带你超深度理解【单链表】_开发语言_27