1. 基本框架
首先，我们先从节点的准备工作入手，请看示例：
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
//节点
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
ListNode(const T& data = T())
:_next(nullptr)
, _prev(nullptr)
, _data(data)
{}
};在上述代码中：先定义一个双向链表的节点结构ListNode。节点结构ListNode包含以下成员变量：
1. _next：指向下一个节点的指针。
2. _prev：指向上一个节点的指针。
3. _data：存储节点数据的变量。
节点结构ListNode还包含一个构造函数，用于初始化成员变量。构造函数接受一个参数data，用于初始化_data成员变量。如果没有提供参数，则_data成员变量的默认值为T()，即T类型的默认构造函数的返回值。
该头文件还使用了iostream和assert.h两个标准头文件，并使用了std命名空间。
2. 封装迭代器
请看示例代码：
//迭代器
template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Self;
Node* _node;
ListIterator(Node* node)
:_node(node)
{}
// ++it;
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
};
在上述代码中：定义了一个迭代器结构ListIterator，用于遍历双向链表。迭代器结构ListIterator包含以下成员变量和成员函数：
成员变量： _node：指向当前迭代器所指向的节点的指针。
成员函数如下：
1. 构造函数：接受一个参数node，用于初始化迭代器的节点指针。
2. 前置递增运算符（++it）：将迭代器指向下一个节点，并返回自身的引用。
3. 前置递减运算符（--it）：将迭代器指向上一个节点，并返回自身的引用。
4. 后置递增运算符（it++）：将迭代器指向下一个节点，并返回之前的迭代器的副本。
5. 后置递减运算符（it--）：将迭代器指向上一个节点，并返回之前的迭代器的副本。
6. 解引用运算符（*）：返回迭代器指向节点的数据的引用。
7. 成员访问运算符（->）：返回迭代器指向节点数据的指针。
8. 不等于运算符（!=）：判断当前迭代器是否与另一个迭代器不相等。
9. 等于运算符（==）：判断当前迭代器是否与另一个迭代器相等。
迭代器结构ListIterator还使用了两个类型别名：
1. Node：表示节点类型ListNode<T>。
2. Self：表示迭代器自身类型ListIterator<T, Ref, Ptr>。
3. 迭代器和构造函数
请看示例代码：
template<class T>
class list
{
typedef ListNode<T> Node;
public:
// 不符合迭代器的行为，无法遍历
//typedef Node* iterator;
//typedef ListIterator<T> iterator;
//typedef ListConstIterator<T> const_iterator;
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
iterator begin()
{
//iterator it(_head->_next);
//return it;
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
list()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
该部分定义了一个双向链表类list。
list类包含以下成员变量和成员函数：
1. typedef Node：类型别名，表示节点类型ListNode<T>。
2. typedef iterator：类型别名，表示迭代器类型ListIterator<T, T&, T*>。
3. typedef const_iterator：类型别名，表示常量迭代器类型ListIterator<T, const T&, const T*>。
成员函数如下：
1. begin()：返回头节点的下一个节点的迭代器，用于遍历链表。
2. begin() const：返回头节点的下一个节点的常量迭代器，用于遍历常量链表。
3. end()：返回头节点的迭代器，用于判断迭代结束。
4. end() const：返回头节点的常量迭代器，用于判断常量迭代结束。
5. 构造函数：初始化头节点，将头节点的_next和_prev指向自身。
注意：由于ListIterator的设计不符合迭代器的行为，无法进行迭代，所以在list类中注释掉了typedef iterator和typedef const_iterator的定义。
3. push_back、pop_back、push_front和pop_front
请看示例代码：
void push_back(const T& x)
{
/*Node* newnode = new Node(x);
Node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;*/
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}这部分代码实现了list类的push_back、pop_back、push_front和pop_front成员函数。
1. push_back：在链表末尾添加一个节点。首先创建一个新的节点newnode，然后获取链表末尾的节点tail，将tail的_next指向newnode，newnode的_prev指向tail，newnode的_next指向头节点_head，头节点的_prev指向newnode。最后调用insert函数，在末尾迭代器的位置插入新节点。
2. pop_back：删除链表末尾的节点。首先获取链表末尾节点的前一个节点，然后调用erase函数，将末尾迭代器的前一个位置的节点删除。
3. push_front：在链表开头添加一个节点。调用insert函数，在开头迭代器的位置插入新节点。
4. pop_front：删除链表开头的节点。调用erase函数，将开头迭代器的位置的节点删除。
4. insert和erase
请看示例代码：
// 没有iterator失效
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);
Node* prev = cur->_prev;
// prev newnode cur
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
// erase 后 pos失效了，pos指向节点被释放了
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 iterator(next);
}这部分代码实现了list类的insert和erase成员函数。
1. insert：在指定位置前插入一个节点。首先获取迭代器pos所指向的节点cur，创建一个新的节点newnode，然后获取pos的前一个节点prev。将prev的_next指向newnode，newnode的_prev指向prev，newnode的_next指向cur，cur的_prev指向newnode。最后返回一个指向新节点的迭代器。
2. erase：删除指定位置的节点。首先断言pos不等于end()，即pos不是指向末尾的迭代器。然后获取迭代器pos所指向的节点cur，分别获取cur的前一个节点prev和后一个节点next。将prev的_next指向next，next的_prev指向prev。删除cur节点，并释放内存。最后返回一个指向删除节点后的节点的迭代器。
需要注意的是，在使用erase函数删除节点时，要确保操作前的迭代器pos不会失效，否则会导致未定义行为。
到此我们只是简单的模拟实现了一下STL中list的相关接口~,后续我们会一一展开学习的,希望这篇博客能给您带来一些启发和思考!那我们下次再一起探险喽,欢迎在评论区进行讨论~~~
