【C++】list模拟实现（详解）
本篇来详细说一下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);//头插0
list<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还有一部分没有介绍完，我们下次见，拜拜~
