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

news/2024/9/20 1:19:47/ 标签: c++, 开发语言

目录

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://www.ppmy.cn/news/1433437.html

相关文章

基于EasyExcel实现的动态表头工具类

基于EasyExcel实现的动态表头工具类

工具类 package net.lesscoding.utils;import cn.hutool.core.bean.BeanUtil; import com.alibaba.excel.EasyExcel; import com.google.common.collect.Lists;import javax.servlet.ServletOutputStream; import javax.servlet.http.HttpServletResponse; import java.io.Uns…
阅读更多...
【Leetcode每日一题】 穷举vs暴搜vs深搜vs回溯vs剪枝_全排列 - 全排列（难度⭐⭐）（62）

【Leetcode每日一题】 穷举vs暴搜vs深搜vs回溯vs剪枝_全排列 - 全排列（难度⭐⭐）（62）

1. 题目解析 题目链接&#xff1a;46. 全排列 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 2.算法原理 回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。当候选解被确认不是一个解&#xff08;或者至少不是最后一…
阅读更多...
IDEA上配置Maven环境

IDEA上配置Maven环境

1.选择IDEA中的Setting 2.搜索maven 3.设置IDEA使用本地安装的Maven&#xff0c;并修改配置文件路径 配置文件&#xff0c;本地仓库&#xff0c;阿里云仓库配置及路径教程 在IDEA上配置完成。
阅读更多...
1. 2XX (Success 成功状态码)

1. 2XX (Success 成功状态码)

状态码2XX表示请求被正常处理了。 &#xff08;1&#xff09;200 OK 200 OK表示客户端发来的请求被服务器端正常处理了。 &#xff08;2&#xff09;204 No Content 该状态码表示客户端发送的请求已经在服务器端正常处理了&#xff0c;但是没有返回的内容&#xff0c;响应报…
阅读更多...
AlgorithmDay20

AlgorithmDay20

day20 [!NOTE] return用作&#xff1a;return递归的上一层&#xff0c;而不一定一定是最后结果。 654.最大二叉树 又是构造二叉树&#xff0c;昨天大家刚刚做完 中序后序确定二叉树&#xff0c;今天做这个 应该会容易一些&#xff0c; 先看视频&#xff0c;好好体会一下 为什么…
阅读更多...
c++补充

c++补充

构造函数、析构函数 #include <iostream> using namespace std;// 构造函数、析构函数 // --- "构造函数"类比生活中的"出厂设置" --- // --- "析构函数"类比生活中的"销毁设置" --- // 如果我们不写这两种函数&#xff0c;编译…
阅读更多...
OpenHarmony多媒体-metadata-extractor

OpenHarmony多媒体-metadata-extractor

简介 metadata-extractor是用于从图像、视频和音频文件中提取 Exif、IPTC、XMP、ICC 和其他元数据的组件。 下载安装 ohpm install ohos/metadata-extractorOpenHarmony ohpm环境配置等更多内容&#xff0c;请参考 如何安装OpenHarmony ohpm包 。 使用说明 引入文件及代码依…
阅读更多...
深入理解Java消息中间件-消息的过滤和选择

深入理解Java消息中间件-消息的过滤和选择

在我们如今这个数据驱动的时代&#xff0c;从无数的信息中准确地过滤和选择出对我们最有价值的消息&#xff0c;是业务和技术领域中不可或缺的一个环节。本文我们将探讨消息的过滤和选择是如何实现的&#xff0c;同时简要介绍其背后的原理。 理解消息过滤和选择的重要性 首先…
阅读更多...
Maven的下载和环境变量的配置

Maven的下载和环境变量的配置

1下载 maven官网https://maven.apache.org/index.html点击Download 这个是Windows的下载版本&#xff0c;一般是最新的版本&#xff0c; 老的版本下载 以下是对应的老版本下载链接 下载好后是一个压缩包的形式 点击他进行解压到想放的文件夹中&#xff0c;&#xff08;一般不…
阅读更多...
Maven基础篇3

Maven基础篇3

Maven进阶 –分模块开发与设计 –聚合 –继承 –属性 –私服 1.分模块开发与设计 开发的时候是分包开发 一个人完成一个包即可&#xff1b; 甚至一个包需要多个人开发&#xff1b;需要对包进行拆分&#xff1b; 也就是将我们一个包的东西&#xff0c;拆分成一个工程&a…
阅读更多...
神经网络进阶学习文章（一）

神经网络进阶学习文章（一）

1.讲解YOLO有关知识 深入浅出Yolo系列之Yolov5核心基础知识完整讲解 - 知乎 (zhihu.com) 2.目标检测算法综述 目标检测算法综述 - 知乎 (zhihu.com) 3.TensorFlow详解&#xff0c;当然现在用的最多的是Pytorch框架了 谷歌大神带你十分钟看懂TensorFlow - 知乎 (zhihu.co…
阅读更多...
ROS1快速入门学习笔记 - 04创建工作环境与功能包

ROS1快速入门学习笔记 - 04创建工作环境与功能包

一、定义 工作空间(workspace)是一个存放工程开发相关文件的文件夹。 src:代码空间&#xff08;Source Space&#xff09;build: 编辑空间&#xff08;Build Space&#xff09;devel:开发空间&#xff08;Development Space&#xff09;install:安装空间&#xff08;Install …
阅读更多...
Laravel 6 - 第十六章 Artisan命令

Laravel 6 - 第十六章 Artisan命令

​ 文章目录 Laravel 6 - 第一章 简介 Laravel 6 - 第二章 项目搭建 Laravel 6 - 第三章 文件夹结构 Laravel 6 - 第四章 生命周期 Laravel 6 - 第五章 控制反转和依赖注入 Laravel 6 - 第六章 服务容器 Laravel 6 - 第七章 服务提供者 Laravel 6 - 第八章 门面 Laravel 6 - …
阅读更多...
Linux shell编程学习笔记47：lsof命令

Linux shell编程学习笔记47：lsof命令

0 前言 今天国产电脑提示磁盘空间已耗尽&#xff0c;使用用df命令检查文件系统情况&#xff0c;发现/dev/sda2已使用100%。 Linux shell编程学习笔记39&#xff1a;df命令https://blog.csdn.net/Purpleendurer/article/details/135577571于是开始清理磁盘空间。 第一步是查看…
阅读更多...
服务器防入侵的方案浅析

服务器防入侵的方案浅析

随着物联网技术和互联网技术的日益发展&#xff0c;勒索病毒、工控安全、产线作业都面领着极大的威胁。智慧互联正在成为各个行业未来的发展方向&#xff0c;智慧互联包括物联网、万物互联&#xff0c;机器与机器&#xff0c;工业控制体系&#xff0c;信息化&#xff0c;也就是…
阅读更多...
XiaodiSec day007 Learn Note 小迪安全学习笔记

XiaodiSec day007 Learn Note 小迪安全学习笔记

XiaodiSec day007 Learn Note 小迪安全学习笔记 记录得比较凌乱&#xff0c;不尽详细 07 2023.12.31 cms识别 资产泄漏&#xff0c;资产即为网站的资源&#xff0c;了解到网站使用了那种cms对信息收集很有帮助 使用工具识别cms 识别cms后可以进行代码审计&#xff0c;或…
阅读更多...
【RAG 论文】面向知识库检索进行大模型增强的框架 —— KnowledGPT

【RAG 论文】面向知识库检索进行大模型增强的框架 —— KnowledGPT

论文&#xff1a;KnowledGPT: Enhancing Large Language Models with Retrieval and Storage Access on Knowledge Bases ⭐⭐⭐⭐ 复旦肖仰华团队工作 论文速读 KnowledGPT 提出了一个通过检索知识库来增强大模型生成的 RAG 框架。 在知识库中&#xff0c;存储着三类形式的知…
阅读更多...
数据库之数据库恢复技术思维导图+大纲笔记

数据库之数据库恢复技术思维导图+大纲笔记

大纲笔记&#xff1a; 事务的基本概念 事务 定义 用户定义的一个数据库操作系列&#xff0c;这些操作要么全做&#xff0c;要么全不做&#xff0c;是一个不可分割的基本单位 语句 BEGIN TRANSACTION 开始 COMMIT 提交&#xff0c;提交事务的所有操作 ROLLBACK 回滚&#xff0c…
阅读更多...
BM25检索算法 python

BM25检索算法 python

1.简介 BM25&#xff08;Best Matching 25&#xff09;是一种经典的信息检索算法&#xff0c;是基于 TF-IDF算法的改进版本&#xff0c;旨在解决、TF-IDF算法的一些不足之处。其被广泛应用于信息检索领域的排名函数&#xff0c;用于估计文档D与用户查询Q之间的相关性。它是一种…
阅读更多...
【AngularJs】前端使用iframe预览pdf文件报错

【AngularJs】前端使用iframe预览pdf文件报错

<iframe style"width: 100%; height: 100%;" src"{{vm.previewUrl}}"></iframe> 出现报错信息&#xff1a;Cant interpolate: {{vm.previewUrl}} 在ctrl文件中信任该文件就可以了 vm.trustUrl $sce.trustAsResourceUrl(vm.previewUrl);//信任…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站