【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的模拟实现了，欢迎在评论区留言，觉得这篇博客对你有帮助的可以点赞关注收藏支持一波喔~😉

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

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

相关文章

StartAI智能绘图软件出现“缺少Python运行库”怎么办？

StartAI智能绘图软件出现“缺少Python运行库”怎么办？

StartAI做为一款国产AI界的新秀&#xff0c;是一款贴合AIGC新手的智能绘图软件。新手安装遇见“缺少Python运行库”怎么办”&#xff1f;小编一招搞定~ 解决方法&#xff1a;手动下载【resource文件】&#xff0c;将文件添加到安装目录下。 点击链接进行手动下载噢~ 确保 Star…
阅读更多...
图像处理之模板匹配（C++）

图像处理之模板匹配（C++）

图像处理之模板匹配&#xff08;C&#xff09; 文章目录 图像处理之模板匹配&#xff08;C&#xff09;前言一、基于灰度的模板匹配1.原理2.代码实现3.结果展示 总结 前言 模板匹配的算法包括基于灰度的匹配、基于特征的匹配、基于组件的匹配、基于相关性的匹配以及局部变形匹…
阅读更多...
Spring-IOC之组件扫描

Spring-IOC之组件扫描

版本 Spring Framework 6.0.9​ 1. 前言 通过自动扫描&#xff0c;Spring 会自动从扫描指定的包及其子包下的所有类&#xff0c;并根据类上的特定注解将该类装配到容器中&#xff0c;而无需在 XML 配置文件或 Java 配置类中逐一声明每一个 Bean。 支持的注解 Spring 支持一系…
阅读更多...
Mysql索引详解（索引分类）

Mysql索引详解（索引分类）

文章目录 概述索引对查询速度的影响索引的优缺点索引类型一级索引和二级索引的区别MySQL 回表联合索引&#xff08;最左前缀原则主键索引和唯一索引的区别BTree索引和Hash索引的区别 覆盖索引索引下推加索引能够提升查询效率原因MySQL 索引结构采用 B树原因索引失效的场景MySQL…
阅读更多...
JAVASE基础语法（异常、常用类）

JAVASE基础语法（异常、常用类）

一、异常 1.1 什么是异常 异常就是指不正常。是指代码在运行过程中可能发生错误&#xff0c;导致程序无法正常运行。 package com.atguigu.exception;public class TestException {public static void main(String[] args) {int[] arr {1,2,3,4,5};System.out.println(&quo…
阅读更多...
前端css中filter(滤镜)的使用

前端css中filter(滤镜)的使用

前端css中filter的使用 一、前言二、补充内容说明三、模糊&#xff08;一&#xff09;、模糊效果&#xff0c;源码1&#xff08;二&#xff09;、源码1运行效果1.视频演示2.截图演示 四、阴影&#xff08;一&#xff09;、阴影效果&#xff0c;源码2&#xff08;二&#xff09;…
阅读更多...
Linux文件系统与日志

Linux文件系统与日志

一、inode和block 文件数据包括元信息与实际数据&#xff0c;文件存储在硬盘上&#xff0c;硬盘最小存储单位是扇区&#xff0c;每个扇区存储512字节 1.block(块)&#xff1a;文件系统中用于存储文件实际数据的最小单位&#xff0c;由文件系统进行分配和管理&#xff0c;并通…
阅读更多...
JavaSE内部类

JavaSE内部类

内部类概述 1.内部类的基础 内部类的分类&#xff1a;实例化内部类&#xff0c;静态内部类&#xff0c;局部内部类和匿名内部类 public class OutClass {// 成员位置定义&#xff1a;未被static修饰 --->实例内部类public class InnerClass1{}// 成员位置定义&#xff1a;被…
阅读更多...
01、创建型-单例模式--只有一个实例

01、创建型-单例模式--只有一个实例

文章目录 前言一、基本介绍1.1 什么是单例模式1.2 为什么要用单例模式1.3 应用场景1.4 单例优缺点 二、单例模式的实现方式2.1 饿汉式单例2.1.1 静态变量方式2.1.2 静态代码块 2.2 懒汉式单例2.2.1 懒汉式单例2.2.2 懒汉式优化①-线程安全2.2.2 懒汉式优化②-双重检查锁2.2.3 懒…
阅读更多...
ROS1快速入门学习笔记 - 04创建工作环境与功能包

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

一、定义 工作空间(workspace)是一个存放工程开发相关文件的文件夹。 src:代码空间&#xff08;Source Space&#xff09;build: 编辑空间&#xff08;Build Space&#xff09;devel:开发空间&#xff08;Development Space&#xff09;install:安装空间&#xff08;Install …
阅读更多...
深入理解Linux文件系统于日志分析

深入理解Linux文件系统于日志分析

目录 一.Inode 和 block 概述 ​编辑 1.inode 的内容 &#xff08;1&#xff09;Inode 包含文件的元信息 &#xff08;2&#xff09;用 stat 命令可以查看某个文件的 inode 信息 &#xff08;3&#xff09; Linux系统文件三个主要的时间属性 &#xff08;4&#xff09;目…
阅读更多...
CentOS 系统的优缺点

CentOS 系统的优缺点

CentOS &#xff08;社区企业操作系统的缩写&#xff09;是一个基于红帽企业 Linux (RHEL)的免费开源发行版&#xff0c; 旨在为服务器和工作站提供稳定、可靠和安全的平台。 不应将其与CentOS Stream 混淆&#xff0c;后者是即将发布的 RHEL 版本的上游开发平台。 CentOS Li…
阅读更多...
第67天：APP攻防-Frida反证书抓包移动安全系统资产提取评估扫描

第67天：APP攻防-Frida反证书抓包移动安全系统资产提取评估扫描

思维导图 案例一&#xff1a;内在-资产提取-AppinfoScanne AppinfoScanner 一款适用于以 HW 行动/红队/渗透测试团队为场景的移动端(Android、iOS、WEB、H5、静态网站)信息收集扫描工具&#xff0c;可以帮助渗透测试工程师、攻击队成员、红队成员快速收集到移动端或者静态 WEB …
阅读更多...
机器学习之sklearn基础教程

机器学习之sklearn基础教程

ChatGPT Scikit-learn (简称sklearn) 是一个非常受欢迎的Python机器学习库。它包含了从数据预处理到训练模型的各种工具。下面是一个关于如何使用sklearn进行机器学习的基础教程。 1. 安装和导入sklearn库 首先&#xff0c;你需要安装sklearn库&#xff08;如果你还没有安装的…
阅读更多...
使用写入这类接口后，文件指针fp是否会偏移？

使用写入这类接口后，文件指针fp是否会偏移？

以fprintf为例&#xff1a; 在使用 fprintf 函数写入数据时&#xff0c;文件指针 fp 会自动进行偏移&#xff0c;以确保数据被写入到文件的正确位置。 每次调用 fprintf 函数都会将数据写入文件&#xff0c;并且文件指针会在写入完成后自动移动到写入的末尾&#xff0c;以便下…
阅读更多...
56-FMC连接器电路设计

56-FMC连接器电路设计

视频链接 FMC连接器电路设计01_哔哩哔哩_bilibili FMC连接器电路设计 1、FMC简介 1.1、FMC介绍 FMC&#xff08;FPGA Mezzanine Card&#xff09;是一个应用范围、适应环境范围和市场领域范围都很广的通用模块。FMC连接器连接了由FPGA提供的引脚和FMC子板的I/O接口。最新的…
阅读更多...
NLP方面知识

NLP方面知识

NLP方面知识 一 基础1.Tokenizer1.1 分词粒度&#xff1a;1.2 大模型的分词粒度1.3 各路语言模型中的tokenizer 2.Embedding layer2.1 理解Embedding矩阵 一 基础 1.Tokenizer tokenizer总体上做三件事情&#xff1a; 分词。tokenizer将字符串分为一些sub-word token string&…
阅读更多...
ISSCC论文详解：“闪电”数模混合存内计算，适应transformer和CNNs架构

ISSCC论文详解：“闪电”数模混合存内计算，适应transformer和CNNs架构

本文聚焦存内计算前沿论文ISSCC 2024 34.3&#xff0c;总结归纳其创新点&#xff0c;并对与之相似的创新点方案进行归纳拓展。 一、文章基本信息 ISSCC 2024 34.4&#xff1a;《A 22nm 64kb Lightning-Like Hybrid Computing-in-Memory Macro with a Compressed Adder Tree a…
阅读更多...
实验七 智能手机互联网程序设计（微信程序方向）实验报告

实验七 智能手机互联网程序设计（微信程序方向）实验报告

请编写一个用户登录界面&#xff0c;提示输入账号和密码进行登录&#xff0c;要求在输入后登陆框显示为绿色&#xff1b; 二、实验步骤与结果&#xff08;给出对应的代码或运行结果截图&#xff09; index.wxml <view class"content"> <view class"a…
阅读更多...
Linux——界面和用户

Linux——界面和用户

本篇文章所写的都是基于centos 7 64位&#xff08;通过虚拟机运行&#xff09;。 一、Linux的界面 Linux操作系统提供了多种用户界面&#xff0c;主要分为图形用户界面&#xff08;GUI&#xff09;和命令行界面&#xff08;CLI&#xff09;。 1、图形用户界面(GUI)&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023