【C++】list的模拟实现

📢博客主页：https://blog.csdn.net/2301_779549673
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由 JohnKi 原创，首发于 CSDN🙉
📢未来很长，值得我们全力奔赴更美好的生活✨

文章目录

📢一、前言

在 C++ 编程中，模拟实现标准模板库（STL）中的

list

具有重要意义和广泛的应用场景。

list

作为一种常用的数据结构，其独特的特性使得在许多情况下能够提供高效和灵活的操作。

模拟实现

list

有助于深入理解其内部工作原理。通过亲手编写代码来模拟 list 的各种功能，如节点的创建、插入、删除、遍历等，可以清晰地掌握数据在链表中的存储和流动方式，这对于提升对数据结构的理解和编程能力至关重要。

在实际应用中，list 常用于需要频繁进行插入和删除操作的场景。例如，当处理动态变化的数据集合，且插入和删除操作的位置不固定时，

list

的优势就凸显出来。相比其他线性数据结构如数组和向量，

list

不需要移动大量元素来进行插入和删除，时间复杂度通常为常数级别。

此外，

list

还适用于需要高效合并和分割数据的情况。由于其节点之间的链接关系相对独立，合并和分割操作可以相对轻松地实现。

总之，无论是为了深入学习数据结构和算法，还是为了在实际编程中灵活运用 list 来解决复杂问题，模拟实现

list

都具有不可忽视的价值。

🏳️‍🌈二、准备工作

list

中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

因为

list

是一个个节点组成的，所以对于他的每一个节点也要进行定义，代码如下：

template<classT>structlist_node{
    T _data;
    list_node<T>* _next;
    list_node<T>* _prev;// 缺省构造函数list_node(const T& data =T()):_data(data),_next(nullptr),_prev(nullptr){}};

🏳️‍🌈三、节点结构体的实现

在模拟实现 C++ 中的

list

时，节点结构体的设计是基础。节点结构体通常包含以下几个部分：
首先是数据域，用于存储实际的数据。其数据类型可以根据具体需求灵活设定，比如整数、字符串、自定义对象等。

其次是前后指针域，分别指向链表中的前一个节点和后一个节点。这两个指针使得链表能够实现双向遍历和操作。

为了方便节点的创建和初始化，还会为节点结构体提供构造函数。构造函数可以接受数据作为参数，用于初始化数据域，并将前后指针域初始化为空指针，以确保节点在创建时处于正确的初始状态。

以下是一个简单的节点结构体示例代码：

template<typenameT>structListNode{
    T data;
    ListNode* prev;
    ListNode* next;ListNode(const T& val):data(val),prev(nullptr),next(nullptr){}};

这样的节点结构体设计为后续实现

list

的各种复杂功能提供了基本的单元支持。

🏳️‍🌈四、迭代器结构体的实现

此处，大家可暂时将迭代器理解成一个指针，该指针指向Iist中的某个节点

我们可以通过下图理解其中的联系

❤️4.1 迭代器的模板参数

在模拟实现 list 的迭代器结构体中，通常会有多个模板参数。比如

<class T, class Ref, class Ptr>

，其中 T 表示迭代器所指向的节点中存储的数据类型。Ref 用于定义解引用操作返回的引用类型，以便在需要修改节点数据时能够进行修改。Ptr 则用于指定指针类型，例如在返回节点数据的指针时使用。

🧡4.2 迭代器的成员变量

迭代器结构体的成员变量通常是一个指向节点的指针，比如

Node* _pnode

。这个指针用于在链表中定位当前迭代器所指向的节点，从而实现对链表的遍历和操作。

💛4.3 重载的运算符

4.3.1 解引用运算符
解引用运算符

operator*

用于获取迭代器所指向节点的数据。通常的实现方式是返回节点中的数据，例如

Ref operator*() { return _pnode->_val; }

，通过这种方式，可以像使用指针一样获取节点中的数据。

4.3.2 指针操作运算符
指针操作运算符

operator->

用于获取节点数据的地址。常见的实现是

Ptr operator->() { return &(_pnode->_val); }

，使得可以通过迭代器像使用指针一样访问节点数据的成员。

4.3.3 不等与相等判断运算符
不等运算符

operator!=

用于比较两个迭代器是否指向不同的节点，通常通过比较它们的指针值来实现，如

bool operator!=(const self& it) const { return _pnode!= it._pnode; }

。相等运算符 operator== 则相反，用于判断两个迭代器是否指向相同的节点。

下面是整个迭代器部分的代码：

// 迭代器  -  结构体// 利用迭代器实现STL数据库template<classT,classRef,classPtr>structlist_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;
        Node* _node;// 构造函数list_iterator(Node* node):_node(node){}

        Ref operator*(){return _node->_data;}// 返回的是指针
        Ptr operator->(){return&_node->_data;}

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

        Self&operator--(){
            _node = _node->_prev;return*this;}booloperator!=(const Self & s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};

🏳️‍🌈五、list 链表类的实现

首先针对链表类，我们需要定义一个头节点和一个用来计算长度的变量

private:
        Node* _head;
        size_t _size;

❤️5.1 成员变量说明头节点指针

在 list 链表类中，通常会有一个成员变量用于存储头节点的指针。这个头节点指针是整个链表的起始点，通过它可以访问到链表中的其他节点。

template<typenameT>classList{
    ListNode<T>* head;};

🧡5.2 构造函数

• 默认构造函数会初始化头节点指针为空，表明链表初始时为空。

// 构造函数voidempty_init(){// 哨兵位
            _head =newNode(T());
            _head->_next = _head;
            _head->_prev = _head;
            _size =0;}

• 拷贝构造函数用于创建一个与现有链表完全相同的新链表。

list(const list <T>& it){empty_init();for(auto& e : it){push_back(e);}}

• 析构函数用于释放链表中所有节点所占用的内存资源，以防止内存泄漏。在遍历链表时，依次删除每个节点。

~list(){clear();delete _head;
            _head =nullptr;}voidclear(){auto it =begin();while(it !=end()){
                it =erase(it);}}

• 头插函数创建一个新节点，并将其置于链表头部。

voidinsert(iterator pos,const T& x){
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode =newNode(x);

            newnode->_next = cur;
            newnode->_prev = prev;

            prev->_next = newnode;
            cur->_prev = newnode;}voidpush_back(const T& x){//Node* newnode = new Node(x);//Node* tail = _head->_prev;//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;//++_size;insert(end(), x);}

• 头删函数删除链表头部的节点。

        iterator erase(iterator pos){assert(pos !=end());
            Node* prev = pos._node->_prev;
            Node* next = pos._node->_next;

            prev->_next = next;
            next->_prev = prev;delete pos._node;return next;}voidpop_back(){erase(end()--);}

• 赋值将一个链表的内容赋给另一个链表。

        list<T>&operator=(list<T> it){swap(it);return*this;}

🏳️‍🌈六、注意事项

• 迭代器失效 在模拟实现 list 的过程中，需要特别注意迭代器失效的问题。当进行插入、删除等操作时，可能会导致原本指向特定节点的迭代器失效。例如，在插入节点后，原本指向插入位置之后节点的迭代器可能不再有效。为了处理迭代器失效，可以在进行可能导致失效的操作后，重新获取迭代器或者对相关迭代器进行更新。
• 构造函数细节 在构造函数中，尤其是按数量和类型构造以及迭代器构造，要确保正确地分配和初始化节点。对于内存分配，要处理可能的异常情况，以保证程序的健壮性。同时，要注意初始化节点之间的指针关系，避免出现悬空指针或循环引用等错误。
• 析构函数要点 析构函数用于释放链表中所有节点占用的内存。在实现时，要确保从链表头部开始，依次正确地删除每个节点，并将相关的指针置为空，以防止内存泄漏和野指针的出现。同时，要处理链表为空的特殊情况，避免出现非法的内存访问操作。

🏳️‍🌈整体代码

#pragmaonce#include<iostream>#include<assert.h>usingnamespace std;namespace bit
{// 单个节点template<classT>structlist_node{
        T _data;
        list_node<T>* _next;
        list_node<T>* _prev;// 缺省构造函数list_node(const T& data =T()):_data(data),_next(nullptr),_prev(nullptr){}};// 迭代器  -  结构体// 利用迭代器实现STL数据库template<classT,classRef,classPtr>structlist_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;
        Node* _node;// 构造函数list_iterator(Node* node):_node(node){}

        Ref operator*(){return _node->_data;}// 返回的是指针
        Ptr operator->(){return&_node->_data;}

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

        Self&operator--(){
            _node = _node->_prev;return*this;}booloperator!=(const Self & s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};/*template<class T>
    struct list_const_iterator
    {
        typedef list_node<T> Node;
        typedef list_const_iterator<T> Self;
        Node* _node;

         构造函数
        list_const_iterator(Node* node)
            :_node(node)
        {}

        const T& operator*()
        {
            return _node->_data;
        }

         返回的是指针
        const T* operator->()
        {
            return &_node->_data;
        }

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

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

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

        bool operator==(const Self& s) const
        {
            return _node == s._node;
        }
    };*/// 链表template<classT>classlist{// 重命名typedef list_node<T> Node;public:/*typedef list_iterator<T> iterator;
        typedef list_const_iterator<T> const_iterator;*/// 利用模板实现两个类（高度相似的两个类）typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<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;}voidswap(list<T>& lt){
            std::swap(_head, lt._head);
            std::swap(_size, lt._size);}voidempty_init(){// 哨兵位
            _head =newNode(T());
            _head->_next = _head;
            _head->_prev = _head;
            _size =0;}list(){empty_init();}// lt2(lt1) 拷贝构造list(const list <T>& it){empty_init();for(auto& e : it){push_back(e);}}// lt1 = lt3
        list<T>&operator=(list<T> it){swap(it);return*this;}~list(){clear();delete _head;
            _head =nullptr;}voidclear(){auto it =begin();while(it !=end()){
                it =erase(it);}}voidinsert(iterator pos,const T& x){
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode =newNode(x);

            newnode->_next = cur;
            newnode->_prev = prev;

            prev->_next = newnode;
            cur->_prev = newnode;}voidpush_back(const T& x){//Node* newnode = new Node(x);//Node* tail = _head->_prev;//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;//++_size;insert(end(), x);}voidpush_front(const T& x){insert(begin(), x);}

        iterator erase(iterator pos){assert(pos !=end());
            Node* prev = pos._node->_prev;
            Node* next = pos._node->_next;

            prev->_next = next;
            next->_prev = prev;delete pos._node;return next;}voidpop_back(){erase(end()--);}voidpop_front(){earse(begin());}
        size_t size()const{return _size;}boolempty()const{return _size ==0;}private:
        Node* _head;
        size_t _size;};structAA{int _a1 =1;int _a2 =1;};template<classContainer>voidprint_container(const Container& con){// const iterator ->迭代器本身不能修改// const_iterator -> 指向内容不能修改// 如果没有typename，编译器可能会错误地将Container::const_iterator解释为一个静态成员变量或成员函数，而不是一个类型。typenameContainer::const_iterator it = con.begin();while(it != con.end()){
            cout <<*it <<" ";++it;}
        cout << endl;for(auto e : con){
            cout << e <<" ";;}
        cout << endl;}voidtest_list1(){
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);

        list<int>::iterator it = lt.begin();while(it != lt.end()){
            cout <<*it <<" ";++it;}
        cout << endl;

        list<AA> lta;
        lta.push_back(AA());
        lta.push_back(AA());
        lta.push_back(AA());
        lta.push_back(AA());
        list<AA>::iterator ita = lta.begin();while(ita != lta.end()){//cout << (*ita)._a1 << ":" << (*ita)._a2 << endl;// 特殊处理，本来应该是两个->才合理，为了可读性，省略了一个->
            cout << ita->_a1 <<":"<< ita->_a2 << endl;
            cout << ita.operator->()->_a1 <<":"<< ita.operator->()->_a2 << endl;++ita;}
        cout << endl;}voidtest_list2(){
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);

        list<int>::iterator it = lt.begin(); 
        lt.insert(it,10);*it +=100;print_container(lt);
        cout << endl;// 删除所有的偶数
        it = lt.begin();while(it != lt.end()){if(*it %2==0){
                it = lt.erase(it);}else++it;}print_container(lt);}voidtest_list3(){
        list<int> lt1;
        lt1.push_back(1);
        lt1.push_back(2);
        lt1.push_back(3);
        lt1.push_back(4);

        list<int>lt2(lt1);print_container(lt1);print_container(lt2);

        list<int> lt3;
        lt3.push_back(9);
        lt3.push_back(9);
        lt3.push_back(9);
        lt3.push_back(9);

        lt1 = lt3;print_container(lt1);print_container(lt3);}}

👥总结

模拟实现 list 是一项具有挑战性但富有价值的工作。要点包括：

• 深入理解双向链表的结构和特性，确保节点结构体、迭代器结构体以及链表类的设计准确无误。
• 精心实现各种构造函数，满足不同的初始化需求，同时注意内存管理和指针操作的正确性。
• 准确编写基本操作函数，如插入、删除、遍历等，保证链表的功能完整且高效。
• 时刻关注迭代器失效问题，在相关操作后进行合理的处理和更新。

本篇博文对 list的模拟实现 做了一个较为详细的介绍，不知道对你有没有帮助呢

觉得博主写得还不错的三连支持下吧！会继续努力的~