算法模板之单链表图文讲解
文章目录
一. ⛳️使用数组模拟单链表讲解
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]];
}
二. ⛳️题目练习
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;
}
📝结语
相关文章：
Java运算符及运算符的优先级【超详细】
int a = 10;int b = 20;a + b;a < b;对操作数进行操作时的符号，不同运算符操作的含义不同。作为一门计算机语言，Java也提供了一套丰富的运算符来操纵变量。Java中运算符可分为以下：算术运算符(+ - */)、关系运算符(< > ==)、逻辑运算符、位运算符、移位运算符以及条件运算符等，接下来我们来一个一个介绍。
Java中Jar包部署nohup后台启动定时按日期分割日志
在JAVA开发中很多没有用docker部署，而是选择传统的Jar包部署方式，这样就涉及日志的产生，如果直接部署日志文件会越来越大，程序怎么可能不出现问题，这样打开日志文件就会很慢，不方便后续问题的定位和解决。这样就要采取优化方案，对日志进行分割，这样便于查看。
Java Comparator多属性排序
自然排序通常情况跟equals保持一致，e1,e2是类C的元素，如果e1.compareTo(e2) == 0 那么e1和e2 equals的结果也是true。因为有的时候它俩结果一致，比如刚好就只有一个属性排序的时候，但多数情况下，二者是不一致的。比如有多个排序属性的时候。有的时候获取的数据需要在内存排序，需要根据List中T对象的属性p1,p2,p3等进行排序，该怎么写呢？这种规则掌握了，管它几个属性排序，管它什么升序降序，通通解决。多个属性，按不同的升降序规则，就变的非常简单了，只需要在下面的。
Linux 查看磁盘空间
Linux 查看磁盘空间可以使用 df 和 du 命令。
Linux多种方法安装MySQL
源码安装：优点是安装包比较小，只有十多M，缺点是安装依赖的库多，安装编译时间长，安装步骤复杂容易出错。使用官方编译好的二进制文件安装：优点是安装速度快，安装步骤简单，缺点是安装包很大，300M左右。yum安装。rpm安装。
Linux中mysql 默认安装位置&Linux 安装 MySQL
MySQL在Linux系统上的默认安装位置是目录。这是MySQL服务器的数据目录，包含所有数据库文件。通过检查MySQL二进制文件的路径，我们可以确认MySQL是否正确安装。在目录中，MySQL使用一系列文件和子目录来组织和存储数据。确保理解MySQL数据目录的结构对于管理和维护MySQL数据库至关重要。按照顺序安装即可解决。
Linux使用systemd服务和crontab实现Shell脚本开机自动运行&编辑当前用户或者指定用户的crontab内容crontab -e
systemd是Linux系统中的一个初始化系统和服务管理器。它可以用于在系统启动时自动运行Shell脚本。crontab是一个用于定时执行任务的工具。我们可以通过编辑crontab文件来设置开机自启动。
Linux定时任务详解&crontab -e 编辑之后如何保存并退出（Ubuntu）
Linux定时任务是一种可执行的命令或者脚本，在特定的时间或者时间间隔下自动执行。通过在系统中预设一些需要执行的任务，可以让Linux定时任务自动执行并完成这些任务。定时任务可以用于自动备份、系统清理、监控、自动化维护等任务。在Linux中，常用的定时任务程序有系统自带的cron和at命令。其中，cron是一个强大的定时任务工具，可以按照设定的实际时间执行命令，非常常用。anacron最小检测周期是天，使用anacron管理的定时任务应该最小是每隔一天执行。
nginx常用操作命令
都启动了同一个Nginx进程。不一样的是：1、Systemd 是一系列工具的集合，其作用也远远不仅是启动操作系统，它还接管了后台服务、结束、状态查询。2、Systemd更方便作服务管理，启动管理Nginx更佳方便。3、Systemd可以作开机服务管理，让服务跟随系统启动。
linux配置nginx开机自启&nginx部署与systemctl控制启动&/etc/systemd/system 和 /lib/systemd/system 的区别
目录/lib/systemd/system 以及/usr/lib/systemd/system 其实指向的是同一目录，在/目录下执行命令lltotal 28该目录中包含的是软件包安装的单元,也就是说通过 yum、dnf、rpm 等软件包管理命令管理的 systemd 单元文件，都放置在该目录下。/etc/systemd/system/(系统管理员安装的单元, 优先级更高)在一般的使用场景下，每一个 Unit（服务等） 都有一个配置文件，告诉 Systemd 怎么启动这个 Unit。
spring 笔记七 Spring JdbcTemplate
它是spring框架中提供的一个对象，是对原始繁琐的JdbcAPI对象的简单封装。spring框架为我们提供了很多的操作模板类。例如：操作关系型数据的JdbcTemplate和HibernateTemplate，操作nosql数据库的RedisTemplate，操作消息队列的JmsTemplate等等。
spring 笔记八 SpringMVC异常处理和SpringMVC拦截器
① 创建异常处理器类实现HandlerExceptionResolver② 配置异常处理器③ 编写异常页面④ 测试异常跳转①创建异常处理器类实现HandlerExceptionResolver@Override//处理异常的代码实现//创建ModelAndView对象②配置异常处理器③编写异常页面。
【redis】Redis 架构演化之路
里面大致说了redis的架构演进。开始学redis架构的时候，总是感觉架构好多，迷迷糊糊的，但是你知道Redis 架构演化之路之后，就明白了前因后果，这样学习更加深入以及搞笑。这篇文章我想和你聊一聊 Redis 的架构演化之路。现如今 Redis 变得越来越流行，几乎在很多项目中都要被用到，不知道你在使用 Redis 时，有没有思考过，Redis 到底是如何稳定、高性能地提供服务的？如果你对 Redis 已经有些了解，肯定也听说过。
【redis】Redis哨兵机制和集群有什么区别？
Redis哨兵机制和集群有什么区别？redis集群有几种实现方式，一个是主从集群，一个是redis cluster.
Elasticsearch分布式搜索分析引擎本地部署与远程访问
本文主要讲解如何使用Elasticsearch分布式搜索分析引擎本地部署与远程访问
讲解K-Means聚类算法进行压缩图片
在本文中，我们讲解了如何使用K-Means聚类算法来压缩图像。通过K-Means算法，我们能够找到图像中的主要颜色，并用这些颜色替换原始图像中的像素颜色，从而实现图像的压缩。这个简单的技术可以在一定程度上减小图像文件的大小，同时保持图像的可视化效果。希望这篇文章能够帮助你理解如何使用K-Means聚类算法进行图像压缩。如果你想进一步学习图像处理和压缩的知识，推荐你深入研究相关的算法和工具。
讲解pytorch可视化 resnet50特征图
然后，我们加载了查询图像，并提取了查询图像的特征。接下来，我们以类似的方式对图像数据库中的每个图像提取特征。然后，我们计算查询图像特征与数据库中每个图像特征的相似度，并根据相似度对数据库图像进行排序。通过这种方法，我们可以使用ResNet50的特征图来构建一个简单的图像检索系统。该系统可以在图像数据库中找到与查询图像相似的图像，从而在实际应用中具有广泛的用途，如图像搜索引擎、商品推荐等。这对于理解模型在图像中学到的特征非常有帮助，并帮助我们进行图像分析和理解计算机视觉模型的工作原理。最后，我们使用模型的。
讲解Unsupported gpu architecture ‘compute_*‘2017解决方法
在使用2017年以前的NVIDIA GPU进行深度学习训练时，经常会遇到"Unsupported GPU Architecture 'compute_*'"的错误。本篇文章将介绍该错误的原因并提供解决方法。
讲解c1xx: fatal error C1356: 无法找到 mspdbcore.dll
本文介绍了这个错误的原因，并提供了一些解决方案来解决这个问题。如果你遇到这个错误，请尝试上述解决方案，希望能帮助你解决这个问题并顺利进行 C++ 编程。这个错误通常出现在编译过程中，而且很可能是由于缺少或损坏了 mspdbcore.dll 文件引起的。在本文中，我们将讨论这个错误的原因，并提供一些解决方案来解决这个问题。是 Visual Studio 内部使用的一个关键文件，它提供了用于编译、链接和调试的重要功能。这有时可以清除一些隐藏的配置问题，并解决。错误时，下面的示例代码可以帮助你解决这个问题。
讲解TypeError: Class advice impossible in Python3. Use the @Implementer class decorator instead
在Python3中，当我们尝试在类上使用旧的类修饰符（class decorator）时，可能会遇到的错误。为了解决这个问题，我们可以使用类修饰符来替代旧的类修饰符。类修饰符是模块提供的一个装饰器，用于实现接口定义。通过使用类修饰符，我们可以在Python3中实现类方法和静态方法的装饰，同时保持代码的兼容性和可读性。希望本文能够帮助你理解如何解决错误，并正确使用类修饰符来装饰类方法和静态方法。
docker搭建maven私库Nexus3
阿里代理地址：http://maven.aliyun.com/nexus/content/groups/public/由于nexus的默认端口为8081，我们在启动的时候改为18091后需要修改nexus的配置文件。这样就可以在本地浏览器进入nexus页面了，地址为 服务器ip:18091。右上角登录用户名为admin,密码为之前查看的密码。配置maven-central的代理地址。删除nuget开头的仓库。同时查看admin密码。
Gitlab基础篇： Gitlab docker 安装部署、Gitlab 设置账号密码
安装docker gitlab前确保docker环境，如果没有搭建docker请查阅“Linux docker 安装文档”可以看到在docker ps -a 打印中看到 容器ID ps 展示的容器ID只时原来的一部分。修改docker镜像的gitlab容器端口前需要把gitlab容器以及docker镜像关闭。通过容器ID就能找到containers下具体哪一个是gitlab容器的配置。修改config.v2.json、hostconfig.json文件。docker 下载 gitlab容器。
spring 笔记五 SpringMVC的数据响应
上述方式手动拼接json格式字符串的方式很麻烦，开发中往往要将复杂的java对象转换成json格式的字符串，我们可以使用web阶段学习过的json转换工具jackson进行转换，导入jackson坐标。在方法上添加@ResponseBody就可以返回json格式的字符串，但是这样配置比较麻烦，配置的代码比较多，因此，我们可以使用mvc的注解驱动代替上述配置。② 将需要回写的字符串直接返回，但此时需要通过@ResponseBody注解告知SpringMVC框架，方法。
spring 笔记六 SpringMVC 获得请求数据
• SpringMVC默认已经提供了一些常用的类型转换器，例如客户端提交的字符串转换成int型进行参数设置。• 但是不是所有的数据类型都提供了转换器，没有提供的就需要自定义转换器，例如：日期类型的数据就需要自定义转换器。自定义类型转换器的开发步骤：① 定义转换器类实现Converter接口② 在配置文件中声明转换器③ 在中引用转换器①定义转换器类实现Converter接口@Overridetry {②在配置文件中声明转换器
static final、static、@PostConstruct、构造方法、@AutoWired执行的顺序
Java提供的注解，被用来修饰方法，被@PostConstruct修饰的方法会在服务器加载Servlet的时候运行，并且只会被服务器执行一次。PostConstruct在构造函数之后执行，init（）方法之前执行。调用的顺序为： 构造函数 > @Autowired > @PostConstruct(2)作用：@PostConstruct注解的方法在项目启动的时候执行这个方法，也可以理解为在spring容器启动的时候执行，可作为一些数据的常规化加载，比如读取数据字典之类、目录树缓存。
【HarmonyOS开发】拖拽动画的实现
在开发拖拽动画时，发现png的图片在拖拽结束后，会出现图片闪动的不流畅问题，改为svg图片解决。因此通过大量的对比验证，确认为鸿蒙底层窜然问题。
YOLOv8-Pose训练自己的数据集
至此，整个YOLOv8-Pose模型训练预测阶段完成。此过程同样可以在linux系统上进行，在数据准备过程中需要仔细，保证最后得到的数据准确，最好是用显卡进行训练。有问题评论区见！
【Redis】Redis中的大key怎么处理？
在Redis中，大key是指存储了大量数据的键。处理大key可能会对Redis服务器的性能和资源消耗产生负面影响。询问这个问题，首先要知道redis的大key会有什么影响。大key占用的内存空间较大，当大量的大key存在时，会消耗大量的内存资源。这可能导致Redis服务器的内存不足，并触发内存溢出，从而影响系统的稳定性和性能。当读取或写入大key时，需要将大量的数据通过网络传输。对于大量的网络传输，特别是在高并发的情况下，会增加整体的延迟，并占用带宽资源。
【Redis】Redis中执行Keys命令会有什么问题？
如果需要根据某种模式来获取键，更好的选择是使用更高效的命令，如SCAN命令，它使用游标方式迭代返回匹配的键，避免了遍历整个键空间的性能问题，并且可以逐步处理数据。KEYS命令用于检索匹配指定模式的所有键。如果匹配的键非常多，返回的结果列表可能巨大无比，占用大量的内存。在极端情况下，如果执行KEYS命令返回的结果集非常大，并且内存不足以容纳整个结果集，Redis服务器可能会发生内存溢出错误。如果KEYS命令运行时间较长或遇到大量匹配的键，会导致服务器长时间无法响应其他请求，从而对系统的可用性产生负面影响。
Vue 3 开发中遇到的问题及解决方案（fix bug）
vite v3.2.4 building for development...'hasInjectionContext' is not exported by node_modules/pinia/node_modules/vue-demi/lib/index.mjs, imported by node_modules/pinia/dist/pinia.mjsat ../node_modules/pinia/dist/pinia.mjs:6:9 4: * @license MIT 5: */