图 1 双向链表（ a) ）和双向循环链表（ b) ）
template<typename T,...>
struct __List_node{
//...
__list_node<T>* prev;
__list_node<T>* next;
T myval;
//...
}
可以看到，list 容器定义的每个节点中，都包含 *prev、*next 和 myval。其中，prev 指针用于指向前一个节点；next 指针用于指向后一个节点；myval 用于存储当前元素的值。
template<tyepname T,...>
struct __list_iterator{
__list_node<T>* node;
//...
//重载 == 运算符
bool operator==(const __list_iterator& x){return node == x.node;}
//重载 != 运算符
bool operator!=(const __list_iterator& x){return node != x.node;}
//重载 * 运算符，返回引用类型
T* operator *() const {return *(node).myval;}
//重载前置 ++ 运算符
__list_iterator<T>& operator ++(){
node = (*node).next;
return *this;
}
//重载后置 ++ 运算符
__list_iterator<T>& operator ++(int){
__list_iterator<T> tmp = *this;
++(*this);
return tmp;
}
//重载前置 -- 运算符
__list_iterator<T>& operator--(){
node = (*node).prev;
return *this;
}
//重载后置 -- 运算符
__list_iterator<T> operator--(int){
__list_iterator<T> tmp = *this;
--(*this);
return tmp;
}
//...
}
可以看到，迭代器的移动就是通过操作节点的指针实现的。
template <class T,...>
class list
{
//...
//指向链表的头节点，并不存放数据
__list_node<T>* node;
//...以下还有list 容器的构造函数以及很多操作函数
}
另外，为了更方便的实现 list 模板类提供的函数，该模板类在构建容器时，会刻意在容器链表中添加一个空白节点，并作为 list 链表的首个节点（又称头节点）。
比如，我们经常构造空的 list 容器，其用到的构造函数如下所示：
list() { empty_initialize(); }
// 用于空链表的建立
void empty_initialize()
{
node = get_node();//初始化节点
node->next = node; // 前置节点指向自己
node->prev = node; // 后置节点指向自己
}
显然，即便是创建空的 list 容器，它也包含有 1 个节点。
图 1 list 容器底层存储示意图
//begin()成员函数
__list_iterator<T> begin(){return (*node).next;}
//end()成员函数
__list_iterator<T> end(){return node;}
//empty()成员函数
bool empty() const{return (*node).next == node;}
//front()成员函数
T& front() {return *begin();}
//back()成员函数
T& back() {return *(--end();)}
//...
本文链接：http://task.lmcjl.com/news/6731.html