带头单链表 C++实现

节点定义

带头单链表:我们只需要一个结点指针指向整个链表的第一个节点,这样我们就可以通过next指针访问整个链表内的所有节点

template<class T>
struct ListNode
{T _val;ListNode* _next;ListNode(const T &val):_val(val),_next(nullptr){}
};

 这里默认将节点的_next指针设置成nullptr

构造析构函数

 成员变量只需要Node* 的头指针即可,这里的_n用来记录整个链表中有几个节点

初始化将_head赋成nullptr 因为开始是空链表

析构:直接遍历链表中的节点,按顺序删除节点即可

template<class T>
class List
{
public:typedef ListNode<T> Node;List(){_head = nullptr;_n = 0;}~List(){Node* cur = _head;while (cur){_head = _head->_next;delete cur;cur = _head;--_n;}_head = nullptr;}private:Node* _head;size_t _n;
};

插入节点

        push_back

尾插:首先需要找到最后一个节点的地址,将新节点连到最后一个节点的_next上完成尾插

需要考虑_head 为nullptr的情况,因为 为nullptr时找尾操作会访问野指针!

void push_back(const T& val)
{Node* newnode = new Node(val);if (_head == nullptr){_head = newnode;_n++;}else{Node* cur = _head;while (cur->_next){cur = cur->_next;}cur->_next = newnode;_n++;}
}

        push_front

头插:头插不需要找尾,只需要让新节点指向原链表,头节点_head指向新节点即可

注意还需要考虑_head为nullptr的情况

void push_front(const T& val)
{Node* newnode = new Node(val);newnode->_next = _head;_head = newnode;++_n;
}

删除节点

pop_back

这里需要分情况,这里的0个节点的情况作了温柔处理,还可以直接assert暴力处理

有多个节点时,需要找到最后一个节点和最后一个的节点的前一个节点,进行删除操作,并将tailPrev的next指针赋为nullptr 

	void pop_back(){//①0个节点if (_head == nullptr){return;}//②一个节点if (_head->_next == nullptr){delete _head;_head = nullptr;--_n;return;}//③一个节点以上Node* tail = _head;Node* tailPrev = nullptr;while (tail->_next){tailPrev = tail;tail = tail->_next;}	delete tail;tail = nullptr;tailPrev->_next = nullptr;--_n;}

pop_front

头删比尾删简单的多:还是这里的空链表情况进行了温柔处理,还可以assert暴力处理

先将_head指向第二个节点,如果只有一个节点的话恰好就是nullptr,然后直接删除_head之前指向的节点 

	void pop_front(){if (_head == nullptr){return;}Node* deleteNode = _head;_head = _head->_next;delete deleteNode;deleteNode = nullptr;--_n;}

遍历节点

 根据链表的最后一个节点的next指针是空来判断走到了链表的尽头,挨个打印即可

void print()
{Node* cur = _head;while (cur){cout << cur->_val << "->";cur = cur->_next;}cout << "NULL" << endl;cout << "节点数量:" << _n << endl;
}

测试代码

void test1()
{List<int> L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);L1.print();
}void test2()
{List<int>L1;L1.push_front(10);L1.push_front(20);L1.push_front(30);L1.push_front(40);L1.print();L1.pop_back();L1.pop_back();L1.print();
}
void test3()
{List<int>L1;L1.push_front(10);L1.push_front(20);L1.push_front(30);L1.push_front(40);L1.print();L1.pop_front();L1.pop_front();L1.pop_front();L1.pop_front();L1.pop_front();L1.print();
}void test4()
{List<int>L1;L1.push_front(10);L1.push_front(20);L1.push_front(30);L1.push_front(40);L1.print();L1.pop_back();L1.pop_back();L1.pop_back();L1.pop_back();L1.pop_back();L1.pop_back();L1.print();
}

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

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

相关文章

开发组合php+mysql 人才招聘小程序源码搭建 招聘平台系统源码+详细图文搭建部署教程

随着互联网的快速发展&#xff0c;传统的招聘方式已经不能满足企业和求职者的需求。为了提高招聘效率&#xff0c;降低招聘成本&#xff0c;越来越多的人开始关注人才招聘小程序、在线招聘平台。分享一个人才招聘小程序源码及搭建&#xff0c;让招聘更加高效便捷。系统是运营级…

【算法】滑动窗口——串联所有单词的子串

今天来以“滑动窗口”的思想来详解一道比较困难的题目——串联所有单词的子串&#xff0c;有需要借鉴即可。 目录 1.题目2.下面是示例代码3.总结 1.题目 题目链接&#xff1a;LINK 这道题如果把每个字符串看成一个字母&#xff0c;就是另外一道中等难度的题目&#xff0c;即&…

2022——蓝桥杯十三届2022国赛大学B组真题

问题分析 看到这个问题的同学很容易想到用十层循环暴力计算&#xff0c;反正是道填空题&#xff0c;一直算总能算得出来的&#xff0c;还有些同学可能觉得十层循环太恐怖了&#xff0c;写成回溯更简洁一点。像下面这样 #include <bits/stdc.h> using namespace std; in…

用 Supabase CLI 进行本地开发环境搭建

文章目录 &#xff08;零&#xff09;前言&#xff08;一&#xff09;Supabase CLI&#xff08;1.1&#xff09;安装 Scoop&#xff08;1.2&#xff09;用 Scoop 安装 Supabase CLI &#xff08;二&#xff09;本地项目环境&#xff08;2.1&#xff09;初始化项目&#xff08;2…

C++ | Leetcode C++题解之第86题分隔链表

题目&#xff1a; 题解&#xff1a; class Solution { public:ListNode* partition(ListNode* head, int x) {ListNode* small new ListNode(0);ListNode* smallHead small;ListNode* large new ListNode(0);ListNode* largeHead large;while (head ! nullptr) {if (head-…

Spring STOMP-消息处理流程

一旦STOMP的接口被公布&#xff0c;Spring应用程序就成为连接客户端的STOMP代理。本节描述服务端消息处理的流程。 spring-messaging模块包含消息类应用的基础功能&#xff0c;这些功能起源于Spring Integration项目。并且&#xff0c;后来被提取整合到Spring框架&#xff0c;…

Zookeeper 注册中心:单机部署

序言 本文给大家介绍 Zookeeper 单机部署流程、 如何与 Spring 整合使用。除此之外&#xff0c;还有 Zookeeper 作为注册中心与 SpringCloud 的整合流程。 一、部署流程 官网下载 Zookeeper 安装包 解压安装包到指定目录 进入 apache-zookeeper-3.8.4-bin/conf 目录&…

目标检测——印度车辆数据集

引言 亲爱的读者们&#xff0c;您是否在寻找某个特定的数据集&#xff0c;用于研究或项目实践&#xff1f;欢迎您在评论区留言&#xff0c;或者通过公众号私信告诉我&#xff0c;您想要的数据集的类型主题。小编会竭尽全力为您寻找&#xff0c;并在找到后第一时间与您分享。 …

《C++学习笔记---初阶篇6》---string类 上

目录 1. 为什么要学习string类 1.1 C语言中的字符串 2. 标准库中的string类 2.1 string类(了解) 2.2 string类的常用接口说明 2.2.1. string类对象的常见构造 2.2.2. string类对象的容量操作 2.2.3.再次探讨reserve与resize 2.2.4.string类对象的访问及遍历操作 2.2.5…

【Spring】验证 @ServerEndpoint 的类成员变量线程安全

文章目录 前言猜想来源验证方法Controller 的情况ServerEndpoint 的情况 后记 前言 最近有 websocket 的需求。探索 ServerEndpoint 的类成员变量特点。 这里类比 Controller 讨论 ServerEndpoint 类成员变量是否线程安全。 猜想来源 网上的教程大多数都这么展示程序&#…

OBS插件--音频采集

音频采集 音频采集是一款 源 插件,类似于OBS的win-capture/game-capture&#xff0c;允许从特定应用程序捕获音频&#xff0c;而不是捕获整个系统的音频。避免了因为特定音频的采集而需要引入第三方软件&#xff0c;而且时延也非常低。 下面截图演示下操作步骤&#xff1a; 首…

简单的Python HTML 输出

1、问题背景 一名初学者在尝试将 Python 脚本输出到网页上时遇到了一些问题。他当前使用 Python 和 HTML 进行开发&#xff0c;并且遇到了以下问题&#xff1a; 担心自己的代码过于复杂&#xff0c;尤其是 WebOutput() 函数。希望通过 JavaScript 使用 HTML 模板文件更新数据。…

几个字符串函数的使用和模拟实现(2)

strcop的使用和模拟实现 strcpy函数的使用事项&#xff1a; 源字符串时不需要修改的&#xff0c;在定义前加上const 源字符串被拷贝到目标字符串上时终止字符\0也被拷贝进去 目标数组的大小要相对于源数组的大小足够大&#xff0c;并且不应该在内存中重叠 函数的返回值是一个字…

网络无线网卡无法配置正确的 dns 服务器

网络无线网卡无法配置正确的 dns 服务器--解决办法 网络无线网卡无法配置正确的 dns 服务器--解决办法 网络无线网卡无法配置正确的 dns 服务器–解决办法 建议先使用疑难反馈&#xff08;自带的&#xff09; 打开网络适配中心 之后更改适配器设置&#xff0c;在点击 wlan 属…

绿盟之旅——一段安全实习结束

去年&#xff0c;因为着急找实习&#xff0c;拿着简历就开始海投&#xff0c;当时想的是有人让我去就谢天谢地了&#xff0c;第一个约我面试的就是绿盟&#xff0c;也很顺利的通过了面试&#xff0c;当时让我选择在上海还是北京&#xff0c;我选择的是上海&#xff0c;因为学校…

【C++】set 和 map 学习及使用

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f3a5;系列专栏&#xff1a;《C语言》 《数据结构》 《C》 《Linux》 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 前言 set 和 map 是 STL 中的容器之一&#xff0c;不同于普通容器&#xff0c;它俩的查找速度极快…

开发一款相亲交友小程序

uni-app框架&#xff1a;使用Vue.js开发跨平台应用的前端框架&#xff0c;编写一套代码&#xff0c;可编译到Android、小程序等平台。 框架支持:springboot/Ssm/thinkphp/django/flask/express均支持 前端开发:vue.js 可选语言&#xff1a;pythonjavanode.jsphp均支持 运行软件…

第四届上海理工大学程序设计全国挑战赛 J.上学 题解 DFS 容斥

上学 题目描述 usst 小学里有 n 名学生&#xff0c;他们分别居住在 n 个地点&#xff0c;第 i 名学生居住在第 i 个地点&#xff0c;这些地点由 n−1 条双向道路连接&#xff0c;保证任意两个地点之间可以通过若干条双向道路抵达。学校则位于另外的第 0 个地点&#xff0c;第…

【JAVA进阶篇教学】第十三篇:Java中volatile关键字讲解

博主打算从0-1讲解下java进阶篇教学&#xff0c;今天教学第十三篇&#xff1a;volatile关键字讲解。 在 Java 中&#xff0c;volatile关键字是一种轻量级的同步机制&#xff0c;用于确保变量的可见性和禁止指令重排序。本文将详细解释volatile关键字的工作原理、可见性保证以及…

Web安全:SQL注入之布尔盲注原理+步骤+实战操作

「作者简介」&#xff1a;2022年北京冬奥会网络安全中国代表队&#xff0c;CSDN Top100&#xff0c;就职奇安信多年&#xff0c;以实战工作为基础对安全知识体系进行总结与归纳&#xff0c;著作适用于快速入门的 《网络安全自学教程》&#xff0c;内容涵盖系统安全、信息收集等…