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; } };
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
//clear void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }
② 析构函数
//析构函数 ~list() { clear(); delete _head; _head = nullptr; }
③ swap
//swap void 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;//定义上一个节点为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 }
复用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）
#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; } //clear void 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); } } //swap void 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 //} //②复用insert void 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; } }
