在C++++中选用了很多的标志模板库（STL）完结程序的规划，这种规划方法使得不同类型的方针都能通用，而不再是C语言中的一般关于不同的类型需求从头规划或许或许比较选用直接的指针操作。C++中的这种方法简化了写代码的复杂度，可是增加了编译器的复杂度和难度。
在数据结构中链表是比较根本的类型，在C++中链表是根据模板的类，因而在实践的运用过程中需求涉及到实践的类型。
#include
list
在C++中关于list的接口比较丰富，首要是关于巨细，数据的刺进、删去等。可是在C++中引入了迭代器的概念，这个迭代器是关于关于容器中比较重要的一部分，由于这种迭代器使得算法等问题与容器独立开来，迭代器本质上仍是指针，精确的将是一个封装了指针的类。
迭代器类的创立应该包含下面的操作，首要应该支撑的操作符至少包含如下（operator*()，operator++()，operator++(int)，operator==()， operator!=()）,当然也会存在const_iterator这样的常迭代器，也便是只允许拜访，不能修正方针的迭代器，当然存在迭代器的结构函数、仿制操控函数，这些函数都是必需求存在的，由于规划到了指针的操作问题，结构函数应该存在参数是链表节点指针的界说，只要存在这个界说才干直接的拜访节点方针。
当然在类中至少存在回来迭代器的begin()和end()函数，这两个函数回来的迭代器别离指向链表的开端和链表完毕的下一个地址，这是迭代器中常常简单了解过错的当地。
在C++中一般创立const_iterator类，然后iterator直接承继const_iterator。
下面说说list类规划的根本思路：
首要、创立链表节点方针，本质上是完结对传递进来的类型的封装操作，一起构成一个双向链表的根本要素（prev、next指针）。节点必定要存在结构函数，并且是直接初始化三个成员变量。
其次、创立迭代器类，本质上便是封装一个节点指针，经过节点指针完结操作，至少要完结的操作符已阐明。这两个类都要设置List为友元类，由于这样才干用List直接操作迭代器的相关操作。
最终、依托上面的迭代器类和节点类，创立一个List类，该类中首要完结一些根本操作。其间需求留意的便是迭代器的操作，比方删去元素和刺进元素今后迭代器的改变问题等。
需求留意的是在List中选用了岗兵节点，这个岗兵节点并不算实践的操作方针，也便是为了确保必定有方针所指向，存在一个head方针，这个方针的next便是实践的数据，而tail是迭代器所能抵达的最终一个方针，可是这个方针并不是合理的区域，实践上end()实践上便是指向了tail节点，这两个节点head和tail便是岗兵节点。详细的参看代码。
完结的根本形式如下：
#ifndef __MYLIST_H_H_
#define __MYLIST_H_H_
#include
namespace myspace
{
template
class List
{
private:
/*封装方针，构成链表节点*/
struct Node
{
Object data;
struct Node *prev;
struct Node *next;
/*节点结构函数*/
Node(const Object &d = Object(), Node *p = NULL, Node *n = NULL)
:data(d), prev(p),next(n){}
};
public:
/*创立一个常量迭代器类，这是容器规划的要害*/
class const_iterator
{
public:
const_iterator():current(NULL)
{}
/*重载迭代器的值*/
const Object & operator*()const
{
return retrieve();
}
/*重载前向++操作符*/
const_iterator & operator++ ()
{
current = current->next;
return *this;
}
/*重载后向++操作符，由于是一个部分方针不能回来引证*/
const_iterator operator++(int)
{
const_iterator old = *this;
++(*this);
return old;
}
/*判别迭代器是否相同，本质上便是判别指向的节点是否相同*/
bool operator==(const const_iterator &rhs) const
{
return current == rhs.current;
}
/*调用==操作符*/
bool operator!=(const const_iterator &rhs)const
{
return (!(*this == rhs));
}
protected:
/*迭代器本质便是一个节点指针*/
Node *current;
/*取得链表中的内容*/
Object & retrieve() const
{
return current->data;
}
/*根据指针参数的迭代器结构函数，确保只要List运用*/
const_iterator(Node *p):current (p)
{}
/*友元类，能够调用迭代器的私有成员*/
friend class List
/*得到方针的值*/
Object &operator*()
{
return retrieve();
}
/*根据const的重载*/
const Object& operator*()const
{
return const_iterator::operator*();
}
/*前向++操作符*/
iterator &operator++()
{
current = current->next;
return *this;
}
/*后向++操作符*/
iterator operator++(int)
{
iterator *old = *this;
++(*this);
return old;
}
protected:
/*根据节点的迭代器结构函数*/
iterator(Node *p):const_iterator(p)
{}
friend class List
List(const List &rhs)
{
/*创立岗兵节点*/
init();
/*仿制数据*/
*this = rhs;
}
const List & operator=(const List &rhs)
{
if(this == &rhs)
return *this;
/*铲除原有的信息*/
clear();
/*增加新的方针*/
for(const_iterator itr = rhs.begin(); itr != rhs.end(); ++ itr)
push_back(*itr);
return *this;
}
/*得到迭代器，本质上便是得到节点指针*/
iterator begin()
{
/*iterator()是结构函数*/
return iterator(head->next);
}
const_iterator begin()const
{
return const_iterator(head->next);
}
iterator end()
{
return iterator(tail);
}
const_iterator end()const
{
return const_iterator(tail);
}
int size()const
{
return theSize;
}
bool empty()const
{
return size() == 0;
}
void clear()
{
while( !empty())
pop_front();
}
/*得到第一个元素*/
Object & front()
{
/*选用了迭代器begin()*/
return *begin();
}
const Object &front()const
{
return *begin();
}
Object &back()
{
/*end()指向最终一个方针的下一个地址，因而需求–*/
return *–end();
}
const Object &back()const
{
return *–end();
}
/***********************************************
*从头刺进新的节点，这时候的begin现已不再是begin
*因而刺进操作会导致迭代器犯错
***********************************************/
void push_front(const Object &x)
{
insert(begin(), x);
}
/*从后刺进新的节点，这时候会将end后移*/
void push_back(const Object &x)
{
insert(end(), x);
}
/*从头弹出一个方针*/
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(–end());
}
/*刺进方针，参数是迭代器和数据*/
iterator insert(iterator itr, const Object &x)
{
/*得到当时迭代器的指针*/
Node *p = itr.current;
theSize ++;
/*
*Node *np = Node(x,p->prev,p);
this means that np->prev = p->prev,
and np->next = p;
update the p->prev and p->prev->next;
*p->prev->next = np;
*p->prev = np;
*/
return iterator(p->prev=p->prev->next= new Node(x,p->prev, p));
}
/*删去迭代器处的方针,因而删去也会导致迭代器损坏*/
iterator erase(iterator itr)
{
/*得到当时迭代器的指针*/
Node *p = itr.current;
/*得到新的迭代器，并初始化*/
iterator retVal(p->next);
/*更新链表的链接联系*/
p->prev->next = p->next;
p->next->prev = p->prev;
/*删去方针*/
delete p;
/*使得方针数削减*/
theSize –;
/*回来新的迭代器*/
return retVal;
}
/*删去迭代器指向的方针*/
iterator erase(iterator start, iterator end)
{
/*for中不运用++itr的原因是erase之后
*便是下一个迭代器，因而不需求++操作*/
for(iterator itr = start; itr != end; )
{
/*该操作会导致迭代器更新到下一个*/
itr = erase(itr);
}
return itr;
}
private:
/*链表中的数据成员*/
int theSize;
Node *head;
Node *tail;
/*初始化函数*/
void init()
{
theSize = 0;
/*create two sentinel node*/
/*构建两个岗兵节点，也便是两个并不算在结构体中的方针*/
head = new Node;
tail = new Node;
/*绑定起来*/
head->next= tail;
tail->prev =head;
}
};
}
#endif
