P1【知识点】【数据结构】【链表LinkedList】C++版

链表是一种逻辑上连续,内存上分散的线性表数据结构,是用一组任意的空间(可以连续,也可以不连续)来存放数据元素。每个数据元素成为一个”结点“,每个结点由数据域和指针域组成。

  1. 访问元素(Access)O(N)
  2. 搜索元素(Search)O(N)
  3. 插入元素(Insert)O(1)
  4. 删除元素(Delete)O(1)

特点:写的快读的慢(应用于写多读少)

最基本的链表如图所示:

以下参考:数据结构:链表及其C++实现 - 菜鸡刘 - 博客园 (cnblogs.com)

插入操作:

假如需要在C结点后面插入F结点,只需要使C结点的指针指向F,F结点的指针指向结点D即可,如图所示

需要注意的是,在具体实现的时候,需要先暂存C结点的指针,先将其赋值给F结点指针,然后再将F结点的地址赋值给C结点的指针,否则会丢失D结点的地址,链表就会在此处断开。

删除操作:

假如需要删除D结点,则直接让C结点的指针指向E结点即可,如图所示

具体代码实现:

本文利用C++面向对象的特性与模板实现了一个链表类,并实现了插入、删除、查找、拷贝构造、拷贝赋值等基本操作。

结点类实现:
// 链表节点类
template<typename T>
class node
{
public:node() : next(nullptr){} // 这是构造函数node(T val) : data(val), next(nullptr) {} // 这是有参构造
private:T data;node* next;friend class list<T>; //同时在node类中将链表类list声明为友元,便于访问node的成员。
};
链表类声明:

链表类list的声明如下,主要实现了以下操作。list类包含两个成员属性head_ptr和length,前者是链表的头指针,后者储存链表的长度。

template<typename T>
class list
{
public:list(); // 构造函数list(const list<T>& l); // 拷贝构造list<T>& operator= (const list<T>& l); // 拷贝赋值 void insert_node(int index, T val); // 在index处插入结点void del_node(int index); // 删除index处结点T get_node(int index); // 获取index处结点值int find(int value); // 查找值value,找到返回index,找不到返回-1int get_length(); // 获取链表长度void push_back(T val); // 在链表尾部插入数据~list(); // 析构函数private:node<T>* head_ptr; // 链表头指针int length; // 链表长度
};
插入实现:

对于插入操作,本文将其分为了三种情况

  • 超出索引,抛出异常
  • 插在空链表的头
  • 一般情况

// 在index处插入结点
template<typename T>
void list<T>::insert_node(int index, T val)
{if((index > this->length)) // 超过索引,最多可以插到当前结点的下一个结点,否则就是超过索引{throw runtime_error("index out of this list`s range");}else if((this->head_ptr == nullptr) && (index == 0)) // 插在空链表的头{this->head_ptr = new node<T>;this->head_ptr->next = nullptr;this->head_ptr->data = val;this->length++;} else // 一般情况{node<T>* p1 = this->head_ptr;node<T>* p2 = new node<T>;for(int i = 0; i < index - 1; i++){p1 = p1->next;}p2->data = val;p2->next = p1->next;p1->next = p2;this->length++;}
}
删除实现:

删除操作需要注意的是,每个结点都是通过new在堆区申请的内存,因此删除节点需要手动释放其内存。

// 删除index处结点
template<typename T>
void list<T>::del_node(int index)
{node<T>* p1 = this->head_ptr;node<T>* p2 = nullptr;for(int i = 0; i < index - 1; i++){p1 = p1->next;}p2 = p1->next->next;delete p1->next;p1->next = p2;this->length--;
}
索引实现:
// 获取index处结点值
template<typename T>
T list<T>::get_node(int index)
{if(index > this->length - 1) // 超过索引{throw runtime_error("index out of this list`s range");}node<T>* p1 = this->head_ptr;for(int i = 0; i < index; i++){p1 = p1->next;}return p1->data;
}
查找实现:
// 查找值value,找到返回index,找不到返回-1
template<typename T>
int list<T>::find(int value)
{node<T>* p1 = this->head_ptr;for(int i = 0; i < this->length; i++){if(p1->data == value){return i;}p1 = p1->next;}return -1;
}
析构实现:

析构函数需要做的就是释放链表每个节点的内存。

// 析构函数
template<typename T>
list<T>::~list()
{// 清空链表node<T>* p1 = this->head_ptr;node<T>* p2 = p1->next;while(p2 != nullptr){delete p1;p1 = p2;p2 = p2->next;}delete p1;this->length = 0;this->head_ptr = nullptr;} 

力扣练习:

【203】移除链表元素

【206】反转链表

视频来源:【数据结构2】链表Linkedlist_哔哩哔哩_bilibili 

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

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

相关文章

保护共享资源的方法(互斥锁)

我最近开了几个专栏&#xff0c;诚信互三&#xff01; > |||《算法专栏》&#xff1a;&#xff1a;刷题教程来自网站《代码随想录》。||| > |||《C专栏》&#xff1a;&#xff1a;记录我学习C的经历&#xff0c;看完你一定会有收获。||| > |||《Linux专栏》&#xff1…

工厂模式(简单工厂模式+工厂模式)

工厂模式的目的就是将对象的创建过程隐藏起来&#xff0c;从而达到很高的灵活性&#xff0c;工厂模式分为三类&#xff1a; 简单工厂模式工厂方法模式抽象工厂模式 在没有工厂模式的时候就是&#xff0c;客户需要一辆马车&#xff0c;需要客户亲自去创建一辆马车&#xff0c;…

向上调整建堆与向下调整建堆的时间复杂度 AND TopK问题

目录 前言建堆的时间复杂度TOPK问题总结 前言 本篇旨在介绍使用向上调整建堆与向下调整建堆的时间复杂度. 以及topk问题 博客主页: 酷酷学!!! 感谢关注~ 建堆的时间复杂度 堆排序是一种优于冒泡排序的算法, 那么在进行堆排序之前, 我们需要先创建堆, 为什么说堆排序的是优于…

2023年数维杯国际大学生数学建模挑战赛D题洗衣房清洁计算解题全过程论文及程序

2023年数维杯国际大学生数学建模挑战赛 D题 洗衣房清洁计算 原题再现&#xff1a; 洗衣房清洁是人们每天都要做的事情。洗衣粉的去污作用来源于一些表面活性剂。它们可以增加水的渗透性&#xff0c;并利用分子间静电排斥机制去除污垢颗粒。由于表面活性剂分子的存在&#xff…

Ubuntu 20/22 安装 Jenkins

1. 使用 apt 命令安装 Java Jenkins 作为一个 Java 应用程序&#xff0c;要求 Java 8 及更高版本&#xff0c;检查系统上是否安装了 Java。 sudo apt install -y openjdk-17-jre-headless安装完成后&#xff0c;再次验证 Java 是否已安装 java --version2. 通过官方存储库安…

15:00面试,15:08出来,面试问的有点变态。。。。

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天…

第10章 数据聚合与分组运算

以下内容参考自https://github.com/iamseancheney/python_for_data_analysis_2nd_chinese_version/blob/master/%E7%AC%AC05%E7%AB%A0%20pandas%E5%85%A5%E9%97%A8.md 《利用Python进行数据分析第2版》 用以学习和记录。 对数据集进行分组并对各组应用一个函数&#xff08;无论…

Dubbo生态之dubbo功能

1.Dubbo生态功能的思考 dubbo具有哪些功能呢&#xff1f;我们要根据dubbo的架构和本质是用来干什么的来思考? 首先对于分布式微服务&#xff0c;假设我们有两个服务A和B&#xff0c;并且都是集群部署的。那么按照我们正常的流程应该是启动两个微服务项目&#xff08;启动时应该…

vscode添加代办相关插件,提高开发效率

这里写目录标题 前言插件添加添加TODO Highlight安装TODO Highlight在项目中自定义需要高亮显示的关键字 TODO Tree安装TODO Tree插件 单行注释快捷键 前言 在前端开发中&#xff0c;我们经常会遇到一些未完成、有问题或需要修复的部分&#xff0c;但又暂时未完成或未确定如何处…

C++初阶学习第十弹——探索STL奥秘(五)——深入讲解vector的迭代器失效问题

vector&#xff08;上&#xff09;&#xff1a;C初阶学习第八弹——探索STL奥秘&#xff08;三&#xff09;——深入刨析vector的使用-CSDN博客 vector&#xff08;中&#xff09;&#xff1a;C初阶学习第九弹——探索STL奥秘&#xff08;四&#xff09;——vector的深层挖掘和…

MYSQL 集群

1.集群目的:负载均衡 解决高并发 高可用HA 服务可用性 远程灾备 数据有效性 类型:M M-S M-S-S M-M M-M-S-S 原理:在主库把数据更改(DDL DML DCL&#xff09;记录到二进制日志中。 备库I/O线程将主库上的日志复制到自己的中继日志中。 备库SQL线程读取中继日志…

Mongodb介绍及springboot集成增删改查

文章目录 1. MongoDB相关概念1.1 业务应用场景1.2 MongoDB简介1.3 体系结构1.4 数据模型1.5 MongoDB的特点 2. docker安装mongodb3. springboot集成3.1 文件结构3.2 增删改查3.2.1 增加insert3.2.2 保存save3.2.3 更新update3.2.4 查询3.2.5 删除 1. MongoDB相关概念 1.1 业务…

【学习笔记】Windows GDI绘图(五)图形路径GraphicsPath详解(上)

文章目录 图形路径GraphicsPath填充模式FillMode构造函数GraphicsPath()GraphicsPath(FillMode)GraphicsPath(Point[],Byte[])和GraphicsPath(PointF[], Byte[])GraphicsPath(Point[], Byte[], FillMode)和GraphicsPath(PointF[], Byte[], FillMode)PathPointType 属性FillMode…

jsp连接数据库

1.打开命令框进入数据库 打开eclipse创建需要连接的项目 粘贴驱动程序 查看驱动器 使用sql的包 int代表个 conlm代表列名 <%page import"java.sql.ResultSet"%> <%page import"java.sql.Statement"%> <%page import"java.sql.Connect…

关于如何创建一个可配置的 SpringBoot Web 项目的全局异常处理

前情概要 这个问题其实困扰了我一周时间&#xff0c;一周都在 Google 上旅游&#xff0c;我要如何动态的设置 RestControllerAdvice 里面的 basePackages 以及 baseClasses 的值呢&#xff1f;经过一周的时间寻求无果之后打算决定放弃的我终于找到了一些关键的线索。 当然在此…

html5 笔记01

01 表单类型和属性 input的type属性 单行文本框: typetext 电子邮箱 : typeemail 地址路径 : type url 定义用于输入数字的字段: typenumber 手机号码: typetel 搜索框 : typesearch 定义颜色选择器 : typecolor 滑块控件 : typerange 定义日期 :typedate 定义输入时间的控件…

CR80清洁卡都能用在什么地方?

CR80清洁卡&#xff08;也被称为ISO 7810 ID-1清洁卡&#xff09;的规格确实使其在各种需要读取磁条或接触式智能卡的设备中都有广泛的用途。这些设备包括但不限于&#xff1a; ATM自动终端机&#xff1a;当ATM机的磁条读卡器出现故障或读卡不灵敏时&#xff0c;可以使用CR80清…

第三期【数据库主题文档上传激励活动】已开启!快来上传文档赢奖励

2023年9月、11月&#xff0c;墨天轮社区相继举办了第一期与第二期【数据库主题文档上传激励活动】&#xff0c;众多用户积极参与、上传了大量优质的数据库主题干货文档&#xff0c;在记录经验的同时也为其他从业者带来了参考帮助&#xff0c;这正实现了“乐知乐享、共同成长”的…

以及Spring中为什么会出现IOC容器?@Autowired和@Resource注解?

以及Spring中为什么会出现IOC容器&#xff1f;Autowired和Resource注解&#xff1f; IOC容器发展史 没有IOC容器之前 首先说一下在Spring之前&#xff0c;我们的程序里面是没有IOC容器的&#xff0c;这个时候我们如果想要得到一个事先已经定义的对象该怎么得到呢&#xff1f;…

STM32自己从零开始实操02:输入部分原理图

一、触摸按键 1.1指路 项目需求&#xff1a; 4个触摸按键&#xff0c;主控芯片 TTP224N-BSBN&#xff08;嘉立创&#xff0c;封装 TSSOP-16&#xff09;&#xff0c;接入到 STM32 的 PE0&#xff0c;PE1&#xff0c;PE2&#xff0c;PE3。 1.2走路 1.2.1数据手册重要信息提…