【C++】手撕list（list的模拟实现）

目录

01.节点

02.迭代器

迭代器运算符重载

03.list类

（1）构造与析构

（2）迭代器相关

（3）容量相关

（4）访问操作

（5）插入删除

我们在学习数据结构的时候，学过一个非常好用的结构，叫做带头双向循环链表，它不仅遍历非常地灵活方便，而且插入和删除操作的效率很高，弥补了单链表相较于数组的缺点。我们今天要讲的list模版底层就是带头双向循环链表。

01.节点

既然是链表，链表是由一个个节点组成的，每一个节点都需要独立开辟空间，节点之间通过指针进行连接，而双向循环链表的节点内部包含两个指针，一个指向下一个节点，一个指向上一个节点。

    // List的节点类template<class T>struct ListNode{ListNode(const T& val = T()): _prev(nullptr), _next(bullptr), _val(val){}ListNode<T>* _prev;ListNode<T>* _next;T _val;};

这里用struct定义类是因为，struct定义的类内部成员默认为公有，而class定义的类内部成员默认私有，节点的参数需要支持外部访问，所以这里用struct定义。

02.迭代器

在vector中，迭代器通常是一个原生指针，因为vector内部是使用连续的内存块来存储数据的，所以可以直接用指针来表示迭代器。

但是list使用双向链表存储数据，其迭代器就不能只是指针了，而需要存储更多的数据，并且迭代器的加减等运算操作也需要重载。

迭代器运算符重载

1.*解引用：

使用 *iter 访问迭代器时，operator*() 返回的是 _node->_val 的引用，可以直接对返回值进行操作，就好像它是一个对象一样。

2.->成员访问：

使用迭代器的 -> 操作符时，实际上是先调用 operator->() 返回 _node->_val 的地址，然后对返回的地址进行成员访问。

3.迭代器++、--：

分为前置++与后置++：

前置++：

  • 调用前置++时，先将 _node 指向下一个节点。
  • 返回的是递增后的对象的引用。
  • 返回的引用允许对递增后的对象进行连续操作。

后置++：

  • 调用后置++时，先创建一个当前对象的副本 temp。
  • 将 _node 指向下一个节点。
  • 返回的是之前的对象的副本 temp。
  • 返回的副本 temp 保留了递增前的状态，允许在返回后继续使用递增前的对象。

--与++同理，只不过--是指向前一个节点，将“ _node = _node->_next”改成“ _node = _node->_prev”即可。

4.==运算符：

判断两个迭代器是否相等就是判断他们的节点是否相等。

//List的迭代器类template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(Node* node = nullptr): _node(node){}ListIterator(const Self& l): *this(l){}T& operator*(){return _node->_val;}T* operator->(){return &(operator*());}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self temp(*this);_node = _node->_next;return temp;}Self& operator--(){_node = _node->_prev;return *this;}Self& operator--(int){Self temp(*this);_node = _node->_prev;return temp;}bool operator!=(const Self& l){return _node != l._node;}bool operator==(const Self& l){return _node == l._node;}private:Node* _node;};

03.list类

（1）构造与析构

在创建一个list实例时，首先需要创建一个头节点，不存储任何有效数据。用于简化链表的操作，以及提供一种统一的操作方式。

    private:void CreateHead(){_head = new node;_head->_prev = _head;_head->_next = _head;}Node* _head;};

list的构造分为无参构造、实例化构造、迭代器构造、拷贝构造等等。

无参构造：

只需要创建一个头节点，CreateHead()已经完成了初始化，就不需要默认构造了

        list(){CreateHead();}

 实例化构造：

实例化n个value元素，在head节点后面插入n个value元素。

        list(int n, const T& value = T()){CreateHead();for (int i = 0; i < n; ++i) {push_back(value);}}

 迭代器构造：

利用迭代器对拷贝源进行遍历，在head节点后面不断插入数据。

        template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last) {push_back(*first);++first;}}

拷贝构造：

复制一个拷贝源副本，然后赋值给目标容器。 

        list(const list<T>& l){CreateHead();//_head = l->_head;//浅拷贝list temp<T>(l.begin(), l.end());this->swap(temp);}

重载=：

创建赋值源的副本并作为返回值返回。 

        list<T>& operator=(const list<T> l){list temp<T>(l.begin(), l.end());return *temp;}

析构：

由于list内部数据存储地址是分散的，析构时要对每一个节点单独进行空间释放，这里我们可以用头删的方法，头节点保留，依次删除头节点指向的首元素节点，并改变指向，这样就可以遍历容器达到析构效果。

        void clear(){Node cur = _head;while (cur != _head){_head->_next = cur->_next;delete cur;cur = _head->_next;}_head->_next = _head->_prev = _head;}~list(){clear();delete _head;_head = nullptr;}

（2）迭代器相关

我们需要定义定义 begin() 和 end() 函数，用于返回指向链表开头和结尾的迭代器。

begin() 函数返回的迭代器指向链表的第一个有效节点，即头节点 _head 的下一个节点 _head->_next。因为头节点 _head 不存储有效数据，而是作为链表的辅助节点。

end() 函数返回的迭代器指向链表的结尾，即头节点 _head。因为在list中，尾节点指向的下一个节点就是头节点 _head。

        // List 迭代器iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}

（3）容量相关

size()函数：

要想知道list容器中的数据个数，就需要遍历全部节点，因为是循环链表，遍历到_head头节点时即表示遍历完毕。

        size_t size()const{size_t count = 0;Node* cur = _head->_next;while (cur != _head){++count;cur = cur->_next;}return count;}

empty()函数：

容器为空的判定条件是：头结点的两个指针都指向自己，即为初始化状态。

        bool empty()const{return _head->_next == _head;}

（4）访问操作

front() 和 back() 函数，分别用于获取链表的第一个元素和最后一个元素。这是直接获取元素的值，而 begin() 和 end() 函数是获取地址。

        T& front(){return _head->_next->_val;}const T& front()const{return _head->_next->_val;}T& back(){return _head->_prev->_val;}const T& back()const{return _head->_prev->_val;}

注意：想要对const类型进行函数重载，函数后面必须加上const关键字，才能构成重载。

（5）插入删除

插入和删除分为头插、头删；尾插、尾删；在pos位置前插入和删除。

由于前两种可以看做是第三种的特殊情况，所以只需要具体实现第三种即可。

在pos位置前插入：

首先需要创建一个新节点newNode，newNode 的 _prev 指向 rightNode 的 _prev ，newNode 的 _next 指向 leftNode 的 _next

 再将 rightNode 的 _prev 、leftNode 的 _next 都指向 newNode ，就完成了插入操作，插入完成后需要返回插入位置的迭代器。

        // 在pos位置前插入值为val的节点iterator insert(iterator pos, const T & val){Node* _pnewnode = new Node;Node* cur = pos._node;_pnewnode->_val = val;_pnewnode->_next = cur;_pnewnode->_prev = cur->_prev;cur->_prev = _pnewnode;return iterator(_pnewnode);}

删除pos位置的节点：

首先将leftNode 的 _next 指向 rightNode ，rightNode 的 _prev 指向 leftNode。

 然后对pos位置节点进行空间释放。

        // 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){Node* pDel = pos._node;Node* pRet = pos._node->_next;pDel->_prev->_next = pDel->_next;pRet->_prev = pDel->_prev;delete pDel;return iterator(pRet);}

头插头删就是在首元素节点前插入节点；尾插尾删就是删除头结点_prev指向的节点，是上述插入删除操作的实例：

        // List 插入和删除void push_back(const T& val) { insert(end(), val);}void pop_back() { erase(--end());}void push_front(const T& val) {insert(begin(), val);}void pop_front(){erase(begin());}

最后附上完整代码：

#pragma once
#include<iostream>
using namespace std;namespace My
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()): _prev(nullptr), _next(bullptr), _val(val){}ListNode<T>* _prev;ListNode<T>* _next;T _val;};//List的迭代器类template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(Node* node = nullptr): _node(node){}ListIterator(const Self& l): *this(l){}T& operator*(){return _node->_val;}T* operator->(){return &(operator*());}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self temp(*this);_node = _node->_next;return temp;}Self& operator--(){_node = _node->_prev;return *this;}Self& operator--(int){Self temp(*this);_node = _node->_prev;return temp;}bool operator!=(const Self& l){return _node != l._node;}bool operator==(const Self& l){return _node == l._node;}private:Node* _node;};//list类template<class T>class list{typedef ListNode<T> Node;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:///// List的构造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();for (int i = 0; i < n; ++i) {push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last) {push_back(*first);++first;}}list(const list<T>& l){CreateHead();//_head = l->_head;//浅拷贝list temp<T>(l.begin(), l.end());this->swap(temp);}list<T>& operator=(const list<T> l){list temp<T>(l.begin(), l.end());return *temp;}~list(){clear();delete _head;_head = nullptr;}///// List 迭代器iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}///// List 容量相关size_t size()const{size_t count = 0;Node* cur = _head->_next;while (cur != _head){++count;cur = cur->_next;}return count;}bool empty()const{return _head->_next == _head;}// List 元素访问操作T& front(){return _head->_next->_val;}const T& front()const{return _head->_next->_val;}T& back(){return _head->_prev->_val;}const T& back()const{return _head->_prev->_val;}// List 插入和删除void push_back(const T& val) { insert(end(), val);}void pop_back() { erase(--end());}void push_front(const T& val) {insert(begin(), val);}void pop_front(){erase(begin());}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T & val){Node* _pnewnode = new Node;Node* cur = pos._node;_pnewnode->_val = val;_pnewnode->_next = cur;_pnewnode->_prev = cur->_prev;cur->_prev = _pnewnode;return iterator(_pnewnode);}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){Node* pDel = pos._node;Node* pRet = pos._node->_next;pDel->_prev->_next = pDel->_next;pRet->_prev = pDel->_prev;delete pDel;return iterator(pRet);}void clear(){Node cur = _head;while (cur != _head){_head->_next = cur->_next;delete cur;cur = _head->_next;}_head->_next = _head->_prev = _head;}void swap(list<T>& l){std::swap(_head, l._head);}private:void CreateHead(){_head = new node;_head->_prev = _head;_head->_next = _head;}Node* _head;};
};

那么以上就是list的模拟实现了，欢迎在评论区留言，觉得这篇博客对你有帮助的可以点赞关注收藏支持一波喔~😉

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

【OceanBase诊断调优 】—— 如何快速定位SQL问题

【OceanBase诊断调优 】—— 如何快速定位SQL问题

作者简介&#xff1a; 花名&#xff1a;洪波&#xff0c;OceanBase 数据库解决方案架构师&#xff0c;目前负责 OceanBase 数据库在各大型互联网公司及企事业单位的落地与技术指导&#xff0c;曾就职于互联网大厂和金融科技公司&#xff0c;主导过多项数据库升级、迁移、国产化…
阅读更多...
台灯太亮会影响视力吗？分享五款防近视护眼台灯

台灯太亮会影响视力吗？分享五款防近视护眼台灯

台灯作为一盏实用的桌面照明灯具&#xff0c;是孩子学习过程中必不可少的“好伴侣”&#xff0c;不过大多数家长只关注到台灯的光线是否够亮&#xff0c;认为只要亮度足够就可以了&#xff0c;那么台灯太亮会影响视力吗&#xff1f; 答案是会的。首先太暗的环境肯定是不够支撑孩…
阅读更多...
用友NC Cloud importhttpscer接口任意文件上传漏洞

用友NC Cloud importhttpscer接口任意文件上传漏洞

声明 本文仅用于技术交流&#xff0c;请勿用于非法用途 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;文章作者不为此承担任何责任。 一、漏洞描述 用友NC Cloud的importhttpscer接口如果存在任意文件上传…
阅读更多...
【pycharm】调试模式中四个常用按钮介绍

【pycharm】调试模式中四个常用按钮介绍

【pycharm】调试模式中四个常用按钮介绍 在 PyCharm 的调试模式中&#xff0c;有四个常用的按钮&#xff0c;它们的功能如下&#xff1a; Step Over (F8)&#xff1a;单步执行&#xff0c;但在遇到函数调用时&#xff0c;不会进入函数内部&#xff0c;而是将整个函数作为一步执…
阅读更多...
【八股】计算机网络篇

【八股】计算机网络篇

网络模型 应用层【HTTP&#x1f449;报文/消息】 传输层【TCP或UDP&#x1f449;段&#x1f449;MSS】网络层【IP、寻址和路由&#x1f449;MTU】 ①IP&#xff08;Internet Protocol&#xff0c;网际协议&#xff09;主要作用是定义数据包的格式、对数据包进行路由和寻址&…
阅读更多...
计算机网络物理层思维导图+大纲笔记

计算机网络物理层思维导图+大纲笔记

大纲笔记&#xff1a; 物理层的基本概念 解决如何在连接各种计算机的传输媒体上传输数据比特流&#xff0c;而不是具体的传输媒体 主要任务 确定与传输媒体接口有关的一些特性 机械特性 电气特性 功能特性 规程特性信道上传送的信号 基带信号 来自信源的信号&#xff0c;直接表…
阅读更多...
CentOS-7部署mysql、clickhouse并通过普罗米修斯、grafna监控告警

CentOS-7部署mysql、clickhouse并通过普罗米修斯、grafna监控告警

一、准备工作 1、系统环境 所用镜像&#xff1a;CentOS-7-x86_64-DVD-2009.iso 2、涉及安装包 3、克隆4台虚拟机 用途IP主机名Prometneus服务器192.168.15.129master被监控服务器1192.168.15.133node1mysql、clickhouse、grafana服务器192.168.15.134node2被监控服务器219…
阅读更多...
3（第二章，数据处理伦理）

3（第二章，数据处理伦理）

目录 概述 基本概念 数据伦理准则 1、尊重他人 2、行善原则 3、公正 4、增加个人自主权 数据隐私法背后的原则 GDPR准则 PIPEDA FTC 违背伦理进行数据处理的风险 违背伦理进行数据处理的行为 概述 数据伦理是社会责任问题而⾮法律问题。 伦理是建立在是否观念上的…
阅读更多...
阿里云服务器ECS经济型e实例和u1实例哪个好？

阿里云服务器ECS经济型e实例和u1实例哪个好？

阿里云服务器ECS经济型e实例和通用算力型u1实例有什么区别&#xff1f;如何选择&#xff1f;ECS经济型e实例是共享型云服务器&#xff0c;通用算力型u实例是企业级独享型云服务器&#xff0c;e实例性价比高&#xff0c;现在2核2G3M带宽一年99元&#xff0c;云服务器u1价格相对要…
阅读更多...
2024，2025（专家期）

2024，2025（专家期）

2024&#xff0c;2025&#xff08;专家期&#xff09; 目录概述需求&#xff1a; 设计思路实现思路分析1.另一种的方式&#xff1a; 2.按照自己的职业规划进行发展 参考资料和推荐阅读 Survive by day and develop by night. talk for import biz , show your perfect code,ful…
阅读更多...
vue3去掉el-table底部白色边框

vue3去掉el-table底部白色边框

加入下面这一行代码就行了&#xff0c;我用的是less :deep(.el-table__inner-wrapper:before) {background: none;}效果图
阅读更多...
400电话多少钱

400电话多少钱

400电话是指客户联系企业所用的号码&#xff0c;统一为以400开头的7位数字&#xff0c;被称为“企业热线”。这种数字式电话凭借其好记、省钱、全国通等特性&#xff0c;早已成为企业营销推广的重要工具。那么&#xff0c;400电话的费用是多少呢&#xff1f; 首先&#xff0c;我…
阅读更多...
Python蜘蛛侠

Python蜘蛛侠

目录 写在前面 蜘蛛侠 编写代码 代码分析 更多精彩 写在后面 写在前面 本期小编给大家推荐一个酷酷的Python蜘蛛侠&#xff0c;一起来看看叭~ 蜘蛛侠 蜘蛛侠&#xff08;Spider-Man&#xff09;是美国漫威漫画宇宙中的一位标志性人物&#xff0c;由传奇创作者斯坦李与艺…
阅读更多...
Linux——文件与目录

Linux——文件与目录

一、Linux的目录 1、Linux的树状目录结构 可以在终端中输入命令 ls / 列出 / 下面的子目录&#xff1a; 对于不同的Linux发布版本&#xff0c;/ 下的子目录可能不同。 2、对于这些目录的解释 / 在Linux中&#xff0c;所有文件和目录都挂载在根目录下&#xff0c;根目录用…
阅读更多...
51-44 Generating Long Videos of Dynamic Scenes，生成动态场景长视频

51-44 Generating Long Videos of Dynamic Scenes，生成动态场景长视频

22年6月&#xff0c;NVIDIA, UC Berkeley联合发布Generating Long Videos of Dynamic Scenes&#xff0c;这也是Sora技术报告中提及的32篇论文之一。 作者的主要贡献是提出了分层生成器架构Hierarchical Generator Architecture&#xff0c;该架构采用了巨大的时间感受野和创新…
阅读更多...
量子密钥分发系统的设计与实现(四)：量子密钥的产生过程分析

量子密钥分发系统的设计与实现(四)：量子密钥的产生过程分析

在之前的文章中&#xff0c;我们讨论了QKD系统的光路系统&#xff0c;我们对整个系统最基础的部分有了初步的了解&#xff0c;从本文开始&#xff0c;我们就要往上层出发了&#xff0c;一起探讨下光电信号如何变成最终的密钥。 1.关于QKD后处理 在光路子系统中&#xff0c;Alic…
阅读更多...
【大数据】LSM树，专为海量数据读写而生的数据结构

【大数据】LSM树，专为海量数据读写而生的数据结构

目录 1.什么是LSM树&#xff1f; 2.LSM树的落地实现 1.什么是LSM树&#xff1f; LSM树&#xff08;Log-Structured Merge Tree&#xff09;是一种专门针对大量写操作做了优化的数据存储结构&#xff0c;尤其适用于现代大规模数据处理系统&#xff0c;如NoSQL数据库&#xff…
阅读更多...
电商API采集的优势、使用场景，如何实时获取主流电商API数据

电商API采集的优势、使用场景，如何实时获取主流电商API数据

电商API采集简介 随着电子商务行业的快速发展&#xff0c;电商API采集成为了许多电商平台和企业的重要工具。API&#xff08;应用程序接口&#xff09;是不同软件系统之间进行数据交互的协议&#xff0c;通过API采集&#xff0c;电商平台可以方便地获取其他电商平台的商品信息…
阅读更多...
如何在Facebook上发布广告？

如何在Facebook上发布广告？

在广告管理工具中创建广告 创建广告系列和广告组。在广告名称文本框中输入描述性名称。选择代表您业务的Facebook 公共主页和Instagram 帐户。 所有广告都必须具有关联的Facebook 公共主页。选择广告格式。 选择素材。 您可能还会看到其他选项&#xff0c;具体取决于您先前所做…
阅读更多...
coredns部署

coredns部署

coredns部署 coredns部署 一&#xff1a;coredns-rbac.yaml apiVersion: v1 kind: ServiceAccount metadata:name: corednsnamespace: kube-systemlabels:kubernetes.io/cluster-service: "true"addonmanager.kubernetes.io/mode: Reconcile --- apiVersion: rbac…
阅读更多...
最新文章

Copyright @ 2022~2023