算法模板之单链表图文讲解

🌈个人主页:聆风吟
🔥系列专栏:算法模板、数据结构
🔖少年有梦不应止于心动,更要付诸行动。
文章目录
- 📋前言
- 一. ⛳️使用数组模拟单链表讲解
- 1.1 🔔为什么我们要使用数组去模拟单链表?
- 1.2 🔔用数组模拟实现单链表
- 1.2.1 👻整体框架说明
- 1.2.3 👻单链表插入结点
- 1.2.4 👻单链表删除结点
- 1.3 🌟模板提取(重点)🌟
- 二. ⛳️题目练习
- 2.1 题目
- 2.2 输入样例
- 2.3 输出样例
- 2.4 c++代码
- 📝结语
📋前言
💬 hello! 各位铁子们大家好哇,今天作者给大家带来的是使用使用数组模拟单链表,让我们一起加油进步。
📚 系列专栏:本期文章收录在《算法模板》,大家有兴趣可以浏览和关注,后面将会有更多精彩内容!
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
一. ⛳️使用数组模拟单链表讲解
1.1 🔔为什么我们要使用数组去模拟单链表?
假如你学过数据结构,那么你对链表的第一反应可能就是:由一系列结点组成,每个结点包含两个域,其中一个域用于存储数据元素,另一个域用于存储下一个结点的地址。节点的表示形式如下:
class Node{
public:int val;Node* next;
};
这种构造形式是我们常见的,使用该方法,在创建 一个值为 x 的新结点的时候,语法如下:
Node* node = new Node();
node->val = x
代码分析:Node* node = new Node();,中间有一个 new 关键字来为新对象分配空间。new 的底层涉及内存分配,调用构造函数,指针转换等多种复杂且费时的操作。由于一秒大概只能 new 一万次左右。在平时的工程代码中,不会涉及上万次的new操作,所以这种使用这种结构创建单链表是一种 见代码知意 的好结构。
但是在算法比赛中,经常碰到在10w级别以上的链表操作,如果使用结构体这种方式创建链表,是无法在算法规定时间完成的。因此,在算法比赛这种有严格的时间要求的环境中,不能频繁使用new操作。所以在这里我们采用数组去模拟单链表。
1.2 🔔用数组模拟实现单链表
1.2.1 👻整体框架说明
初始状态:将头指针head指向空结点。

插入结点状态:
- 创建数组
val和ne分别存储某个结点的值和指向下个结点的next指针; - 使用数组下表进行关联,通过数组ne将整个链表链接起来;
- 空结点的下表用 - 1 来表示;

### 1.2.2 👻单链表查找和修改 因为是使用数组模拟出来的链表,所以对于查找和修改直接通过数组下标进行遍历查找即可,这里就不多叙述。
1.2.3 👻单链表插入结点
1. 头插:将 x 插入到头结点

代码展示(建议结合图示看注释):
//将x插到头结点
//idx 存储当前已经用到了哪个点,即记录当前下标位置
void add_to_head(int x)
{val[idx] = x;//记录要插入结点的数据ne[idx] = head;//将待插结点指向头结点head = idx;//断开头指针head指向的头结点的箭头,改为指向待插入结点idx++;//下标向后移一位,为下一次插入元素做准备。
}
2. 任意位置插入:将 x 插入到下标是k的结点后面

代码展示(建议结合图示看注释):
//将x插到下标是k的结点后面
//idx 存储当前已经用到了哪个点,即记录当前下标位置
void add(int k, int x)
{val[idx] = x;//记录要插入结点的数据ne[idx] = ne[k];//将待插结点指向下标为k结点的下个结点ne[k] = idx;//断开下标为k到k+1结点的箭头,将下标为k的结点改为指向待插入结点idx++;//下标向后移一位,为下一次插入元素做准备。
}
1.2.4 👻单链表删除结点
将下标为 k 的结点 后面的结点删掉

代码展示(建议结合图示看注释):
//将下标是k的点后面的点删掉
void remove(int k)
{ne[k] = ne[ne[k]];//让k指向的改为指向下下个结点,那中间的那个结点就被挤掉了。
}
1.3 🌟模板提取(重点)🌟
模板代码
// head 表示头结点的下标
// val[i] 表示结点i的值
// ne[i] 表示结点i的next指针是多少
// idx 存储当前已经用到了哪个点,即记录当前下标位置
int head, val[N], ne[N], idx;//初始化
void init()
{head = -1;//将头指针head指向空结点。idx = 0;//下标置为0
}//将 x 插入到头结点
void add_to_head(int x)
{val[idx] = x; ne[idx] = head;head = idx;idx++;
}//将 x 插入到下标是k的结点后面
void add(int k, int x)
{val[idx] = x;ne[idx] = ne[k];ne[k] = idx;idx++;
}//将下标是k的点后面的点删掉
void remove(int k)
{ne[k] = ne[ne[k]];
}
二. ⛳️题目练习
⌈ 在线OJ链接,可以转至此处自行练习 ⌋
2.1 题目

2.2 输入样例
3
H 9
I 1 1
D 1
2.3 输出样例
9
2.4 c++代码
#include <iostream>using namespace std;const int N = 100010;
// head 表示头结点的下标
// val[i] 表示结点i的值
// ne[i] 表示结点i的next指针是多少
// idx 存储当前已经用到了哪个点,即记录当前下标位置
int head, val[N], ne[N], idx;//初始化
void init()
{head = -1;idx = 0;
}//将 x 插入到头结点
void add_to_head(int x)
{val[idx] = x; ne[idx] = head;head = idx;idx++;
}//将 x 插入到下标是k的结点后面
void add(int k, int x)
{val[idx] = x;ne[idx] = ne[k];ne[k] = idx;idx++;
}//将下标是k的点后面的点删掉
void remove(int k)
{ne[k] = ne[ne[k]];
}int main()
{int m;cin >> m;init();//切记:初始化while(m--){int k, x;char op;cin >> op;//判断执行哪种操作if(op == 'H'){//执行头插操作cin >> x;add_to_head(x);}else if(op == 'D'){//执行删除操作cin >> k;if(k == 0) head = ne[head];//删除头节点remove(k - 1);//注意删除第k个输入后面的数,那函数里放的是下标,k要减去1}else{//执行指定位置插入操作cin >> k >> x;add(k - 1, x);}}for(int i = head; i != -1; i = ne[i]) cout << val[i] << " ";cout << endl;return 0;
}
📝结语
今天的干货分享到这里就结束啦!如果觉得文章还可以的话,希望能给个三连支持一下,聆风吟的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是作者前进的最大动力!

相关文章:
算法模板之单链表图文讲解
🌈个人主页:聆风吟 🔥系列专栏:算法模板、数据结构 🔖少年有梦不应止于心动,更要付诸行动。 文章目录 📋前言一. ⛳️使用数组模拟单链表讲解1.1 🔔为什么我们要使用数组去模拟单链表…...
【强化学习-读书笔记】表格型问题的 Model-Free 方法
参考 Reinforcement Learning, Second Edition An Introduction By Richard S. Sutton and Andrew G. Barto无模型方法 在前面的文章中,我们介绍的是有模型方法(Model-Based)。在强化学习中,"Model"可以理解为算法…...
【手撕算法系列】k-means
k-means k-means算法介绍 k-means算法介绍 K-means算法是一种用于聚类的迭代算法,它将数据集划分为K个簇,其中每个数据点属于与其最近的簇的中心。这个算法的目标是最小化簇内的平方和误差(簇内数据点与簇中心的距离的平方和)。 …...
D33|动态规划!启程!
1.动态规划五部曲: 1)确定dp数组(dp table)以及下标的含义 2)确定递推公式 3)dp数组如何初始化 4)确定遍历顺序 5)举例推导dp数组 2.动态规划应该如何debug 找问题的最好方式就是把…...
C语言----文件操作(二)
在上一篇文章中我们简单介绍了在C语言中文件是什么以及文件的打开和关闭操作,在实际工作中,我们不仅仅是要打开和关闭文件,二是需要对文件进行增删改写。本文将详细介绍如果对文件进行安全读写。 一,以字符形式读写文件ÿ…...
oracle 10046事件跟踪
10046事件是一个很好的排查sql语句执行缓慢的内部事件,具体设置方式如下: 根据10046事件跟踪SQL语句 1、 alter session set events 10046 trace name context forever,level 12; 2、执行SQL语句 3、关闭10046事件 alter session set events 10046 trace…...
微软自带浏览器Edge,无法关闭“保存历史记录网站的屏幕截图”解决方案
微软自带浏览器Edge,无法关闭“保存历史记录网站的屏幕截图”解决方案 吐槽1:Windows自带的Chrome内核版本的浏览器Microsofg Edge刚发布时可谓一股清流,启动速度快,占用内存较小,相信很多人也开始抛弃正代Chrome&…...
讲座 | 颠覆传统摄像方式乃至计算机视觉的“脉冲视觉”
传统相机拍摄视频时其实是以一定帧率进行采样,视频其实还是一串图片的集合,因此低帧率时会觉得视频卡,拍摄高速运动物体时会有运动模糊等等问题。然而你能想象这一切都可以被“脉冲视觉”这一前沿技术改变吗? 今天下午听了北京大学…...
uniGUI学习之UniHTMLMemo1富文本编辑器
1]系统自带的富文本编辑器 2]jQueryBootstarp富文本编辑器插件summernote.js 1]系统自带的富文本编辑器 1、末尾增加<p> 2、增加字体 3、解决滚屏问题 4、输入长度限制问题 5、显示 并 编辑 HTML源代码(主要是图片处理) 1、末尾增加<p> UniHTMLMemo1.Lines…...
详细教程 - 从零开发 鸿蒙harmonyOS应用 第四节 (鸿蒙Stage模型 登录页面 ArkTS版 推荐使用)
在鸿蒙OS中,Ability是应用程序提供的抽象功能,可以理解为一种功能。在应用程序中,一个页面即一种能力,如登录页面,即具有登录功能的能力。以下是对鸿蒙新建项目的登录代码功能的详细解读和工作流程的描述: …...
uniapp怎么实现授权登录
在Uniapp中实现授权登录通常涉及以下几个步骤: 创建登录按钮:在页面中创建一个按钮,用于触发登录操作。 获取用户授权:当用户点击登录按钮时,调用uni.login或uni.getUserInfo等API获取用户授权。 处理授权回调&#…...
从零开始:前端架构师的基础建设和架构设计之路
文章目录 一、引言二、前端架构师的职责三、基础建设四、架构设计思想五、总结《前端架构师:基础建设与架构设计思想》编辑推荐内容简介作者简介目录获取方式 一、引言 在现代软件开发中,前端开发已经成为了一个不可或缺的部分。随着互联网的普及和移动…...
椋鸟C语言笔记#26:数据在内存中的存储(大小端字节序)、浮点数的存储(IEEE754)
萌新的学习笔记,写错了恳请斧正。 目录 大小端字节序 什么是大小端 写一个判断大小端的程序 浮点数在内存中的存储(IEEE 754规则) 引入 存储规则解释 读取规则解释 1.阶码不全为0或全为1(规格化数) 2.阶码全为…...
设计模式——组合模式(结构型)
引言 组合模式是一种结构型设计模式, 你可以使用它将对象组合成树状结构, 并且能像使用独立对象一样使用它们。 问题 如果应用的核心模型能用树状结构表示, 在应用中使用组合模式才有价值。 例如, 你有两类对象: …...
鸿蒙小车之多任务调度实验
说到鸿蒙我们都会想到华为mate60:遥遥领先!我们一直领先! 我们这个小车也是采用的是鸿蒙操作系统,学习鸿蒙小车,让你遥遥领先于你的同学。 文章目录 前言一、什么是任务?为什么要有任务二、任务的状态三、任…...
【报错栏】(vue)Module not found: Error: Can‘t resolve ‘element-ui‘ in xxx
Module not found: Error: Cant resolve element-ui in xxx 报错原因是: 未安装 element-ui 依赖 解决: npm install element-ui 运行...
seaborn库图形进行数据分析(基于tips数据集)
Seaborn 是一个基于 matplotlib 的数据可视化库,可以用来绘制各种统计图表,包括散点图、条形图、折线图、箱线图等。Seaborn 提供了一些用于美化图表的默认样式和颜色主题,使得生成的图表更具有吸引力。下面是一些 Seaborn 库的常用功能和用法…...
AC843. n皇后问题--60
我们只需要把蓝色的往上移动就行了 if(!col[i][j]&&!dg[ui]&&!udg[])//1y(i)向下,x(u)向右为正。yxb的by-x一定>0,y-xb的bxy可能>0,这个不考虑,只看-bxy....
Js WebSocket类,收发Json,带心跳,断线重连
如题 心跳:4秒发一次 断线:2秒后自动重连 收发:发送和返回json,处理粘包断包等情况,json字符串最大长度9999 缓存:未连接时,自动缓存100个包,当连接时会自动发出 JS代码 var MyWeb…...
VBA技术资料MF96:单字段多条件高级筛选
我给VBA的定义:VBA是个人小型自动化处理的有效工具。利用好了,可以大大提高自己的工作效率,而且可以提高数据的准确度。我的教程一共九套,分为初级、中级、高级三大部分。是对VBA的系统讲解,从简单的入门,到…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
