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

单链表讲解

一.链表的概念以及结构

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

链表的结构与火车是类似的,一节一节的,数据就像乘客一样在车厢中一样。

与顺序表不同的是,链表里的每节"车厢"都是独立申请的空间,我们将这样的空间称为节点或者结点

 既然链表是一节一节的结点构成的,那么这样的结点是怎么连接的呢?

链表中的节点一般是通过结构体来实现的,结构体中的存储着数据和下一个节点的地址,这样我们就可以访问下一个节点中的数据了。

节点:

typedef struct SListNode
{SLTDataType val;struct SListNode* next;
}SLTNode;

为了使用方便我们可以对其重命名。

二.单链表的实现

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data; //节点数据struct SListNode* next; //指针保存下⼀个节点的地址
}SLTNode;
void SLTPrint(SLTNode* phead);
//头部插⼊删除/尾部插⼊删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, 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 SListDesTroy(SLTNode** pphead);

首先我们来思考如何打印数据呢?

void SLTPrint(SLTNode* phead);

这个参数是指向第一个头节点的指针,为什么要使用指针呢?

通过指针我们可以访问这个结构体中的元素,如果我们不使用指针,形参是实参的一份临时拷贝,如果数据过大,这样会很浪费空间(我们这里存储的数据是整形,为了泛用性,我们还是要使用一级指针),直接使用会降低程序性能。

phead->data就可以访问到数据了,那么下一个节点的数据呢?

这时候就会用到我们在结构体中存储的指针了,这个指针指向下一个结构体,所以再通过下一个结构体我们就可以访问下一个结构体的数据,同理,下下个结构体的指针同理。

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

通常习惯上,我们是不会改变直接传过来的参数的,所以我们要使用的话,就再使用一个变量来进行接收。

这里pcur不为NULL时,代表我们的指针并没有走到结构体的末尾,我们就可以以它作为限制条件,每经过一个节点,就打印一次数据,直到遇到空指针停止。 

然后就是要完成指定位置之前插入数据了。

假设有一个链表1->>2->>3->>5->>NULL.

我们要在数据5的前面插入4.可是在插入之前,我们要找到数据五的位置才能插入。

如何查找元素呢?

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

第一个参数是指向第一个节点的指针,第二个是要寻找的数据,虽然这里可能会存在相同的数字,但是这只是我们练习的场景,假设我们要存储人的身份信息,这是不可能存在相同的人的,所以我们这里假设数据不相同。

最后返回这个节点的地址。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {assert(phead);SLTNode* pcur = phead;while (pcur) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
};

和打印数据相同。我们只需要遍历整个数组即可,如果找到就返回这个节点的地址,否则就返回空。

接着我们再来完成指定位置插入数据。

即使我们找打这个节点的地址,我们要在它之前插入数据,也就是再创建一个节点,然后把这个节点的next指针指向找的节点,这样我们就在指定节点前面插入了数据。

但是我们新建的这个节点是没有被节点指向的,所以我们还要让前一个节点指向新的节点。

这个SLTBuyNode是创建新节点函数,我们在插入数据时,会频繁用到这个代码,如果重复的写,就太浪费时间了,所以我们单独封装一个函数来完成这个功能。

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

可是这样写就完了吗?

如果我们要在链表的第一个节点之前插入数据,我们会发现这个代码循环是根本没有进入的,并且会访问NULL地址,这是非法的。

所以为了防止这样的问题,我们还需要额外区分头插的情况。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(*pphead);if (*pphead == pos) {*pphead = SLTBuyNode(x);(*pphead)->next = pos;}else {SLTNode* pcur = *pphead;while (pcur->next != pos) {pcur = pcur->next;}pcur->next = SLTBuyNode(x);pcur->next->next = pos;}
};

 然后我们来思考,为什么这里要使用二级指针,我们使用指针的目的是为了在函数中改变指针所指向的变量的值,这里就是传值和传址的区别了,我们在头插的过程中指向头节点的指针,是会改变的,如果我们传一级指针,是改变不了这个指针的,所以我们要使用二级指针。

然后就是删除数据函数

void SLTErase(SLTNode** pphead, SLTNode* pos);

这里与插入函数一样,是需要考虑头删的。

void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;if (pos == *pphead) {*pphead = pos->next;free(pos);}else {while (pcur->next != pos) {pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
};

删除指定节点,只需要我们将前一个节点指向下一个节点就行了,然后再释放指定节点即可 。

而头删就是释放头节点,然后将头指针指向头节点的下一个节点既可以。

为了方便,头插头删位插尾删,我们都使用前面两个函数来进行完成,这样更加方便。

void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);if (*pphead == NULL) {*pphead = SLTBuyNode(x);}else {SLTInsert(pphead,NULL,x);}
}

在尾插时,如果链表为空,我们就直接创建一个新的节点即可,否则我们就只需要在NULL前面插入一个节点即可,因为最后一个节点的next指针指向的是空。

void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);if (*pphead == NULL) {*pphead = SLTBuyNode(x);}else {SLTInsert(pphead, *pphead, x);}
};

头插同理,如果链表为空直接创建新的链表即可,否则就是在头节点之前插入即可,而且头节点直接作为参数给我们使用了,所以我们就不需要再查找了. 

void SLTPopBack(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur->next != NULL) {pcur = pcur->next;}SLTErase(pphead,pcur);
};

尾删就需要我们遍历链表,找到最后一个链表的指针 ,这样再删除即可。链表为空就不能删了,所以我们要断言一下。

void SLTPopFront(SLTNode** pphead) {assert(pphead && *pphead);SLTErase(pphead,*pphead);
};

头删更简单,不需要遍历,直接调用删除函数即可。

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* next = SLTBuyNode(x);next->next = pos->next;pos->next = next;
};
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {assert(pos);SLTNode* next = pos->next;pos->next = next->next;free(next);next = NULL;
};

 这里是同理,要插入就直接创建新链表然后插入即可,删除也是同理,这里是需要判断pos是否为空的,因为如果没有找到find函数就会返回空。

删除链表

void SListDesTroy(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur) {SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
};

就需要遍历整个链表然后依次释放,最后为了防止野指针,我们还需要将*pphead置为NULL。 

三.链表 

链表的种类有很多种。

任意两两组合就有2 * 2 * 2 = 8种组合

这个带头和不带头后面双链表再讲解。

我们通常所说的单链表是不带头单向不循环链表。

单向就是通过一个只能访问下一个节点不能访问上一个节点,否则就是双向。

循环就是链表围成一个圈,链表的最后一个节点next指向头节点了,而不是NULL.

虽然有这么多的链表的结构,但是我们实际中最常⽤还是两种结构: 单链表 双向带头循环链表
  1.  ⽆头单向⾮循环链表:结构简单,⼀般不会单独⽤来存数据。实际中更多是作为其他数据结 构的⼦结构,如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
  2.  带头双向循环链表:结构最复杂,⼀般⽤在单独存储数据。实际中使⽤的链表数据结构,都 是带头双向循环链表。另外这个结构虽然结构复杂,但是使⽤代码实现以后会发现结构会带 来很多优势,实现反⽽简单了,后⾯我们代码实现了就知道了。

 

相关文章:

单链表讲解

一.链表的概念以及结构 链表是一种物理结构上不连续,逻辑结构上连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表的结构与火车是类似的,一节一节的,数据就像乘客一样在车厢中一样。 与顺序表不同的…...

DFS算法系列 回溯

DFS算法系列-回溯 文章目录 DFS算法系列-回溯1. 算法介绍2. 算法应用2.1 全排列2.2 组合2.3 子集 3. 总结 1. 算法介绍 回溯算法是一种经典的递归算法,通常被用来解决排列问题、组合问题和搜索问题 基本思想 从一个初始状态开始,按一定的规则向前搜索&…...

Linux C应用编程:MQTT物联网

1 MQTT通信协议 MQTT(Message Queuing Telemetry Transport,消息队列遥测传 输)是一种基于客户端-服务端架构的消息传输协议,如今,MQTT 成为了最受欢迎的物联网协议,已广泛应用于车联网、智能家居、即时聊…...

企业常用Linux文件命令相关知识+小案例

远程连接工具无法连接VMWARE: 如果发现连接工具有时连不上,ip存在,这时候我们查看网络编辑器,更多配置,看vnet8是不是10段,nat设置是否是正确的? 软件重启一下虚机还原一下网络编辑器 查看文件…...

Istio介绍

1.什么是Istio Istio是一个开源的服务网格(Service Mesh)框架,它提供了一种简单的方式来为部署在Kubernetes等容器编排平台上的微服务应用添加网络功能。Istio的核心功能包括: 服务治理:Istio能够帮助管理服务之间的…...

代码随想录算法训练营第四十七天|leetcode115、392题

一、leetcode第392题 本题要求判断s是否为t的子序列,因此设置dp数组,dp[i][j]的含义是下标为i-1的子串与下标为j-1的子串相同字符的个数,可得递推公式是通过s[i-1]和t[j-1]是否相等区分。 具体代码如下: class Solution { publ…...

将Ubuntu18.04默认的python3.6升级到python3.8

1、查看现有的 python3 版本 python3 --version 2、安装 python3.8 sudo apt install python3.8 3、将 python3.6 和 3.8 添加到 update-alternatives sudo update-alternatives --install /usr/bin/python3 python3 /usr/bin/python3.6 1 sudo update-alternatives --insta…...

Python和Java哪个更适合后端开发?

Python和Java都是强大的后端开发语言,它们各自有鲜明的特点和适用场景。选择哪一个更适合后端开发,主要取决于具体的项目需求、团队技术栈、个人技能偏好以及长期发展考虑等因素。 下面是两者在后端开发中的优势和劣势: 「Python&#xff1…...

Python+pytest接口自动化之cookie绕过登录(保持登录状态)

前言 我们今天来聊聊pythonpytest接口自动化之cookie绕过登录(保持登录状态),在编写接口自动化测试用例或其他脚本的过程中,经常会遇到需要绕过用户名/密码或验证码登录,去请求接口的情况,一是因为有时验证…...

什么数据集成(Data Integration):如何将业务数据集成到云平台?

说到数据集成(Data Integration),简单地将所有数据倒入数据湖并不是解决办法。 在这篇文章中,我们将介绍如何轻松集成数据、链接不同来源的数据、将其置于合适的环境中,使其具有相关性并易于使用。 数据集成&#xff1…...

国外EDM邮件群发多少钱?哪个软件好?

在当今全球化市场环境下,电子邮件营销作为最有效的数字营销渠道之一,其影响力不容忽视。而高效精准的EDM(Electronic Direct Mail)邮件营销策略更是企业拓展海外市场、提升品牌知名度的关键手段。云衔科技以其创新的智能EDM邮件营…...

C语言入门算法——回文数

题目描述: 若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。 例如:给定一个十进制数 56,将 56 加 65(即把 56 从右向左读),得到 121 是一个…...

OceanBase—操作实践

文档结构 1、概念简介2、核心设计3、操作实践3.3、数据同步 官方文档:https://www.oceanbase.com/docs/oceanbase-database-cn 1、概念简介 版本分为社区版和企业版,其中企业版兼容MySQL 和Oracle数据库语法; 2、核心设计 存储层 复制层 …...

智慧用电安全管理系统

智慧用电安全管理系统 智慧用电安全管理系统是智能电网中客户侧关键的构成部分,是基本建设新型智慧城市的基本,将完成地区内各种各样用电设备的智能化系统监管,完成地区内日常生活与工作中安全性、舒服。 一、智慧用电安全管理系统介绍 …...

Rust语言入门第二篇-Cargo教程

文章目录 Rust语言入门第二篇-Cargo教程一,Cargo 是什么二,Cargo教程Cargo.toml文件src/main.rs 文件构建并运行Cargo项目 Rust语言入门第二篇-Cargo教程 本节提供对cargo命令行工具的快速了解。我们演示了它为我们生成新包的能力,它在包内编…...

测试用例的编写方式

学习目标 能对穷举场景设计测试点能对限定边界规则设计测试点能对多条件依赖关系进行设计测试点能对于项目业务进行设计测试点 目录 等价类划分法案例 等价类划分 说明:在所有测试数据中,具有某种共同特征的数据集合进行划分分类: 有效等…...

HarmonyOS实战开发-状态管理、通过使用页面级的状态变量 和应用级的状态变量 来实现应用的状态管理。

介绍 本示例通过使用页面级的状态变量 和应用级的状态变量 来实现应用的状态管理。 效果预览 使用说明 1.点击首页中的基本类型进入对应页面,点击按钮可以更改圆形的颜色;点击查看源码可以展示基本类型功能效果的源码。 2.点击首页中的数组类型进入对…...

【Java开发指南 | 第二篇】标识符、Java关键字及注释

专栏:Java开发指南 CSDN秋说 文章目录 标识符Java关键字Java注释 标识符 Java 所有的组成部分都需要名字。类名、变量名以及方法名都被称为标识符。 所有的标识符都应该以字母(A-Z 或者 a-z),美元符($)、或者下划线&…...

3D可视化技术:研发基地的科技新篇章

在科技日新月异的今天,我们生活在一个充满无限可能性的时代。而在这个时代中,3D可视化技术正以其独特的魅力,引领着科技领域的新一轮变革。 3D可视化技术通过三维图像的方式,将现实世界或虚拟世界中的物体、场景等以立体、逼真的形…...

蓝旭前端05:JavaScript进阶

蓝旭前端05:JavaScript进阶 基础简单复习 数据类型 基本数据类型:Number、String、Boolean、Null、Undefined等。引用数据类型:Object、Array、Function等。typeof操作符:返回数据类型的字符串形式。 变量 变量声明&#xff1…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

PHP和Node.js哪个更爽?

先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...