【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指向哨兵位头节点，这样，新节点就成了新的尾节点。

wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==

编辑

代码实现如下。

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;