目录
0.前言
1.节点类
2.迭代器类
①普通迭代器
②const迭代器
③模板迭代器
list%E7%B1%BB%C2%A0-toc" style="margin-left:0px;">3.list类
3.1 clear、析构函数、swap
①clear
② 析构函数
③ swap
3.2构造函数
①无参构造
②赋值构造
3.3 迭代器
3.4插入函数
①insert插入
②头插
③尾插
3.5 删除函数
①erase删除
②头删
③尾删
4.测试
list.h%EF%BC%89%C2%A0-toc" style="margin-left:0px;">源代码（list.h）
0.前言
我们知道，list是一个双向循环链表，所以list的每个节点中需要存在一个指向前一个节点的指针prev、一个指向下一个节点的指针next和一个数据域data
1.节点类
因为list的底层是节点，而节点的底层又是prev、next指针和数据域data，所以我们先将节点封装为一个类，然后再用list类调用节点类。节点类的代码如下：
//定义链表节点template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;//链表节点构造函数ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}2.迭代器类
在string和vector中我们使用迭代器访问数据时需要有这样的操作：
vector<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;需要知悉的是，在C++中，为了方便和统一，无论什么类我们大多都采用此方法进行访问，string与vector都是连续的，如此访问必然不会有差错，可是list并不是连续的
我们希望++it就能找到下一个节点，而it解引用（*it）就得到节点里存的data，所以，为了使迭代器能够正常访问，我们在自定义的类中必须实现以下方法：
1. 指针可以解引用，迭代器的类中必须重载operator*()
2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
代码如下：
①普通迭代器
//①普通迭代器 可读可写template<class T>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator D;Node* _node;//迭代器构造函数__list_iterator(Node* x):_node(x){}//重载++//前置++D& operator++()//返回迭代器的引用{_node = _node->_next;//指向下一个节点return *this;}//后置++D operator++(int){D tmp(*this);_node = _node->_next;return tmp;//返回拷贝之前的值}//重载--//前置--D& operator--(){_node = _node->_prev;return *this;}//后置--D operator--(int){D tmp(*this);_node = _node->_prev;return tmp;}//重载解引用T& operator*()//返回数据的引用{return _node->_data;//返回节点里的数据}//重载->T* operator->(){return &_node->_data;}//重载！=bool operator !=(const D& s){return _node != s._node;}//重载==bool operator==(const D& s){return _node == s._node;}};②const迭代器
const迭代器的作用是只可读不可写，防止数据被修改，因此我们只需在普通迭代器的基础上对operator*()和operator->()添加const操作即可：
//②const迭代器 可读不可写template<class T>struct __list_const_iterator{typedef ListNode<T> Node;typedef __list_const_iterator D;Node* _node;//迭代器构造函数__list_const_iterator(Node* x):_node(x){}//重载++//前置++D& operator++()//返回迭代器的引用{_node = _node->_next;//指向下一个节点return *this;}//后置++D operator++(int){D tmp(*this);_node = _node->_next;return tmp;//返回拷贝之前的值}//重载--//前置--D& operator--(){_node = _node->_prev;return *this;}//后置--D operator--(int){D tmp(*this);_node = _node->_prev;return tmp;}//重载解引用const T& operator*()//返回数据的引用{return _node->_data;//返回节点里的数据}//重载->const T* operator->(){return &_node->_data; }//重载！=bool operator !=(const D& s){return _node != s._node;}//重载==bool operator==(const D& s){return _node == s._node;}};③模板迭代器
观察以上两个迭代器，不同之处也就在于对operator*()和operator->()的操作不同，代码相似度可以说达到了90%，那么有没有办法减少冗余，提高代码的可读性呢？
答案当然是有的，我们可以为两个迭代器提供一个共同的模板，再提供两个参数，当调用普通迭代器和const迭代器时，只需根据所传递的参数而选择不同的迭代器。
template<class T, class Ref, class Ptr>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T, Ref, Ptr> D;Node* _node;//迭代器构造函数__list_iterator(Node* x):_node(x){}//重载++//前置++D& operator++()//返回迭代器的引用{_node = _node->_next;//指向下一个节点return *this;}//后置++D operator++(int){D tmp(*this);_node = _node->_next;return tmp;//返回拷贝之前的值}//重载--//前置--D& operator--(){_node = _node->_prev;return *this;}//后置--D operator--(int){D tmp(*this);_node = _node->_prev;return tmp;}//重载解引用Ref operator*()//返回数据的引用{return _node->_data;//返回节点里的数据}//重载->Ptr operator->(){return &_node->_data;}//重载！=bool operator !=(const D& s){return _node != s._node;}//重载==bool operator==(const D& s){return _node == s._node;}};list%E7%B1%BB%C2%A0">3.list类
做好了节点类和迭代器类的准备工作，终于来到了主角list类
//定义链表template<class T>class list{typedef ListNode<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;private:Node* _head;};3.1 clear、析构函数、swap
①clear
//clearvoid clear(){iterator it = begin();while (it != end()){it = erase(it);}}② 析构函数
//析构函数~list(){clear();delete _head;_head = nullptr;}③ swap
//swapvoid swap(list<T>& tmp){std::swap(_head, tmp._head);}3.2构造函数
①无参构造
//链表构造函数list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}②赋值构造
//operator=list<T>& operator=(list<T> lt){swap(lt);return *this;}3.3 迭代器
//普通迭代器iterator begin(){//return iterator(_head->_next);return _head->_next;//单参数的构造函数支持隐式类型转换}iterator end(){return _head;}//const迭代器const_iterator begin() const{//return iterator(_head->_next);return _head->_next;//单参数的构造函数支持隐式类型转换}const_iterator end() const{return _head;}3.4插入函数
①insert插入
//insert插入
iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;//取当前节点Node* prev = cur->_prev;//当前节点的前一个节点Node* newnode = new Node(x);//创建并初始化新节点prev->_next = newnode;//前一个节点的_next指针指向新节点newnode->_prev = prev;//新节点的_prev指针指向前一个节点newnode->_next = cur;//新节点的_next指针指向当前节点（此时相对于新节点就变成了后一个节点）cur->_prev = newnode;//当前节点的_prev指针指向新节点（此时相对于新节点就变成了后一个节点）//return iterator(newnode);return newnode;
}②头插
//push_front头插void push_front(const T& x){insert(begin(), x);}③尾插
原始写法
void push_back(const T& x){Node* newnode = new Node(x);//开辟并初始化新节点newnode Node* tail = _head->_prev;//定义上一个节点为tailtail->_next = newnode;//上一个节点tail的next指针指向新节点newnodenewnode->_prev = tail;//新节点newnode的prev指针指向上一个节点tailnewnode->_next = _head;//新节点newnode的next指针指向头节点_head_head->_prev = newnode;//头节点_head的prve指针指向新节点newnode}复用insert
void push_back(const T& x){insert(end(), x);}复用尾插，写拷贝构造：
//拷贝构造list(list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;//拷贝之前先创建一个头节点，自己指向自己for (const auto& e : lt){push_back(e);}}3.5 删除函数
①erase删除
iterator erase(iterator pos){assert(pos != end());//避免删除哨兵位的头节点Node* cur = pos._node;//取当前节点Node* prev = cur->_prev;//取前一个节点Node* next = cur->_next;//取后一个节点prev->_next = next;next->_prev = prev;//销毁当前节点delete cur;return next;}②头删
//pop_front头删void pop_front(){erase(begin());}③尾删
//pop_back尾删void pop_back(){erase(--end());}4.测试
void test_list(){//无参构造list<int> l1;for (auto e : l1){cout << e << " ";}cout << endl;//插入//insert插入l1.insert(l1.begin(), 1);for (auto e : l1){cout << e << " ";}cout << endl;//头插l1.push_front(0);for (auto e : l1){cout << e << " ";}cout << endl;//尾插l1.push_back(2);l1.push_back(3);l1.push_back(4);for (auto e : l1){cout << e << " ";}cout << endl;//删除//erase删除l1.erase(l1.begin());for (auto e : l1){cout << e << " ";}cout << endl;//头删l1.pop_front();for (auto e : l1){cout << e << " ";}cout << endl;//尾删l1.pop_back();for (auto e : l1){cout << e << " ";}cout << endl;//赋值构造list<int> l2 = l1;for (auto e : l1){cout << e << " ";}cout << endl;}
list.h%EF%BC%89%C2%A0">源代码（list.h）
#pragma once#include <iostream>
#include <assert.h>
using namespace std;
#include <assert.h>namespace xxk
{//定义链表节点template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;//链表节点构造函数ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};//定义迭代器//在vector使用迭代器时：/*vector<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;*///在这段代码中我们希望++it就能找到下一个节点，而it解引用（*it）我们需要得到节点里存的data//可是链表并不是连续的，因迭代器使用形式与指针完全相同，想要实现以上功能，我们必须要在自定义类中实现以下方法：//1. 指针可以解引用，迭代器的类中必须重载operator*()//2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()//3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)// 至于operator--() / operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，// 所以需要重载，如果是forward_list就不需要重载--//4. 迭代器需要进行是否相等的比较，因此还需要重载operator == ()与operator != ()//③为减少冗余，提高代码的可读性，使用模板将两个类写到一起template<class T, class Ref, class Ptr>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T, Ref, Ptr> D;Node* _node;//迭代器构造函数__list_iterator(Node* x):_node(x){}//重载++//前置++D& operator++()//返回迭代器的引用{_node = _node->_next;//指向下一个节点return *this;}//后置++D operator++(int){D tmp(*this);_node = _node->_next;return tmp;//返回拷贝之前的值}//重载--//前置--D& operator--(){_node = _node->_prev;return *this;}//后置--D operator--(int){D tmp(*this);_node = _node->_prev;return tmp;}//重载解引用Ref operator*()//返回数据的引用{return _node->_data;//返回节点里的数据}//重载->Ptr operator->(){return &_node->_data;}//重载！=bool operator !=(const D& s){return _node != s._node;}//重载==bool operator==(const D& s){return _node == s._node;}};//定义链表template<class T>class list{typedef ListNode<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 iterator(_head->_next);return _head->_next;//单参数的构造函数支持隐式类型转换}iterator end(){return _head;}//const迭代器const_iterator begin() const{//return iterator(_head->_next);return _head->_next;//单参数的构造函数支持隐式类型转换}const_iterator end() const{return _head;}//链表构造函数list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}//clearvoid clear(){iterator it = begin();while (it != end()){it = erase(it);}}//析构函数~list(){clear();delete _head;_head = nullptr;}//拷贝构造list(list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;//拷贝之前先创建一个头节点，自己指向自己for (const auto& e : lt){push_back(e);}}//swapvoid swap(list<T>& tmp){std::swap(_head, tmp._head);}//operator=list<T>& operator=(list<T> lt){swap(lt);return *this;}//尾插①//void push_back(const T& x)//{// Node* newnode = new Node(x);//开辟并初始化新节点newnode // Node* tail = _head->_prev;//定义上一个节点为tail// tail->_next = newnode;//上一个节点tail的next指针指向新节点newnode// newnode->_prev = tail;//新节点newnode的prev指针指向上一个节点tail// newnode->_next = _head;//新节点newnode的next指针指向头节点_head// _head->_prev = newnode;//头节点_head的prve指针指向新节点newnode//}//②复用insertvoid push_back(const T& x){insert(end(), x);}//insert插入iterator insert(iterator pos, const T& x){Node* cur = pos._node;//取当前节点Node* prev = cur->_prev;//当前节点的前一个节点Node* newnode = new Node(x);//创建并初始化新节点prev->_next = newnode;//前一个节点的_next指针指向新节点newnode->_prev = prev;//新节点的_prev指针指向前一个节点newnode->_next = cur;//新节点的_next指针指向当前节点（此时相对于新节点就变成了后一个节点）cur->_prev = newnode;//当前节点的_prev指针指向新节点（此时相对于新节点就变成了后一个节点）//return iterator(newnode);return newnode;}//push_front头插void push_front(const T& x){insert(begin(), x);}//erase删除函数iterator erase(iterator pos){assert(pos != end());//避免删除哨兵位的头节点Node* cur = pos._node;//取当前节点Node* prev = cur->_prev;//取前一个节点Node* next = cur->_next;//取后一个节点prev->_next = next;next->_prev = prev;//销毁当前节点delete cur;return next;}//pop_back尾删void pop_back(){erase(--end());}//pop_front头删void pop_front(){erase(begin());}private:Node* _head;};void test_list(){//无参构造list<int> l1;for (auto e : l1){cout << e << " ";}cout << endl;//插入//insert插入l1.insert(l1.begin(), 1);for (auto e : l1){cout << e << " ";}cout << endl;//头插l1.push_front(0);for (auto e : l1){cout << e << " ";}cout << endl;//尾插l1.push_back(2);l1.push_back(3);l1.push_back(4);for (auto e : l1){cout << e << " ";}cout << endl;//删除//erase删除l1.erase(l1.begin());for (auto e : l1){cout << e << " ";}cout << endl;//头删l1.pop_front();for (auto e : l1){cout << e << " ";}cout << endl;//尾删l1.pop_back();for (auto e : l1){cout << e << " ";}cout << endl;//赋值构造list<int> l2 = l1;for (auto e : l1){cout << e << " ";}cout << endl;}
}
