本篇来详细说一下list的模拟实现，list的大体框架实现会比较简单，难的是list的iterator的实现。我们模拟实现的是带哨兵位头结点的list。
1.准备工作
为了不和C++库里面的list冲突，我们在实现的时候用命名空间隔开。
//list.h
#pragma once
#include <iostream>
using namespace std;
namespace lyj
{}//test.cpp
#include "list.h"
namespace lyj
{void test1(){//后续测试代码}
}
int main()
{lyj::test1();return 0;
}在list.h的namespace里面实现list的节点，他的节点是一个单独的结构，并且要用类模板。
namespace lyj
{template<class T>struct list_node{T _data; //存的数据list_node<T>* _next;//指向后一个节点list_node<T>* _prev;//指向前一个节点};
}再在list.h的namespace里面实现list的类，也要用类模板。
template<class T>
struct list_node
{T _data; //存的数据list_node<T>* _next;//指向后一个节点list_node<T>* _prev;//指向前一个节点
};template<class T>
class list
{typedef list_node<T> Node; //换个短的名字
public://成员函数private:Node* _head;size_t _size;//list原本没有，我们自己加的
};成员变量加一个_size方便我们计算链表结点个数。
list_node类里面还需要一个构造函数。
struct list_node
{T _data; //存的数据list_node<T>* _next;//指向后一个节点list_node<T>* _prev;//指向前一个节点list_node(const T& data = T()) //给缺省值T():_data(data),_next(nullptr),_prev(nullptr){}
};2.list构造函数
2.1 无参构造/默认构造
在list.h的list类里面实现。
list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}哨兵位头节点，自己指向自己。
3.增删查改操作（1）
3.1 size和empty
前面说过，list里面没有设计这个成员变量，我们自己加上，方便记录个数。
size_t size() const
{return _size;
}bool empty() const
{return _size == 0;
}3.2 push_back 尾插
我们要让尾节点的_next指向新节点，哨兵位头结点的_prev指向新节点，新节点的_prev指向原来的尾节点，让新节点的_next指向哨兵位头节点，这样，新节点就成了新的尾节点。
编辑
代码实现如下。
void push_back(const T& x)
{Node* newnode = new Node(x);Node* tail = _head->_prev;//头结点的前一个就是尾节点//将新节点连接起来tail->_next = newnode;newnode->next = _head;newnode->_prev = tail;_head->_prev = newnode;++_size;
}4.迭代器的实现（重难点）
list部分的迭代器已经不是原生指针了，因为链表空间不连续，对指针++，是+到了下一个连续的地址的位置，但是这个位置不是节点。想要访问数据，也不是简单的解引用。string和vector的迭代器可以直接用原生指针，但是list的结构比较特殊，所以他的迭代器的实现也比较特殊。
所以，我们要用一个类来封装节点的指针。
4.1 list_iterator类
在list.h的namespace里面实现list_iterator类，目前我们已经有3个类了。
template<class T>
struct list_iterator
{};struct和class的区别在【C++】类和对象（上）：初识类和对象-CSDN博客 的第1点有详细介绍。
类里面我们对解引用运算符（*）和++运算符进行重载。
4.1.1 operator*
template<class T>
struct list_iterator
{typedef list_node<T> Node; //换个短的名字Node* _node;T& operator*() //重载解引用运算符{return _node->_data;//返回数据}
};解引用运算符重载的返回值是T类型的引用，因为我们需要对数据进行修改。
4.1.2 operator++和operator-- (前置++/--)
Self& operator++() //重载++{_node = _node->_next;//加到下一个节点return *this;//返回自己}迭代器++之后还是迭代器，所以返回类型是迭代器自己的类型。
Self& operator--() //重载--
{_node = _node->_prev;//减到前一个节点return *this;//返回自己
}--也是一样。
4.1.3 operator!=和operator==
另外，我们还需要重载!=运算符。
bool operator!=(const Self& s) const
{return _node != s._node;
}还可以弄一个==。
bool operator==(const Self& s) const
{return _node == s._node;
}4.1.4 迭代器这个类的构造函数
list_iterator(Node* node):_node(node)
{}4.2 list类里的迭代器实现
在list.h的list类里面实现。
先改个名字，统一一下。
public:typedef list_iterator<T> iterator;迭代器的begin是第一个节点的位置。
iterator begin()
{iterator it(_head->next);return it;
}上面的写法是有名对象，我们还可以用匿名对象，如下。
iterator begin()
{return iterator(_head->next);
}还可以走隐式类型转换，因为单参数构造函数支持隐式类型转换，如下。
iterator begin()
{return _head->next;
}三种写法都可以，任选其一。
迭代器的end是最后一个节点的下一个位置，这里就是哨兵位头节点。
iterator end()
{return _head;
}在test.cpp中测试。
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;
5.增删查改操作（2）
5.1 insert
在pos位置之前插入节点。
void insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);//连接起来newnode->_next = cur;newnode->_prev = prev;prev->_next = newnode;cur->_prev = newnode;++_size;
}在test.cpp中测试。
void test2()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.insert(lt.begin(), 0);//头插0list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}
5.2 头插以及尾插改装
我们实现了insert，push_back尾插就可以套用insert，第一个参数传迭代器end就可以了。
void push_back(const T& x)
{insert(end(), x);++_size;
}push_front就是头插，也可以套用insert，第一个参数传迭代器begin就可以了。
void push_front(const T& x)
{insert(begin(), x);++_size;
}两个一起在test.cpp中测试。
void test3()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_front(3);lt.push_front(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}
5.3 erase 删除
把pos位置的数据删除，就是把pos前一个节点和pos后一个节点连接起来。但是我们不可以删除哨兵位头节点，迭代器end是尾节点的下一个节点，就是哨兵位，所以pos不可以是end。
void erase(iterator pos)
{assert(pos != end());//不可以删哨兵位头节点Node* prev = pos._node->_prev;//存pos前后节点Node* next = pos._node->_next;prev->_next = next;//链接pos前后节点next->_prev = prev;delete pos._node;//释放pos节点--_size;
}使用assert要包含头文件#include <assert.h>。
在test.cpp中测试。
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.erase(++lt.begin());//删除第二个节点
list<int>::iterator it = lt.begin();
while (it != lt.end())
{cout << *it << " ";++it;
}
cout << endl;
5.4 头删和尾删
实现了erase，头删和尾删就可以复用它。
void pop_back()//尾删
{erase(--end());//迭代器部分重载过--
}尾节点是end的前一个节点。
void pop_front()//头删
{erase(begin());
}在test.cpp中测试。
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.pop_front();//头删
lt.pop_back();//尾删
list<int>::iterator it = lt.begin();
while (it != lt.end())
{cout << *it << " ";++it;
}
cout << endl;
本次分享就到这里，list还有一部分没有介绍完，我们下次见，拜拜~
)
