当前位置：首页 > 行业知识 > 【C++】List模拟实现

行业知识

【C++】List模拟实现

2026-10-31 11:03:14 来源：互联网转载

前言

hello hello~ ，这里是大耳朵土土垚~ ，欢迎大家点赞关注收藏

个人主页：大耳朵土土垚的博客

所属专栏：C++入门至进阶

这里将会不定期更新有关C++的内容，希望大家多多点赞关注收藏

一、什么是List

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

二、Lits模拟实现

2.1 List完整实现代码

#pragma onceusing namespace std;#include#includenamespace tutu{//1.list节点templatestruct ListNode{//默认构造struct ListNode(const T& val = T()):_node(val),_prev(NULL),_next(NULL){}//成员函数T _node;ListNode* _prev;ListNode* _next;};//2.迭代器类templatestruct List_Iterator{typedef struct ListNode Node;typedef List_Iterator 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;}bool operator!=(const self& pnode){return !(_pnode == pnode._pnode);}bool operator==(const self& pnode){return _pnode == pnode._pnode;}};const迭代器//template//struct Const_List_Iterator//{//typedef struct ListNode Node;//typedef Const_List_Iterator 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类templateclass List{public:typedef struct ListNode Node;typedef struct ListNode* pNode;//迭代器typedef List_Iterator iterator;//const 迭代器，数据不可被修改，但可++,判断是否相等typedef List_Iterator const_iterator;iterator begin(){return iterator(_listhead->_next);}iterator end(){return iterator(_listhead);}const_iterator begin()const{return const_iterator(_listhead->_next);}const_iterator end() const{return const_iterator(_listhead);}void EmptyInit(){_listhead = new Node();_listhead->_prev = _listhead;_listhead->_next = _listhead;}//默认构造List(){EmptyInit();}//拷贝构造List(List& lt){EmptyInit();for (auto& e : lt){push_back(e);}}//initializer_listList(initializer_list il){EmptyInit();for (const auto& e : il){push_back(e);}}//赋值运算符重载List& operator=(List lt){swap(_listhead,lt._listhead);return *this;}//清空数据void clear(){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;}//尾插void push_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);}//尾删void pop_back(){/*if (_listhead->_prev != _listhead){pNode tail = _listhead->_prev->_prev;delete _listhead->_prev;_listhead->_prev = tail;tail->_next = _listhead;}*/erase(--end());}//头插void push_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);}//头删void pop_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 = new Node(x);pNode cur = pos._pnode;cur->_prev->_next = newnode;newnode->_prev = cur->_prev;newnode->_next = cur;cur->_prev = newnode;//返回新插入位置的迭代器return iterator(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;return iterator(next);}private:pNode _listhead;};//迭代器测试void test2(){List lt1;lt1.push_back(1);lt1.push_back(2);List::iterator it = lt1.begin();while (it != lt1.end()){cout // const iterator const 迭代器不能普通迭代器前面加const修饰// const 迭代器目标本身可以修改，指向的内容不能修改 类似const T* p List// 指向的内容不能修改//*it += 10;cout Listcout Listcout Listcout Pos(int a = 100, int b = 100):x(a), y(b){}int x;int y;};void test(){Listcout //默认构造Listcout cout  1,2,3,4 ,5};it = lt3.begin();while (it != lt3.end()){cout //默认构造Listcout cout //默认构造struct ListNode(const T& val = T()):_node(val),_prev(NULL),_next(NULL){}//成员函数T _node;ListNodepublic:typedef struct ListNodepNode newnode = new Node(val);//开辟新节点，并用val初始化newnode-_prev = _listhead-_prev;_listhead-_prev-_next = newnode;newnode-_next = _listhead;_listhead-_prev = newnode;}if (_listhead-_prev != _listhead)//如果有节点{pNode tail = _listhead-_prev-_prev;delete _listhead-_prev;_listhead-_prev = tail;tail-_next = _listhead;}}typedef struct ListNode}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;}bool operator!=(const self& pnode){return !(_pnode == pnode._pnode);}bool operator==(const self& pnode){return _pnode == pnode._pnode;}};Pos(int a = 100, int b = 100):x(a), y(b){}int x;int y;};Listcout public:typedef struct ListNodereturn iterator(_listhead-_next);}iterator end(){return iterator(_listhead);}private:pNode _listhead;};Listcout typedef struct ListNode}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;}};

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

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

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

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

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

templatestruct List_Iterator{typedef struct ListNode Node;typedef List_Iterator 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;}bool operator!=(const self& pnode){return !(_pnode == pnode._pnode);}bool operator==(const self& pnode){return _pnode == pnode._pnode;}};

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

templateclass List{public:typedef struct ListNode Node;typedef struct ListNode* pNode;//迭代器typedef List_Iterator iterator;//const 迭代器，数据不可被修改，但可++,判断是否相等typedef List_Iterator const_iterator;iterator begin(){return iterator(_listhead->_next);}iterator end(){return iterator(_listhead);}const_iterator begin()const{return const_iterator(_listhead->_next);}const_iterator end() const{return const_iterator(_listhead);}private:pNode _listhead;};

2.5头插头删

//头插void push_front(const T& val = T()){pNode newnode = new Node(val);_listhead->_next->_prev = newnode;newnode->_next = _listhead->_next;newnode->_prev = _listhead;_listhead->_next = newnode;}

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

✨头插头删测试代码

//头插头删void test4(){List 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::iterator it = lt1.begin();while (it != lt1.end()){cout pNode newnode = new Node(x);//创建新节点，并初始化pNode cur = pos._pnode;cur-_prev-_next = newnode;newnode->_prev = cur->_prev;newnode->_next = cur;cur->_prev = newnode;//返回新插入位置的迭代器return iterator(newnode);}

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

//头插void push_front(const T& val = T()){insert(begin(), val);}//尾插void push_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;return iterator(next);}

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

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

//尾删void pop_back(){erase(--end());}```cpp//头删void pop_front(){erase(begin());}

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

//任意位置插入删除void test5(){List lt1;List::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 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构造函数

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

//哨兵位头节点void EmptyInit(){_listhead = new Node();_listhead->_prev = _listhead;_listhead->_next = _listhead;}

✨默认构造

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

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

✨拷贝构造

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

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

✨initializer_list构造

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

//initializer_listList(initializer_list il){EmptyInit();for (const auto& e : il){push_back(e);}}

✨测试代码

//构造函数测试代码void test6(){//默认构造List lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);List::iterator it = lt1.begin();while (it != lt1.end()){cout cout  1,2,3,4 ,5};it = lt3.begin();while (it != lt3.end()){cout swap(_listhead,lt._listhead);return *this;}//默认构造Listcout cout

上一篇：ftp服务器怎么写?

下一篇：linux服务器怎么配置hosts?