C++ list链表模拟实现

目录

前言:

模拟实现:

迭代器的实现:

list类功能函数实现:

 初始化成空函数(empty_init):

构造函数:

 拷贝构造函数:

尾插(push_back):

插入(insert):

删除(erase):

 尾删(pop_back):

头插(push_front):

头删(pop_front):

 清理(clear):

 交换(swap):

赋值重载:

析构:

代码


前言:

  在学习完list的基本功能后,我自己模拟实现了一个list,具备一些常用的基本功能,这篇博客用来分享并记录,方便后续复习。

模拟实现:

因为list中可以存很多种类型,比如int,char,float,等,还可能是自定义类型,所以我打算使用类模板,先把简单的节点弄成类模板:

接下来就是list的类模板:

迭代器的实现:

  这里迭代器的模拟实现不能像vector一样简单的使用原生指针,因为链表的地址不是连续的,我们在进行原生指针的++或者--操作时,是无法实现访问下一个或者上一个元素的,那该怎样实现简单的对迭代器++或者--就能实现访问下一个或者上一个元素呢?

  这里有一个巧妙地方法就是借助类,没错,我们将原生指针放入一个名为Listiterator的类里面,然后在这个类中,使用运算符重载,重载++,--,*,->等运算符,就能像库里面一样使用迭代器了。

 上图的Ref和Ptr模板分别是传引用和传指针,用于应对const 迭代器的使用 ,保证const迭代器可以修改迭代器,但不能修改该迭代器指向的内容。接下来开始在这个类中重载各种运算符:

这几个运算符重载都很简单,应该都能看懂,接下来进入list类模板中,就行list的功能函数实现:

list类功能函数实现:

先来几个简单但又很重要的函数实现:

 初始化成空函数(empty_init):

构造函数:

有了上面这个函数后,构造函数就简单了,直接复用即可:

 拷贝构造函数:

尾插(push_back):

插入(insert):

删除(erase):

 尾删(pop_back):

头插(push_front):

头删(pop_front):

 清理(clear):

 交换(swap):

赋值重载:

 此处传值传参的妙处:

list1=iist2,进入函数此时lt是list2的拷贝,因为swap是成员函数,所以有一个隐含的this指针,此时只需传参lt就可以完成lt和list1交换,间接完成对list1的赋值,同时没有改变list2,只是改变了lt,而lt出作用域后就会消失。

析构:

代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
namespace sxk
{   
	template<class T>
	struct ListNode
	{
		ListNode<T>* next;//下一个节点的地址
		ListNode<T>* prev;//上一个节点的地址
		T val;//数据

		ListNode(const T& x = T())//节点的构造函数
			:next(nullptr)
			, prev(nullptr)
			, val(x)
		{}
	};
	template<class T,class Ref,class Ptr>
	struct Listiterator
	{
		typedef ListNode<T> Node;
		typedef Listiterator<T, Ref, Ptr> Self;
		typedef Listiterator<T, T&, T*> iterator;
		typedef Listiterator<T, const T&, const T*> const_iterator;

		Node* _node;

		Listiterator(Node* node)//迭代器的构造函数
			:_node(node)
		{}

		Ref operator*()
		{
			return _node->val;
		}

		Ptr operator->()
		{
			return &_node->val;
		}

		Self& operator++()
		{
			_node = _node->next;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp(*this);
			_node = _node->next;
			return tmp;
		}

		Self& operator--()
		{
			_node = _node->prev;
			return *this;
		}

		Self operator--(int)
		{
			Self tmp(*this);
			_node = _node->prev;
			return tmp;
		}

		bool operator==(const Self& it)
		{
			return _node == it._node;
		}

		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}
	};
	template<class T>
	class list
	{
	public:
		typedef ListNode<T> Node;
		typedef Listiterator<T, T&, T*> iterator;
		typedef Listiterator<T, const T&, const T*> const_iterator;
		iterator begin()
		{
			return _head->next;
		}

		iterator end()
		{
			return _head;
		}

		const_iterator begin()const
		{
			return _head->next;
		}

		const_iterator end()const
		{
			return _head;
		}

		size_t size()
		{
			return _size;
		}

		bool empty()
		{
			return _size == 0;
		}

		void empty_init()
		{
			_head = new Node;//new出头节点
			_head->next = _head;//头节点下一个指向自己
			_head->prev = _head;//头节点上一个指向自己

			_size = 0;
		}


		list()//构造函数
		{
			empty_init();
		}

		list(const list<T>& lt)//拷贝构造函数
		{
			empty_init();//先初始化成只有一个头节点
			for (auto& x : lt)
			{
				push_back(x);//直接尾插即可
			}
		}

		list<T>& operator=(const list<T> lt)//lt是赋值类的拷贝
		{
			swap(lt);//交换lt和this,可以完成赋值并不影响赋值类
			return *this;
		}

		void swap(const list<T>& lt)
		{
			std::swap(_head, lt._head);//直接调用库里的swap交换两个成员变量即可
			std::swap(_size, lt._size);
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())//遍历删除
			{
				it = erase(it);//更新it,防止erase后迭代器失效
				it++;
			}
		}

		~list()
		{
			clear();//先清理,只保留一个头节点
			delete _head;//释放头节点
			_head = nullptr;
		}

		void push_back(const T& x)
		{
			Node* newnode = new Node;//new出新节点
			newnode->val = x;//给新节点赋值
			Node* tail = _head->prev;//记录尾节点

			tail->next = newnode;//尾节点的下一个指向新节点
			newnode->next = _head;//新节点的next指向头节点
			newnode->prev = tail;//新节点的prev指向之前旧的尾节点
			_head->prev = newnode;//头节点的prev指向新节点
			_size++;
		}

		void push_front()
		{
			insert(begin());
		}

		void pop_back()
		{
			erase(--end());//直接复用erase,注意end指向的是头节点,所以要--
		}

		void pop_front()
		{
			erase(begin());
		}

		void insert(iterator pos, const T& x)//在pos位置前插入x
		{
			Node* newnode = new Node;//new出新节点
			newnode->val = x;//给新节点赋值
			Node* cur = pos._node;//记录当前pos位置
			Node* prev = cur->prev;//记录pos前一个

			prev->next = newnode;//pos前一个节点的next指向新节点
			newnode->next = cur;//新节点的next指向pos节点
			newnode->prev = prev;//新节点的prev指向pos前一个节点
			cur->prev = newnode;//pos的prev指向新节点
			_size++;
		}

		iterator erase(iterator pos)//删除pos位置的值
		{
			Node* cur = pos._node;//记录pos位置的节点
			Node* prev = cur->prev;//记录pos的前一个节点
			Node* next = cur->next;//记录pos的下一个节点

			prev->next = cur->next;//pos的前一个节点的next指向pos的下一个节点
			next->prev = prev;//pos的下一个节点的prev指向pos的前一个节点
			delete cur;//释放pos位置的节点
			cur = nullptr;//置为空
			_size--;
			return iterator(next);//防止erase后迭代器失效,更新迭代器
		}

	private:
		Node* _head;
		size_t _size;
	};

	void Print_List(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << (*it) << " ";
			it++;
		}
		cout << endl;
	}
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【触想智能】工业一体机和普通电脑的区别是什么?

工业一体机和普通电脑的区别是什么&#xff0c;工业一体机可以当普通电脑一样使用吗? 要想了解工业一体机和普通电脑的区别是什么?我们首先来看看工业一体机是什么&#xff0c;它跟普通电脑有哪些相似的地方?下面小编就为大家来详细介绍一下。 在工作原理上&#xff0c;工业…

GFS分布式 文件系统

一、GFS的概念 文件存储分为nfs、lvm、raid 对象存储分为GFS、CEPH、fastDFS&#xff08;分布式文件存储&#xff09;NAS OSS S3 switch OSS 属于阿里云 通过URL 链接 S3属于亚马逊通过URL链接 1.1 GFS简介 开源的分布式文件系统&#xff0c;由存储服务器、客户端…

Pillow教程11:九宫格切图的实现方法(安排!!!)

---------------Pillow教程集合--------------- Python项目18&#xff1a;使用Pillow模块&#xff0c;随机生成4位数的图片验证码 Python教程93&#xff1a;初识Pillow模块&#xff08;创建Image对象查看属性图片的保存与缩放&#xff09; Pillow教程02&#xff1a;图片的裁…

xv6源码分析 003

xv6源码分析 003 在开始今晚的内容之前我先纠正以下昨天的一个错误 struct cmd {int type; };代表的是在sh.c开头就定义的宏常量&#xff0c;系统调用号是通过汇编代码来传入的。修改之后的内容如下&#xff1a; 好啦&#xff0c;我们继续昨晚的内容吧。 在sh.c 的 main函数中…

大屏可视化展示平台解决方案(word原件获取)

1.系统概述 1.1.需求分析 1.2.重难点分析 1.3.重难点解决措施 2.系统架构设计 2.1.系统架构图 2.2.关键技术 2.3.接口及要求 3.系统功能设计 3.1.功能清单列表 3.2.数据源管理 3.3.数据集管理 3.4.视图管理 3.5.仪表盘管理 3.6.移动端设计 3.1.系统权限设计 3.2.数据查询过程设…

如何使用vscode启动Flask并实现无公网IP远程访问内网服务

文章目录 1. 安装部署Flask2. 安装Cpolar内网穿透3. 配置Flask的web界面公网访问地址4. 公网远程访问Flask的web界面 本篇文章主要讲解如何在本地安装Flask&#xff0c;以及如何将其web界面发布到公网进行远程访问。 Flask是目前十分流行的web框架&#xff0c;采用Python编程语…

linux网络服务学习(5):iscsi

1.什么是iscsi 1.1 scsi SCSI是一种I/O技术&#xff0c;规范了一种并行的I/O总线和相关协议&#xff08;scsi协议&#xff09;。 SCSI总线通过SCSI控制器&#xff08;target&#xff09;来和硬盘之类的设备&#xff08;scsi设备&#xff09;进行通信&#xff0c;访问的客户端…

图形学物体拾取:CPU VS GPU

一、CPU – raycaster 射线包围盒是一种常用的方法&#xff0c;在 CPU 中进行拾取&#xff0c;性能较好&#xff0c;但是精度较差。当拾取频率不高时&#xff0c;可以考虑使用像素级精度的帧缓冲拾取Framebuffer Picker.射线投射涉及将射线投射到场景中并检查对象和射线之间的…

K8s技术全景:架构、应用与优化

一、介绍 Kubernetes的历史和演进 Kubernetes&#xff08;简称K8s&#xff09;是一个开源的容器编排系统&#xff0c;用于自动化应用程序的部署、扩展和管理。它最初是由Google内部的Borg系统启发并设计的&#xff0c;于2014年作为开源项目首次亮相。 初始阶段 Kubernetes的诞生…

网站想使用https安全协议,必须要安装ssl证书吗?

ssl证书作为保护网站数据传输安全的重要工具&#xff0c;被广泛应用于网站的安全加密通信中。很多人在初次接触ssl证书时&#xff0c;有一个常见的疑问&#xff1a;网站使用https协议必须要ssl证书吗&#xff1f; 答案是肯定的。   HTTPS是一种通过计算机网络进行安全通信的…

计算机网络 网络命令的使用

一、实验内容 1.PING网络命令的实验 ping 127.0.0.1(内部回环测试)ping 本主机的IP地址ping 默认网关地址ping远端目的地的IP地址ping localhostping域名 2.其他网络命令实验 命令用途ipconfig/all 显示当前系统网络配置&#xff0c;包括IP地址、子网掩码、默认网关等trace…

Unity MySql安装部署与Unity连接

1.前言 最近项目用到MySql&#xff0c;记录一下安装部署过程。 数据量过大或者需要管理用户数据的时候用mysql的话数据结构比较清晰明了&#xff0c;便于管理。 2.安装MySql Unity版本&#xff1a;2019.4.16 MySql版本&#xff1a;8.2.0 下载地址&#xff1a;MySql 下载…

LLM - 大语言模型(LLM) 的 应用技术

欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://blog.csdn.net/caroline_wendy/article/details/137503579 大语言模型(LLM) 的应用技术范围非常广泛,即: LangChain:开发框架,专为大型语言模型设计,以提高开发人工智能应用的效率,允许开发者将语言模…

Day17_学点JavaEE_转发、重定向、Get、POST、乱码问题总结

1 转发 转发&#xff1a;一般查询了数据之后&#xff0c;转发到一个jsp页面进行展示 req.setAttribute("list", list); req.getRequestDispatcher("student_list.jsp").forward(req, resp);2 重定向 重定向&#xff1a;一般添加、删除、修改之后重定向到…

整理的微信小程序日历(单选/多选/筛选)

一、日历横向多选&#xff0c;支持单日、双日、三日、工作日等选择 效果图 wxml文件 <view class"calendar"><view class"section"><view class"title flex-box"><button bindtap"past">上一页</button&…

AWS入门实践-在EC2上部署Wordpress网站

在AWS EC2上部署WordPress涉及到几个步骤&#xff0c;包括启动EC2实例、配置数据库、安装WordPress等。以下是详细的步骤和相应的命令脚本 第一步: 启动 EC2 实例 登录 AWS 控制台,进入 EC2 服务启动一个新的 EC2 实例,选择 Amazon Linux 2 AMI选择合适的实例类型(例如 t2.mi…

⼿机客户端画K线图流程

优质博文&#xff1a;IT-BLOG-CN 一、什么是K线流程 K线图是一种用于展示金融市场价格走势的图表。它通常由四个关键价格点组成&#xff0c;即开盘价、收盘价、最高价和最低价。K线图的流程可以简单概括为以下几个步骤&#xff1a; 【1】收集数据&#xff1a; 首先&#xff0c…

GPT-4对多模态大模型在多模态预训练、 理解生成上的启发

传统人工智能 模型往往依赖大量有标签数据的监督训练,而且一个模型一般只能解决一个任务,仅适用于单一场景, 这使得人工智能的研发和应用成本高,场景适应能力弱,难以规模化应用。 常见的多模态任务大致可以分为两类: 多模态理解任务,如视频 分类、视觉问答、跨模态检索、指代…

数据库——实验6 视图的创建与使用

1. 视图的定义 视图是根据需要以一个表或多个表为基础&#xff0c;选择满足一定条件的行或列数据的静态定义。它是一种逻辑对象&#xff0c;是一种虚拟表。视图并不生成行或列的永久副本&#xff0c;并不占用存储空 间&#xff0c;也就是说&#xff0c;视图就是保存在数据库中…

LLMs之FreeGPT35:FreeGPT35的简介、安装和使用方法、案例应用之详细攻略

LLMs之FreeGPT35&#xff1a;FreeGPT35的简介、安装和使用方法、案例应用之详细攻略 目录 FreeGPT35的简介 FreeGPT35的安装和使用方法 1、部署和启动服务 Node 2、使用 Docker 部署服务&#xff1a; 运行 Docker 容器以部署服务 使用 Docker Compose 进行更方便的容器化…