C++小记 -链表
链表
文章目录
- 链表
- 链表基础理论
- 链表的类型
- 单链表
- 双链表
- 循环链表
- 链表的存储方式
- 链表的定义
- 链表的操作
- 添加节点
- 删除节点
- 性能分析
- 构建链表
- 删除节点(内存泄漏的坑)
- 1.直接移除
- 2.使用虚拟头结点
- 3.delete指针后,要将指针置为NULL!!
- 完整代码示例
链表基础理论
什么是链表,链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。
链表的入口节点称为链表的头结点也就是head。
链表的类型
单链表

双链表

单链表中的指针域只能指向节点的下一个节点。
双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
循环链表
循环链表,顾名思义,就是链表首尾相连。
循环链表可以用来解决约瑟夫环

链表的存储方式
数组是在内存中是连续分布的,但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ,而是散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理。

这个链表起始节点为2, 终止节点为7, 各个节点分布在内存的不同地址空间上,通过指针串联在一起。
链表的定义
// 单链表
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};
有同学说了,我不定义构造函数行不行,答案是可以的,C++默认生成一个构造函数。
但是这个构造函数不会初始化任何成员变量,下面我来举两个例子:
通过自己定义构造函数初始化节点:
ListNode* head = new ListNode(5);
使用默认构造函数初始化节点:
ListNode* head = new ListNode();
head->val = 5;
所以如果不定义构造函数使用默认构造函数的话,在初始化的时候就不能直接给变量赋值!
链表的操作
添加节点

删除节点
删除D节点,如图所示:

delete root;
只要将C节点的next指针 指向E节点就可以了。
那有同学说了,D节点不是依然存留在内存里么?只不过是没有在这个链表里而已。
是这样的,所以在C++里最好是再手动释放这个D节点,释放这块内存。
性能分析

数组在定义的时候,长度就是固定的,如果想改动数组的长度,就需要重新定义一个新的数组。
链表的长度可以是不固定的,并且可以动态增删, 适合数据量不固定,频繁增删,较少查询的场景。
构建链表
// 数组构造链表
ListNode* construct_array(const vector<int>& vec) {if (vec.empty()) return nullptr;ListNode* head = new ListNode(vec[0]);ListNode* cur = head;for (int i = 1; i < vec.size(); i++) {cur->next = new ListNode(vec[i]);cur = cur->next;}cur->next = NULL;return head;
}
删除节点(内存泄漏的坑)
1.直接移除
ListNode* removeElements1(ListNode* head, int val) {// 删除头节点while (head!=NULL && head->val == val){ListNode* tmp = head;head = head->next;delete tmp;tmp = NULL;}// 删除非头节点ListNode* cur = head;while (cur != NULL && cur->next != NULL){if (cur->next->val == val){ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;tmp = NULL;}else{cur = cur->next;}}return head;
}
2.使用虚拟头结点
ListNode* removeElements2(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点dummyHead->next = head; // 将虚拟头结点指向head,这样方便后面做删除操作ListNode* cur = dummyHead;while (cur->next != NULL) {if (cur->next->val == val) {ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;tmp = NULL; }else {cur = cur->next;}}head = dummyHead->next;delete dummyHead;return head;
}
3.delete指针后,要将指针置为NULL!!
在delete指针后,将指针置为NULL。例如:delete tmp; tmp = NULL;
在delete指针后,将指针置为NULL。例如:delete tmp; tmp = NULL;
在delete指针后,将指针置为NULL。例如:delete tmp; tmp = NULL;
不然会发生内存泄漏!!!
不然会发生内存泄漏!!!
不然会发生内存泄漏!!
完整代码示例
#include <iostream>
#include <vector>
using namespace std;// 单链表
struct ListNode
{int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode() : val(NULL), next(NULL){} // 节点的构造函数ListNode(int x) : val(x), next(NULL){} // 节点的构造函数
};// 数组构造链表
ListNode* construct_array(const vector<int>& vec) {if (vec.empty()) return nullptr;ListNode* head = new ListNode(vec[0]);ListNode* cur = head;for (int i = 1; i < vec.size(); i++) {cur->next = new ListNode(vec[i]);cur = cur->next;}cur->next = NULL;return head;
}// 添加节点
void append(ListNode* head, int value){if (!head){head = new ListNode(value);}else{ListNode* cur = head;while (cur->next){cur = cur->next;}cur->next = new ListNode(value);}
}/* 删除节点
在delete指针后,将指针置为NULL。例如:delete tmp; tmp = NULL;
在delete指针后,将指针置为NULL。例如:delete tmp; tmp = NULL;
在delete指针后,将指针置为NULL。例如:delete tmp; tmp = NULL;
*/
ListNode* removeElements(ListNode* head, int val) {// 删除头节点while (head != NULL && head->val == val){ListNode* tmp = head;head = head->next;delete tmp;tmp = NULL;}// 删除非头节点ListNode* cur = head;while (cur != NULL && cur->next != NULL){if (cur->next->val == val){ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;tmp = NULL;}else{cur = cur->next;}}return head;
}// 打印链表
void printList(ListNode* head){ListNode* cur = head;while (cur){cout << cur->val << " ";cur = cur->next;}cout << endl;
}int main() {vector<int> arry = { 1, 3, 3, 4, 5 };ListNode* head = construct_array(arry);printList(head);append(head, 6);printList(head);head = removeElements(head, 3);printList(head);system("PAUSE");return 0;
}
相关文章:
C++小记 -链表
链表 文章目录 链表链表基础理论链表的类型单链表双链表循环链表 链表的存储方式链表的定义链表的操作添加节点删除节点 性能分析构建链表删除节点(内存泄漏的坑)1.直接移除2.使用虚拟头结点3.delete指针后,要将指针置为NULL!&…...
网络协议学习DAY1
1.网络协议模型: OSI协议模型 应用层 实际发送的数据 表示层 发送的数据是否加密 会话层 是否建立会话连接 传输层 数据传输的方式(数据报、流式) 网…...
vue3中全局变量的定义和获取
在vue项目中,我们知道vue2定义全局变量是在main.js文件将变量挂载到vue.prototype.name"lisi",在页面通过this.name去调用。但是在vue3中,这个定义全局变量有所改变: const app createApp(App) app.config.globalProp…...
1.2 数据模型 数据库系统概论
目录 1.2.1 两类数据模型 1.2.2 概念模型 1.信息世界中的基本概念 (1)实体 (2)属性 (3)码 (4)实体型 (5)实体集 (6)联系 2.…...
C#中openFileDialog 对话框不在最顶层,TopMost的异常情况
重点!!!若 当前窗体this的TopMost是false,可以设置为true,这样打开的对话框就是最顶层 /// <summary> /// 设置窗体TopMost,缺点和其他程序ide有冲突。例如VS有断点的调试会卡死 /// </summary&g…...
信息安全与阿里云等保三级方案实践总结
信息安全在当今数字化时代变得至关重要,企业和组织需要采取有效措施来保护其数据和信息资产。阿里云作为中国领先的云服务提供商,提供了等保三级方案,帮助用户满足国家信息安全等级保护的要求。本文将探讨信息安全和阿里云等保三级方案的重要…...
嵌入式学习记录——线程
线程基本概念: 线程:线程是一个轻量级的进程,位于进程空间内部,一个进程中可以创建多个线程 1.线程创建: 线程独占栈空间,文本段、数据段和堆区与进程共享 2.线程调度: 与进程调度是一样的 宏观并行,微观串行 3.线程消亡: 与进程消亡是一样的 4.进程和线程…...
同步服务器操作系统公网仓库到本地 _ 统信UOS _ 麒麟KYLINOS
原文链接:同步服务器操作系统公网仓库到本地 | 统信UOS | 麒麟KYLINOS 在如今快速发展的信息技术时代,维护和更新服务器操作系统变得越来越重要。无论是为了提高安全性、增加新功能还是提升系统稳定性,同步公网源仓库到本地都是一个关键步骤。…...
【数仓】flume常见配置总结,以及示例
相关文章 【数仓】基本概念、知识普及、核心技术【数仓】数据分层概念以及相关逻辑【数仓】Hadoop软件安装及使用(集群配置)【数仓】Hadoop集群配置常用参数说明【数仓】zookeeper软件安装及集群配置【数仓】kafka软件安装及集群配置【数仓】flume软件安…...
统计信息锁定
在导入成功后我要收集下这些表的信息,结果发现好几张表都没法收集,用DBMS_STATS包显示ORA-20005:object statistics are locked (stattype ALL),用Analyze命令显示ORA-38029: 对象统计信息已锁定。 解决办法很明确&a…...
光猫改为bridge模式
注意事项: 改成桥接模式后,光猫将不再拨号上网,建议提前记录自己的宽带账号,打10010申请修改自己的宽带密码。 光猫改好桥接之后,把宽带账号和密码输入到负责拨号上网的终端设备中,完成宽带PPPOE拨号设置。…...
回溯算法01-组合(Java)
1.组合 题目描述 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1: 输入:n 4, k 2 输出: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]示例 2: 输入&#x…...
初始网络 --- 网络基础
目录 0、 前言 1、 计算机网络发展背景 1.1. 局域网(LAN) && 广域网(WAN) 2、 认识并理解协议 3、 初始网络协议 3.1. 协议分层 4、 TCP/IP 五层(或四层)模型 4.1. 简单了解TCP/IP层状体系 4.2. TCP/IP协议层状结构和计算机层状结构的关系 5、 OSI七层模型 …...
在Linux/Ubuntu/Debian中计算MD5,SHA256的方法
MD5(消息摘要算法 5)和 SHA-256(安全哈希算法 256 位)等流行的哈希算法广泛用于从任意数据生成固定大小的哈希值或校验和。 以下是这些算法及其计算方式的简要概述: MD5(消息摘要算法5)&#x…...
mybatis mysql insert 主键id为空
错误示范 java代码设置了param参数,但是sql 字段没有带上参数,例如 void insertV2(Param("historyDO") HistoryDO historyDO); <insert id"insertDuplicate" parameterType"com.test.entity.HistoryDO"keyProperty&…...
批次大小对ES写入性能影响初探
问题背景 ES使用bulk写入时每批次的大小对性能有什么影响?设置每批次多大为好? 一般来说,在Elasticsearch中,使用bulk API进行批量写入时,每批次的大小对性能有着显著的影响。具体来说,当批量请求的大小增…...
c语言十大核心用法
当然,以下是十个关于 C 语言用法的代码示例: 指针的基本用法: #include <stdio.h>int main() {int num 10;int *ptr;ptr #printf("The value of num is: %d\n", *ptr);return 0; }结构体的使用: #in…...
网页打开慢,这锅该谁背?
一、背景 工作中扯皮说不可避免且非常常见的事情. 开发与产品、开发和测试、前端和后端都会产生扯皮现象。今天要聊的一个问题就是前后端之间的扯皮问题。 网页打开太慢或者点击了某个按钮发现数据很久才显示出来,这个锅谁背? 做开发不能无凭据地胡乱甩锅, 我们…...
题目 1538: 蓝桥杯-格子位置
题目描述: 输入三个自然数N,i,j (1< i< N,1< j< N),输出在一个N*N格的棋盘中,与格子(i,j)同行、同列、同一对角线的所有格子的位置。 样例解释…...
第十三届蓝桥杯嵌入式省赛程序设计详细题解
第十三届蓝桥杯嵌入式省赛题目相对于第十二届较为简单,没有那么多串口的数据处理以及判断! 第十三届省赛主要是制作一个可由串口设置密码的密码锁。本实验中,我们将用到LED模块、按键模块、串口模块、定时器的PWM模块以及官方会提供源码的LC…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...
