在C++标准模板库（STL）中，list是一个非常强大的容器，它基于双向链表实现，支持高效的插入和删除操作。虽然我们可以直接使用STL中的list，但通过自己模拟实现一个list，可以更好地理解其背后的原理和数据结构的精髓。
今天我们要从三个方面来实现list：list的结构，list迭代器和list的常用接口。闲话少说，直接进入主题！
模拟实现list结点类
从上面的图片我们可以看到list中有三个成员变量，分别是prev前驱指针、next后驱指针和data数据域。
template<class T>
//建立节点结构
struct Mylist_node
{
Mylist_node<T>* prev;
Mylist_node<T>* next;
T data;
//构造函数
Mylist_node(const T& val = T())
:prev(nullptr)
, next(nullptr)
, data(val)
{}
};
如上代码，我们分别写出了前驱指针，后驱指针和数据域。但是我们很奇怪的是，为什么要写一个构造函数呢？
初始化成员变量：构造函数可以为结构体的成员变量提供初始值。在上述的代码中，prev和next被初始化为nullptr，表示新创建的节点最初没有前驱和后继节点。
灵活性：通过构造函数，你可以灵活地为不同类型的数据成员提供不同的初始值。
构造函数中的T()是什么意思？
在构造函数中，T()是一个默认构造函数调用。这里的T是一个模板参数，表示Mylist_node可以存储任意类型的数据。T()表示调用类型T的默认构造函数来初始化data成员。
什么时候需要加上T()？
当你需要确保data成员被正确初始化，并且类型T有一个可用的默认构造函数时，就需要加上T()。
例如：
如果T是一个类类型，并且你希望data成员被初始化为该类的默认状态。
如果T是一个基本数据类型（如int、double等），T()将调用该类型的默认构造函数，通常将其初始化为0或0.0等。
模拟实现list迭代器
list的迭代器跟我们前面说的vector的迭代器大有不同，比vector的迭代器更加难实现，也就是说更加的复杂！话不多说我们来看看！
我们现在来分别实现两种迭代器普通迭代器和const迭代器。
普通迭代器：
template <class T>
struct list_iterator
{
typedef Mylist_node Node;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->data;
}
T operator->()
{
return &_node->data;
}
list_iterator<T>& operator++()
{
_node = _node->next;
return (*this);
}
bool operator!=(const list_iterator<T>& it)
{
return _node != it._node;
}
bool operator==(const list_iterator<T>& it)
{
return _node == it._node;
}
};
const迭代器：
template <class T>
struct list_const_iterator
{
typedef Mylist_node Node;
Node* _node;
list_const_iterator(Node* node)
:_node(node)
{}
const T& operator*()
{
return _node->data;
}
const T operator->()
{
return &_node->data;
}
list_const_iterator<T>& operator++()
{
_node = _node->next;
return _node;
}
bool operator!=(const list_const_iterator<T>& it)
{
return _node != it._node;
}
bool operator==(const list_const_iterator<T>& it)
{
return _node == it._node;
}
};
我们观察上面我们实现的两个迭代器，是不是发现一个问题？就是很多代码其实重复了，那我们又该怎么办呢？当然是复用呀！我们该怎么复用上述代码呢？
如下所示：
//构造list迭代器结构
template<class T,class Ref,class Ptr>
struct list_iterator
{
typedef Mylist_node<T> Node;
typedef list_iterator Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->data;
}
Ptr operator->()
{
return &_node->data;
}
Self& operator++()
{
_node = _node->next;
return (*this);
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->next;
return tmp;
}
Self& operator--()
{
_node = _node->prev;
return (*this);
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->prev;
return tmp;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
};
如上代码，我们将两个迭代器的代码合二为一。那这样就会冒出很多问题了，为什么我们这样可以实现两个迭代器呢？一系列的问题。我们逐一解决！
首先我们看第一个问题：
template<class T,class Ref,class Ptr>
对于我们这里实现的模板，其中Ref和Ptr，这两个是啥玩意儿呀？
我们看上述红色框框里的内容，我们再往上翻，我们实现普通迭代器和const迭代器的时候，最突出的区别是不是在重载*和->的时候一个需要有const一个没有呢？
第二个问题在于前置++和后置++(前置–/后置–)
为什么前置++实现的时候要引用返回而后置++不用呢？
前置迭代器（++it）
前置迭代器在递增操作后返回一个新的迭代器，该迭代器指向下一个元素。由于这个操作改变了迭代器的状态（即它现在指向下一个元素），因此返回类型是引用（Self&），这意味着返回的是当前对象的引用。这样做的好处是可以链式调用，例如 ++(++it)，而不会创建临时对象，从而提高效率。
后置迭代器（it++）
后置迭代器在递增操作后返回一个旧的迭代器，该迭代器仍然指向原始位置。由于这个操作不改变当前对象的状态，而是创建一个新的对象来表示递增后的状态，因此返回类型是值（Self），这意味着返回的是当前对象的拷贝。这样做的好处是可以在递增操作后仍然访问原始位置的元素。
为什么前置++（）内不用加int而后置++却需要加上int呢？
在C++中，后置递增操作符需要一个参数（通常是int），以区分前置递增和后置递增。这是因为C++需要一种方式来区分这两种操作，而参数类型是区分它们的一种方式。
模拟实现list中的常用接口
list的构造函数：
void empty_Mylist()
{
_head = new Node;
_head->next = _head;
_head->prev = _head;
_size = 0;
}
Mylist()
{
empty_Mylist();
}
这就没什么好说的，创建一个新的结点将，将前驱指针和后驱指针都指向自己，有效数据size置为零。上述我将其分为了两部分。
list的析构函数：
~Mylist()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
list的析构函数又跟vector有很大的区别，vector中的析构函数将容器内的数据置为空就好了，但是在list中需要将链表中的结点一个个清除掉，再将链表的头结点清除，所以如上我们创建一个clear函数遍历清除掉每一个结点。（上述我实现clear时用到了erase，后续我们会将它实现出来）
list的拷贝构造：
在模拟实现list中的接口的时候肯定避免不了的就是深拷贝，有深拷贝我们必然就是要实现拷贝构造。
Mylist(const Mylist<T>& it)
{
empty_Mylist();
for (auto& e : it)
{
push_back(e);
}
}
list中的赋值运算符重载：
//赋值运算符重载
void swap(Mylist<T> it)
{
std::swap(_head, it._head);
std::swap(_size, it._size);
}
Mylist<T>& operator= (Mylist<T> it)
{
swap(it);
return (*this);
}
赋值运算符重载就不多说了，看上述代码实现。
list中的尾插实现：
void push_back(const T& val)
{
//创建一个新节点
Node* newnode = new Node(val);
//插入数据
Node* tail = _head->prev;
newnode->prev = tail;
newnode->next = _head;
tail->next = newnode;
_head->prev = newnode;
}
如上代码是list尾插代码实现，但是我们可以在实现insert之后，用insert来复用push_back，复用如下：
void push_back(const T& val)
{
insert(end(), val);
}
list的insert实现：
void insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->prev;
//创建一个新的节点
Node* newnode = new Node(val);
//将新的节点插入链表中
prev->next = newnode;
newnode->prev = prev;
newnode->next = cur;
cur->prev = newnode;
//有效数字++
_size++;
}
list的erase实现：
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* nextnode = cur->next;
Node* prevnode = cur->prev;
prevnode->next = nextnode;
nextnode->prev = prevnode;
delete cur;
--_size;
return iterator(nextnode);
}
上述代码，就是实现erase。那么我们会有问题，就是为什么erase返回的类型是迭代器呢？什么原因呢？如果返回的不是迭代器会出现什么问题吗？
原因：返回一个指向下一个元素的迭代器可以避免重新获取迭代器的开销，特别是在循环中删除元素时。这样可以提高代码的执行效率。在删除元素后，返回下一个元素的迭代器可以保持迭代器的连续性，使得在删除元素后可以无缝地继续遍历列表。如果删除操作失败（例如，尝试删除一个不存在的元素），返回一个有效的迭代器可以避免返回一个无效的迭代器，从而减少错误处理的复杂性。
如果不这样使用会出现什么问题：如果你在遍历容器时删除元素，返回类型不是迭代器会导致你无法获取到被删除元素之后的那个元素的迭代器。这将使得你难以继续遍历容器，因为你失去了对下一个元素的引用。
其他模式实现接口：
//有效数据
size_t size() const
{
return _size;
}
//头插
void push_front(const T& val)
{
insert(begin(), val);
}
//尾删
void pop_back()
{
erase(end());
}
//头删
void pop_front()
{
erase(begin());
}
模拟实现list代码总览
Mylist.h:
#pragma once
#include <iostream>
#include <assert.h>
namespace cjc
{
template<class T>
//建立节点结构
struct Mylist_node
{
Mylist_node<T>* prev;
Mylist_node<T>* next;
T data;
//构造函数
Mylist_node(const T& val = T())
:prev(nullptr)
, next(nullptr)
, data(val)
{}
};
//构造list迭代器结构
template<class T,class Ref,class Ptr>
struct list_iterator
{
typedef Mylist_node<T> Node;
typedef list_iterator Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->data;
}
Ptr operator->()
{
return &_node->data;
}
Self& operator++()
{
_node = _node->next;
return (*this);
}
Self operator++(int) //后置++需要int区分一下
{
Self tmp(*this); //这里最开始的类型不对
_node = _node->next;
return tmp;
}
Self& operator--()
{
_node = _node->prev;
return (*this);
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->prev;
return tmp;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
};
/*template <class T>
struct list_iterator
{
typedef Mylist_node Node;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->data;
}
T operator->()
{
return &_node->data;
}
list_iterator<T>& operator++()
{
_node = _node->next;
return (*this);
}
bool operator!=(const list_iterator<T>& it)
{
return _node != it._node;
}
bool operator==(const list_iterator<T>& it)
{
return _node == it._node;
}
};
template <class T>
struct list_const_iterator
{
typedef Mylist_node Node;
Node* _node;
list_const_iterator(Node* node)
:_node(node)
{}
const T& operator*()
{
return _node->data;
}
const T operator->()
{
return &_node->data;
}
list_const_iterator<T>& operator++()
{
_node = _node->next;
return _node;
}
bool operator!=(const list_const_iterator<T>& it)
{
return _node != it._node;
}
bool operator==(const list_const_iterator<T>& it)
{
return _node == it._node;
}
};*/
template <class T>
class Mylist
{
typedef Mylist_node<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);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
return iterator(_head->next);
}
const_iterator end() const
{
return iterator(_head);
}
//构造函数
void empty_Mylist()
{
_head = new Node;
_head->next = _head;
_head->prev = _head;
_size = 0;
}
Mylist()
{
empty_Mylist();
}
//析构函数
~Mylist()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
//拷贝构造
Mylist(const Mylist<T>& it)
{
empty_Mylist();
for (auto& e : it)
{
push_back(e);
}
}
//赋值运算符重载
void swap(Mylist<T> it)
{
std::swap(_head, it._head);
std::swap(_size, it._size);
}
Mylist<T>& operator= (Mylist<T> it)
{
swap(it);
return (*this);
}
//有效数据
size_t size() const
{
return _size;
}
//尾插实现
void push_back(const T& val)
{
创建一个新节点
//Node* newnode = new Node(val);
插入数据
//Node* tail = _head->prev;
//newnode->prev = tail;
//newnode->next = _head;
//tail->next = newnode;
//_head->prev = newnode;
insert(end(), val);
}
//头插
void push_front(const T& val)
{
insert(begin(), val);
}
//尾删
void pop_back()
{
erase(end());
}
//头删
void pop_front()
{
erase(begin());
}
//插入数据
void insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->prev;
//创建一个新的节点
Node* newnode = new Node(val);
//将新的节点插入链表中
prev->next = newnode;
newnode->prev = prev;
newnode->next = cur;
cur->prev = newnode;
//有效数字++
_size++;
}
//删除数据
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* nextnode = cur->next;
Node* prevnode = cur->prev;
prevnode->next = nextnode;
nextnode->prev = prevnode;
delete cur;
--_size;
return iterator(nextnode);
}
private:
Node* _head;
size_t _size;
};
}
test.cpp:
#define _CRT_SECURE_NO_WARNINGS 1
#include "Mylist.h"
#include <iostream>
void Test1()
{
cjc::Mylist<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
for (auto& e : l1)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
void Test2()
{
cjc::Mylist<int>l2;
l2.push_front(1);
l2.push_front(2);
l2.push_front(3);
l2.push_front(4);
for (auto& e : l2)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
void Test3()
{
cjc::Mylist<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
l1.erase(l1.begin());
l1.erase(l1.begin());
l1.erase(l1.begin());
for (auto& e : l1)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
void Test4()
{
cjc::Mylist<int>l2;
l2.push_front(1);
l2.push_front(2);
l2.push_front(3);
l2.push_front(4);
l2.insert(l2.begin(), 0);
l2.insert(l2.begin(), 0);
l2.insert(l2.begin(), 0);
l2.insert(l2.begin(), 0);
for (auto& e : l2)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
void Test5()
{
cjc::Mylist<int>l2;
l2.push_front(1);
l2.push_front(2);
l2.push_front(3);
l2.push_front(4);
for (auto& e : l2)
{
std::cout << e << " ";
}
std::cout << std::endl;
l2.clear();
for (auto& e : l2)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
int main()
{
尾插测试
//Test1();
头插测试
//Test2();
尾删测试
//Test3();
头删测试
//Test4();
//删除测试
Test5();
return 0;
}