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

 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  销毁链表

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

正文开始——

前言：

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

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

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

1、链表的概念和结构

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

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;}

2.3  打印链表

【思路图解】

【代码】 

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

2.4  尾插

【思路图解】

【代码】 

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;
}

【验证】 

【注意】

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

2.5  头插

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

【思路图解】

【代码】

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;
}

【验证】

2.6  尾删

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

【思路图解】

当链表内不止一个结点时

当链表内只有一个结点时 

【代码】

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;
}

【验证】

2.7  头删

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

【思路图解】

【代码】

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;
}

【验证】

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");}
}

【验证】

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

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

【思路图解】

【代码】

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);}

【验证】

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

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

【思路图解】

【代码】

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); }

【验证】

2.11  删除pos结点

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

【思路图解】

【代码】

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); }

【验证】

2.12  删除pos之后的结点

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

【思路图解】

【代码】

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); }

【验证】

2.13  销毁链表

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

【思路图解】

【代码】

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;
}

【验证】

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

完——

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

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

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

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

至此结束——

再见——

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/382769.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

PT2262-IR

PT2262-IR

PT2262是一款很古老的编码芯片，其兼容型号有：SC2262，AD2262，SC2260(需改变匹配电阻)等。 依据其datasheet，PT2262射频模式工作原理: CODE BITS A Code Bit is the basic component of the encoded waveform, and ca…
阅读更多...
Docker核心技术：Docker原理之Cgroups

Docker核心技术：Docker原理之Cgroups

云原生学习路线导航页（持续更新中） 本文是 Docker核心技术 系列文章：Docker原理之Cgroups，其他文章快捷链接如下： 应用架构演进容器技术要解决哪些问题Docker的基本使用Docker是如何实现的 Docker核心技术：…
阅读更多...
Maven学习——Maven的下载、安装与配置（详细攻略！）

Maven学习——Maven的下载、安装与配置（详细攻略！）

目录 前言 1.下载与安装 2.配置Maven的环境变量 3.配置Maven的本地仓库 4. 配置Maven的镜像远程仓库 前言 我在之前写了一篇博客，是介绍Maven的基本概念和下载安装，但是由于篇幅过长，Maven的下载与安装写的并不详细🐶&#x…
阅读更多...
Windows系统设置暂停更新，暂停时间可达3000天，“永久”暂停更新，亲测有效

Windows系统设置暂停更新，暂停时间可达3000天，“永久”暂停更新，亲测有效

好多小伙伴被Windows系统的更新搞得很烦，经常在使用中自己下载更新包，占用网路资源，过段时间就要更新，特别讨厌 今天教你一招，可以暂停更新长达3000天，亲测有效 1、打开系统CMD命令执行窗口，输…
阅读更多...
Ideal窗口中左右侧栏消失了

Ideal窗口中左右侧栏消失了

不知道大家在工作过程中有没有遇到过此类问题，不论是Maven项目还是Gradle项目，突然发现Ideal窗口右侧图标丢失了，同事今天突然说大象图标不见了，不知道怎样刷新gradle。 不要慌张，下面提供一些解决思路： 1…
阅读更多...
超声波俱乐部：AI应用大爆发前夜，场景、闭环与LLM进化

超声波俱乐部：AI应用大爆发前夜，场景、闭环与LLM进化

7月13日，第十九期超声波俱乐部内部分享会在北京望京举行，本期的主题是：AI应用大爆发前夜，场景、闭环与LLM进化。 到场的嘉宾有：超声波创始人杨子超，超声波联合创始人、和牛商业创始人刘思雨，豆…
阅读更多...
硅纪元视角 | 语音克隆突破：微软VALL-E 2，Deepfake新纪元！

硅纪元视角 | 语音克隆突破：微软VALL-E 2，Deepfake新纪元！

在数字化浪潮的推动下，人工智能（AI）正成为塑造未来的关键力量。硅纪元视角栏目紧跟AI科技的最新发展，捕捉行业动态；提供深入的新闻解读，助您洞悉技术背后的逻辑；汇聚行业专家的见解，…
阅读更多...
IP协议和路由转发

IP协议和路由转发

文章目录 IP协议IP报头网段划分特殊的IP私有IP和公有IP IP分片 路由 IP协议 IP协议提供了一种能力，将数据报从A主机送到B主机，TCP可以保证可靠性，所以TCP/IP协议可以将数据可靠的从A主机送到B主机。 IP报头 4位版本号(version): 指定IP协议…
阅读更多...
Java 面试 | Redis

Java 面试 | Redis

目录 1. 在项目中缓存是如何使用的？2. 为啥在项目中要用缓存？3. 缓存如果使用不当会造成什么后果？4. redis 和 memcached 有什么区别？5. redis 的线程模型是什么？6. 为什么单线程的 redis 比多线程的 memcached 效率要…
阅读更多...
android13禁用某个usb设备

android13禁用某个usb设备

总纲 android13 rom 开发总纲说明 目录 1.前言 2.触摸设备查看 3.功能修改 3.1 禁用usb触摸 3.2 禁用usb键盘 3.3 禁用usb遥感 4.查看生效与否 5.彩蛋 1.前言 用户想要禁止使用某些usb设备，需要系统不能使用相关的usb设备，例如usb触摸屏，usb键盘，usb遥感等等usb…
阅读更多...
Unity：PC包直接查看Log日志

Unity：PC包直接查看Log日志

PC端会输出Log日志，位置在： C:\Users\用户名\AppData\LocalLow\公司名\项目名 在这里可以找到类似的文件： 打开便可以看到打印。
阅读更多...
C++ 设计模式（五）——状态模式

C++ 设计模式（五）——状态模式

状态模式 序言理解源码 序言 设计模式只是一个抽象的设计模式方法，并不是一个固定使用的搭配，就算是普通switch语句，Map，乃至状态机都是状态模式的其中一种实现方法 状态模式看起来好像和策略模式差不多，主要是其的侧…
阅读更多...
10道JVM经典面试题

10道JVM经典面试题

1、 JVM中，new出来的对象是在哪个区？ 2、 说说类加载有哪些步骤？ 3、 JMM是什么？ 4、 说说JVM内存结构？ 5、 MinorGC和FullGC有什么区别？ 6、 什么是STW? 7、 什么情况下会发生堆/栈溢出&#xff1f…
阅读更多...
来参与“向日葵杯”全国教育仿真技术大赛~

来参与“向日葵杯”全国教育仿真技术大赛~

可点击进行了解：“向日葵杯”全国教育仿真技术大赛 (sunmooc.cn) 本次大赛共分为四个赛道：自主命题赛道、教育知识图谱设计赛道、FPGA硬件扑克牌对抗赛道、EasyAR元宇宙空间设计赛道。 参赛对象 ： 具有正式学籍的在校研究生，本科…
阅读更多...
面试场景题系列--（1）如果系统的 QPS 突然提升 10 倍该怎么设计？--xunznux

面试场景题系列--（1）如果系统的 QPS 突然提升 10 倍该怎么设计？--xunznux

1. 如果系统的 QPS 突然提升 10 倍该怎么设计？ 1.1 硬件的扩展微服务的拆分 如果所有的业务包括交易系统、会员信息、库存、商品等等都夹杂在一起，当流量一旦起来之后，单体架构的问题就暴露出来了，机器挂了所有的业务就全部无法…
阅读更多...
【Mysql】Docker下Mysql8数据备份与恢复

【Mysql】Docker下Mysql8数据备份与恢复

[TOC] 【Mysql】Docker下Mysql8数据备份与恢复 1 创建Mysql容器 格式 docker run -d --name容器名称 -p 宿主端口号:3306 -e MYSQL_ROOT_PASSWORDmysql密码 -e MYSQL_PASSWORDmysql密码 -e TZAsia/Shanghai -v 宿主目录-数据:/var/lib/mysql -v 宿主目录-备份数据:/back…
阅读更多...
信息收集Part3-资产监控

信息收集Part3-资产监控

Github监控 便于收集整理最新exp或poc 便于发现相关测试目标的资产 各种子域名查询 DNS,备案，证书 全球节点请求cdn 枚举爆破或解析子域名对应 便于发现管理员相关的注册信息 通过Server酱接口接收漏洞信息 https://sct.ftqq.com/ https://github.com/easych…
阅读更多...
国内品牌推广全攻略：策略用对，成功翻倍！

国内品牌推广全攻略：策略用对，成功翻倍！

在国内，推广品牌的常用策略多种多样，这些策略旨在提高品牌的知名度、美誉度和市场份额。 以下是一些常用的推广品牌策略： 码字不易，如果回答对您有所帮助，请不吝给一个三连哦！ 1. 社交媒体营销 策略说明…
阅读更多...
计算机网络基础：3.DNS服务器、域名分类

计算机网络基础：3.DNS服务器、域名分类

一、DNS服务器 DNS服务器在网络中的作用类似于餐厅中的“顾客座位对照表”，它帮助前台（路由器）将顾客（用户）的请求转发到正确的餐桌（目标设备）。 (1)概念与原理 DNS的基本概念 DNS&…
阅读更多...
攻防世界 re新手模式

攻防世界 re新手模式

Reversing-x64Elf-100 64位ida打开 看if语句，根据i的不同，选择不同的数组，后面的2*i/3选择数组中的某一个元素，我们输入的是a1 直接逆向得到就行 二维字符数组写法：前一个是代表有几个字符串，后一个是每…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023