0
0

【C++】List模拟实现

💞💞 前言

hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹
在这里插入图片描述

💥个人主页：大耳朵土土垚的博客
💥 所属专栏：C++入门至进阶
这里将会不定期更新有关C++的内容，希望大家多多点赞关注收藏💖💖

目录

一、什么是List

C++中的list是一种双向链表（doubly linked list）的实现。它是C++标准库中的一种容器，可以存储一系列元素，并且允许在任意位置插入、删除和访问元素。对于双向链表有疑问的可以点击查看数据结构——带头双向循环链表详解

二、Lits模拟实现

2.1 List完整实现代码

#pragmaonceusingnamespace std;#include<iostream>#include<assert.h>namespace tutu
{//1.list节点template<classT>structListNode{//默认构造structListNode(const T& val =T()):_node(val),_prev(NULL),_next(NULL){}//成员函数
        T _node;
        ListNode<T>* _prev;
        ListNode<T>* _next;};//2.迭代器类template<classT,classRef,classPtr>structList_Iterator{typedefstructListNode<T> Node;typedef List_Iterator<T,Ref,Ptr> self;
        Node* _pnode;//构造函数List_Iterator(Node* node):_pnode(node){}
        Ref operator*()const{return _pnode->_node;}

        Ptr operator->()const{return&_pnode->_node;}//前置++
        self&operator++(){
            _pnode =  _pnode->_next;return*this;}//后置++
        self&operator++(int){
            self tmp(*this);
            _pnode = _pnode->_next;return tmp;}//前置--
        self&operator--(){
            _pnode = _pnode->_prev;return*this;}//后置--
        self&operator--(int){
            self tmp(*this);
            _pnode = _pnode->_prev;return tmp;}booloperator!=(const self& pnode){return!(_pnode == pnode._pnode);}booloperator==(const self& pnode){return _pnode == pnode._pnode;}};const迭代器//template<class T>//struct Const_List_Iterator//{//    typedef struct ListNode<T> Node;//    typedef Const_List_Iterator<T> self;//    Node* _pnode;//    //构造函数//    Const_List_Iterator(Node* node)//        :_pnode(node)//    {//    }//    const T& operator*()const//    {//        return _pnode->_node;//    }//    const T* operator->()const//    {//        return &_pnode->node;//    }//    //前置++//    self& operator++()//    {//        _pnode = _pnode->_next;//        return *this;//    }//    //后置++//    self& operator++(int)//    {//        self tmp(*this);//        _pnode = _pnode->_next;//        return tmp;//    }//    //前置--//    self& operator--()//    {//        _pnode = _pnode->_prev;//        return *this;//    }//    //后置--//    self& operator--(int)//    {//        self tmp(*this);//        _pnode = _pnode->_prev;//        return tmp;//    }//    bool operator!=(const self& pnode)const//    {//        return !(_pnode == pnode._pnode);//    }//    bool operator==(const self& pnode)const//    {//        return _pnode == pnode._pnode;//    }//};//3.list类template<classT>classList{public:typedefstructListNode<T> Node;typedefstructListNode<T>* pNode;//迭代器typedef List_Iterator<T,T&,T*> iterator;//const 迭代器，数据不可被修改，但可++,判断是否相等typedef List_Iterator<T,const T&,const T*> const_iterator;

        

        iterator begin(){returniterator(_listhead->_next);}
        iterator end(){returniterator(_listhead);}

        const_iterator begin()const{returnconst_iterator(_listhead->_next);}
        const_iterator end()const{returnconst_iterator(_listhead);}voidEmptyInit(){
            _listhead =newNode();
            _listhead->_prev = _listhead;
            _listhead->_next = _listhead;}//默认构造List(){EmptyInit();}//拷贝构造List(List<T>& lt){EmptyInit();for(auto& e : lt){push_back(e);}}//initializer_listList(initializer_list<T> il){EmptyInit();for(constauto& e : il){push_back(e);}}//赋值运算符重载
        List<T>&operator=(List<T> lt){swap(_listhead,lt._listhead);return*this;}//清空数据voidclear(){
            pNode cur = _listhead->_next;
            pNode del = _listhead->_next;while(cur != _listhead){
                cur = cur->_next;delete del;
                del = cur;}
            _listhead->_next = _listhead;
            _listhead->_prev = _listhead;}//析构函数~List(){clear();//释放哨兵位头节点delete _listhead;}//尾插voidpush_back(const T& val =T()){/*pNode newnode = new Node(val);
            newnode->_prev = _listhead->_prev;
            _listhead->_prev->_next = newnode;
            newnode->_next = _listhead;
            _listhead->_prev = newnode;*/insert(end(), val);}//尾删voidpop_back(){/*if (_listhead->_prev != _listhead)
            {
                pNode tail = _listhead->_prev->_prev;
                delete _listhead->_prev;
                _listhead->_prev = tail;
                tail->_next = _listhead;
            }*/erase(--end());}//头插voidpush_front(const T& val =T()){/*pNode newnode = new Node(val);
            _listhead->_next->_prev = newnode;
            newnode->_next = _listhead->_next;
            newnode->_prev = _listhead;
            _listhead->_next = newnode;*/insert(begin(), val);}//头删voidpop_front(){/*if (_listhead->_prev != _listhead)
            {
                pNode head = _listhead->_next->_next;
                delete _listhead->_next;
                _listhead->_next = head;
                head->_prev = _listhead;
            }*/erase(begin());}//任意位置前插入
        iterator insert(iterator pos,const T& x){
            pNode newnode =newNode(x);
            pNode cur = pos._pnode;
            
            cur->_prev->_next = newnode;
            newnode->_prev = cur->_prev;
            newnode->_next = cur;
            cur->_prev = newnode;//返回新插入位置的迭代器returniterator(newnode);}//任意位置删除
        iterator erase(iterator pos){assert(pos !=end());

            Node* cur = pos._pnode;
            Node* prev = cur->_prev;
            Node* next = cur->_next;

            prev->_next = next;
            next->_prev = prev;delete cur;returniterator(next);}private:
        pNode _listhead;};//迭代器测试voidtest2(){
        List<int> lt1;
        lt1.push_back(1);
        lt1.push_back(2);
        List<int>::iterator it = lt1.begin();while(it != lt1.end()){
            cout <<*it << endl;++it;}}voidFunc(const List<int>& lt){// const iterator const 迭代器不能普通迭代器前面加const修饰// const 迭代器目标本身可以修改，指向的内容不能修改 类似const T* p 
        List<int>::const_iterator it = lt.begin();while(it != lt.end()){// 指向的内容不能修改//*it += 10;

            cout <<*it <<" ";++it;}
        cout << endl;}//尾插尾删voidtest3(){
        List<int> lt1;
        lt1.push_back(1);
        lt1.push_back(2);
        lt1.push_back(3);
        lt1.push_back(4);

        lt1.pop_back();
        lt1.pop_back();

        List<int>::iterator it = lt1.begin();while(it != lt1.end()){
            cout <<*it << endl;++it;}}//头插头删voidtest4(){
        List<int> lt1;
        lt1.push_front(1);
        lt1.push_front(2);
        lt1.push_front(3);
        lt1.push_front(4);
        lt1.pop_front();
        lt1.pop_front();
        lt1.pop_front();

        List<int>::iterator it = lt1.begin();while(it != lt1.end()){
            cout <<*it << endl;++it;}}//任意位置插入删除voidtest5(){
        List<int> lt1;
        List<int>::iterator it = lt1.begin();
        lt1.insert(it,1);
        lt1.insert(it,2);
        lt1.insert(it,3);
        it = lt1.begin();
        it = lt1.erase(it);while(it != lt1.end()){
            cout <<*it << endl;++it;}}structPos{Pos(int a =100,int b =100):x(a),y(b){}int x;int y;};voidtest(){
        
        List<Pos> lt;
        lt.push_back(Pos(1,1));
        lt.push_back(Pos(2,2));
        lt.push_back(Pos(3,3));
        List<Pos>::iterator it = lt.begin();while(it != lt.end()){
            cout << it->x <<":"<< it->y << endl;
            it++;}}//构造函数测试代码voidtest6(){//默认构造
        List<int> lt1;
        lt1.push_back(1);
        lt1.push_back(2);
        lt1.push_back(3);
        lt1.push_back(4);
        List<int>::iterator it = lt1.begin();while(it != lt1.end()){
            cout <<*it <<" ";++it;}
        cout << endl;//拷贝构造
        List<int>lt2(lt1);
        it = lt2.begin();while(it != lt2.end()){
            cout <<*it <<" ";++it;}
        cout << endl;//initializer_list
        List<int> lt3 ={1,2,3,4,5};
        it = lt3.begin();while(it != lt3.end()){
            cout <<*it <<" ";++it;}}//赋值运算符重载测试代码voidtest7(){//默认构造
        List<int> lt1;
        lt1.push_back(1);
        lt1.push_back(2);
        lt1.push_back(3);
        lt1.push_back(4);
        List<int>::iterator it = lt1.begin();while(it != lt1.end()){
            cout <<*it <<" ";++it;}
        cout << endl;//赋值运算符重载
        List<int> lt2 = lt1;

        it = lt2.begin();while(it != lt2.end()){
            cout <<*it <<" ";++it;}
        cout << endl;}}

2.2List框架

✨ListNode节点

该类用来封装一个一个的节点，包括两个指针，一个指针指向前一个节点，另一个指向后一个节点，和一个存放数据的类型：

//1.list节点template<classT>structListNode{//默认构造structListNode(const T& val =T()):_node(val),_prev(NULL),_next(NULL){}//成员函数
    T _node;
    ListNode<T>* _prev;
    ListNode<T>* _next;};

ListNode类中还定义了构造函数，用来初始化数据

因为struct表明这个类里面的成员函数和成员变量都是公有的，所以直接使用struct就行

✨List类

该类包括一个成员变量，是指向第一个节点类的指针，也就是指向哨兵位头节点的指针

//2.list类template<classT>classList{public:typedefstructListNode<T> Node;typedefstructListNode<T>* pNode;private:
    pNode _listhead;};

2.3尾插尾删

//尾插voidpush_back(const T& val =T()){
    pNode newnode =newNode(val);//开辟新节点，并用val初始化
    newnode->_prev = _listhead->_prev;
    _listhead->_prev->_next = newnode;
    newnode->_next = _listhead;
    _listhead->_prev = newnode;}

如下图所示：
在这里插入图片描述

尾插节点，需要将新节点的前一个指针指向最后一个节点也就是

 _listhead->_prev

，将最后一个节点的下一个指针指向新节点，新节点的下一个指针指向哨兵位头节点，还需要将哨兵位头节点前一个指针指向新节点

因为前面的节点ListNode类中创建了构造函数，所以可以用val来初始化数据

//尾删voidpop_back(){if(_listhead->_prev != _listhead)//如果有节点{
        pNode tail = _listhead->_prev->_prev;delete _listhead->_prev;
        _listhead->_prev = tail;
        tail->_next = _listhead;}}

在这里插入图片描述

对于尾删我们需要将倒数第二个节点的下一个指针指向哨兵位头节点以及将哨兵位头节点的下一个指向倒数第二个节点，并且释放掉最后一个节点

2.4迭代器封装

与vector的迭代器直接使用数据指针

T*

不同，list迭代器如果直接使用指针，由于物理空间位置不连续，是无法使用++，以及！=判断的，所以要将其封装在一个类中，并对其需要使用的运算符进行重载：

//普通迭代器template<classT>structList_Iterator{typedefstructListNode<T> Node;typedef List_Iterator<T> self;
        Node* _pnode;//构造函数List_Iterator(Node* node):_pnode(node){}
        T&operator*()const{return _pnode->_node;}

        T*operator->()const{return&_pnode->_node;}//前置++
        self&operator++(){
            _pnode =  _pnode->_next;return*this;}//后置++
        self&operator++(int)//提供一个参数区分{
            self tmp(*this);
            _pnode = _pnode->_next;return tmp;}//前置--
        self&operator--(){
            _pnode = _pnode->_prev;return*this;}//后置--
        self&operator--(int){
            self tmp(*this);
            _pnode = _pnode->_prev;return tmp;}booloperator!=(const self& pnode){return!(_pnode == pnode._pnode);}booloperator==(const self& pnode){return _pnode == pnode._pnode;}};

因为struct表明这个类里面的成员函数和成员变量都是公有的，所以直接使用struct就行

注意这里

operator->

返回的是节点里面数据的指针

T*

，在使用时写一个->即可，为了可读性省略了一个箭头，例如对于下面的类：

structPos{Pos(int a =100,int b =100):x(a),y(b){}int x;int y;};

我们将其存入list中：

voidtest(){
    
    List<Pos> lt;
    lt.push_back(Pos(1,1));
    lt.push_back(Pos(2,2));
    lt.push_back(Pos(3,3));
    List<Pos>::iterator it = lt.begin();while(it != lt.end()){
        cout << it->x <<":"<< it->y << endl;
        it++;}}

就可以通过重载的->来获取数据的指针并通过指针访问其中包含的数据，这里本来应该写两个->，但是为了可读性省略了一个

结果如下：
在这里插入图片描述

使用迭代器时，在list类中

typedef

成我们平常使用的样子

iterator

便于统一使用，比较规范

//3.list类template<classT>classList{public:typedefstructListNode<T> Node;typedefstructListNode<T>* pNode;//迭代器typedef List_Iterator<T> iterator;
    iterator begin(){returniterator(_listhead->_next);}
    iterator end(){returniterator(_listhead);}private:
    pNode _listhead;};

在return时就可以将节点指针拷贝构造成迭代器返回了

有了迭代器我们就可以遍历打印list里面的数据啦🥳🥳

✨尾插尾删测试代码

//尾插尾删voidtest3(){
    List<int> lt1;
    lt1.push_back(1);
    lt1.push_back(2);
    lt1.push_back(3);
    lt1.push_back(4);

    lt1.pop_back();
    lt1.pop_back();//迭代器遍历
    List<int>::iterator it = lt1.begin();while(it != lt1.end()){
        cout <<*it << endl;++it;}}

结果如下：
在这里插入图片描述

✨const迭代器

对于const迭代器来说其数据是可以被访问但是不能修改，当然迭代器自身++，–是可以的，所以我们不能简单的直接在迭代器前面+const，在数据前面+const也不行，因为list中的数据不一定是const类型，所以要重新封装一个const迭代器

//const迭代器template<classT>structConst_List_Iterator{typedefstructListNode<T> Node;typedef Const_List_Iterator<T> self;
    Node* _pnode;//构造函数Const_List_Iterator(Node* node):_pnode(node){}const T&operator*()const{return _pnode->_node;}const T*operator->()const{return&_pnode->node;}//前置++
    self&operator++(){
        _pnode = _pnode->_next;return*this;}//后置++
    self&operator++(int){
        self tmp(*this);
        _pnode = _pnode->_next;return tmp;}//前置--
    self&operator--(){
        _pnode = _pnode->_prev;return*this;}//后置--
    self&operator--(int){
        self tmp(*this);
        _pnode = _pnode->_prev;return tmp;}booloperator!=(const self& pnode)const{return!(_pnode == pnode._pnode);}booloperator==(const self& pnode)const{return _pnode == pnode._pnode;}};

如下图所示const迭代器的数据不能被修改：

在这里插入图片描述

我们发现能够修改数据的只有这两个函数：

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

所以我们在返回值前面+const修饰其不能被修改即可，因为是const对象使用，所以后面也要+const修饰this

我们发现普通对象的迭代器和const对象使用的迭代器差异非常小，很多代码都是重复的，所以我们可以考虑使用模板来简化代码，代码如下：

template<classT,classRef,classPtr>structList_Iterator{typedefstructListNode<T> Node;typedef List_Iterator<T,Ref,Ptr> self;
    Node* _pnode;//构造函数List_Iterator(Node* node):_pnode(node){}
    Ref operator*()const{return _pnode->_node;}

    Ptr operator->()const{return&_pnode->_node;}//前置++
    self&operator++(){
        _pnode =  _pnode->_next;return*this;}//后置++
    self&operator++(int){
        self tmp(*this);
        _pnode = _pnode->_next;return tmp;}//前置--
    self&operator--(){
        _pnode = _pnode->_prev;return*this;}//后置--
    self&operator--(int){
        self tmp(*this);
        _pnode = _pnode->_prev;return tmp;}booloperator!=(const self& pnode){return!(_pnode == pnode._pnode);}booloperator==(const self& pnode){return _pnode == pnode._pnode;}};

因为仅仅有两个函数返回值不一样，所以我们考虑多传两个模板参数，以减少代码的数量，简化代码

template<classT>classList{public:typedefstructListNode<T> Node;typedefstructListNode<T>* pNode;//迭代器typedef List_Iterator<T,T&,T*> iterator;//const 迭代器，数据不可被修改，但可++,判断是否相等typedef List_Iterator<T,const T&,const T*> const_iterator;

    

    iterator begin(){returniterator(_listhead->_next);}
    iterator end(){returniterator(_listhead);}

    const_iterator begin()const{returnconst_iterator(_listhead->_next);}
    const_iterator end()const{returnconst_iterator(_listhead);}private:
    pNode _listhead;};

2.5头插头删

//头插voidpush_front(const T& val =T()){
    pNode newnode =newNode(val);
    _listhead->_next->_prev = newnode;
    newnode->_next = _listhead->_next;
    newnode->_prev = _listhead;
    _listhead->_next = newnode;}

//头删voidpop_front(){if(_listhead->_prev != _listhead){
        pNode head = _listhead->_next->_next;delete _listhead->_next;
        _listhead->_next = head;
        head->_prev = _listhead;}}

✨头插头删测试代码

//头插头删voidtest4(){
    List<int> lt1;
    lt1.push_front(1);
    lt1.push_front(2);
    lt1.push_front(3);
    lt1.push_front(4);
    lt1.pop_front();
    lt1.pop_front();
    lt1.pop_front();

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

结果如下：
在这里插入图片描述

2.6任意位置插入

//任意位置前插入
iterator insert(iterator pos,const T& x){
    pNode newnode =newNode(x);//创建新节点，并初始化
    
    pNode cur = pos._pnode;    
    cur->_prev->_next = newnode;
    newnode->_prev = cur->_prev;
    newnode->_next = cur;
    cur->_prev = newnode;//返回新插入位置的迭代器returniterator(newnode);}

有了任意位置插入，就可以在头插和尾插这里实现代码复用：

//头插voidpush_front(const T& val =T()){insert(begin(), val);}//尾插voidpush_back(const T& val =T()){insert(end(), val);}

2.7任意位置删除

//任意位置删除
iterator erase(iterator pos){assert(pos !=end());

    Node* cur = pos._pnode;
    Node* prev = cur->_prev;
    Node* next = cur->_next;

    prev->_next = next;
    next->_prev = prev;delete cur;returniterator(next);}

注意删除任意位置之后，迭代器会失效，所以可以返回新的迭代器，然后使用时重新赋值，这样才行

有了任意位置删除，就可以在头删和尾删这里实现代码复用：

//尾删voidpop_back(){erase(--end());}

```cpp
//头删voidpop_front(){erase(begin());}

✨任意位置插入删除测试代码

//任意位置插入删除voidtest5(){
        List<int> lt1;
        List<int>::iterator it = lt1.begin();
        lt1.insert(it,1);
        lt1.insert(it,2);
        lt1.insert(it,3);
        it = lt1.begin();
        it = lt1.erase(it);//更新迭代器while(it != lt1.end()){
            cout <<*it << endl;++it;}}

结果如下：
在这里插入图片描述

我们看到使用erase之后迭代器会失效，所以我们更新了迭代器

2.8清空数据

释放除了哨兵位头节点之外的所有节点，将哨兵位头节点的前后指针都指向自己

//清空数据voidclear(){
            pNode cur = _listhead->_next;
            pNode del = _listhead->_next;while(cur != _listhead){
                cur = cur->_next;delete del;
                del = cur;}
            _listhead->_next = _listhead;
            _listhead->_prev = _listhead;}

2.9析构函数

直接复用clear函数再释放哨兵位头节点即可

//析构函数~List(){clear();//释放哨兵位头节点delete _listhead;}

2.10构造函数

无论是哪个构造函数，我们都需要一个哨兵位头节点，所以可以单独写一个函数，用来复用

//哨兵位头节点voidEmptyInit(){
    _listhead =newNode();
    _listhead->_prev = _listhead;
    _listhead->_next = _listhead;}

✨默认构造

只需一个哨兵位头节点即可

//默认构造List(){EmptyInit();}

✨拷贝构造

//拷贝构造List(List<T>& lt){EmptyInit();/哨兵位
            for(auto& e : lt){push_back(e);}}

有了哨兵位节点之后就可以遍历lt尾插实现深拷贝了

✨initializer_list构造

和拷贝构造一样，先需要一个哨兵位头节点然后遍历initializer_list，尾插实现构造

//initializer_listList(initializer_list<T> il){EmptyInit();for(constauto& e : il){push_back(e);}}

✨测试代码

//构造函数测试代码voidtest6(){//默认构造
    List<int> lt1;
    lt1.push_back(1);
    lt1.push_back(2);
    lt1.push_back(3);
    lt1.push_back(4);
    List<int>::iterator it = lt1.begin();while(it != lt1.end()){
        cout <<*it <<" ";++it;}
    cout << endl;//拷贝构造
    List<int>lt2(lt1);
    it = lt2.begin();while(it != lt2.end()){
        cout <<*it <<" ";++it;}
    cout << endl;//initializer_list
    List<int> lt3 ={1,2,3,4,5};
    it = lt3.begin();while(it != lt3.end()){
        cout <<*it <<" ";++it;}}

结果如下：
在这里插入图片描述

2.11赋值运算符重载

和vector一样利用形参拷贝，然后交换，利用析构释放之前的list对象，返回交换后的对象

//赋值运算符重载
List<T>&operator=(List<T> lt){swap(_listhead,lt._listhead);return*this;}

✨赋值运算符重载测试代码

//赋值运算符重载测试代码voidtest7(){//默认构造
    List<int> lt1;
    lt1.push_back(1);
    lt1.push_back(2);
    lt1.push_back(3);
    lt1.push_back(4);
    List<int>::iterator it = lt1.begin();while(it != lt1.end()){
        cout <<*it <<" ";++it;}
    cout << endl;//赋值运算符重载
    List<int> lt2 = lt1;

    it = lt2.begin();while(it != lt2.end()){
        cout <<*it <<" ";++it;}
    cout << endl;}

结果如下：
在这里插入图片描述

三、结语

对于list大部分和前面学习过的vector类似，关键点在于理解list的迭代器的封装以及const迭代器，还有list实现包括了三个类，它们分别都有类模板，容易绕晕，需要好好理解清楚，以上就是今天所有的内容啦~ 完结撒花~ 🥳🎉🎉

标签： c++ list 开发语言
本文转载自: https://blog.csdn.net/Renswc/article/details/139358497
版权归原作者 大耳朵土土垚 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【C++】List模拟实现”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航