双向循环链表，STL中的iterator实现
带头节点的链表
在列表头部引入一个伪首节点来实现，这个节点被称为头节点。这个头节点的数据部分不存放列表元素；它作为存放第一个元素的节点的前驱，其链域指向“真正的”首节点。头节点的作用其实就是在循环链表中告诉你链表的起始位置
Dnode<T> *header=new dnode<T>;
header->prev=header;
header->next=header;
//default constructor
template <typename T>
class dnode
{ public:
Dnode()
{
next=this;
prev=this;
}
}
Template<Typename T>
Void writeDLinkedList(dnode<T>
*header, const string&separator=“ “)
{
Dnode<T> *p=header->next;
While(p!=header)
{
cout<<p->nodeValue<<separator;
p=p->next;
}
}
Template<Typename T>
Dnode<T> *insert(dnode<T> *curr,const
T& item)
{ dnode<T> *newNode, *prevNode;
newNode=new dnode<T>(item);
prevNode=curr->prev;
newNode->prev=prevNode;
newNode->next=curr;
prevNode->next=newNode;
curr->prev=newNode;
return newNode;
}
Template<Typename T>
void *erase(dnode<T> *curr)
{
if(curr->next==curr)return;
dnode<T> *prevNode=curr->prev,
*succNode=curr->next;
prevNode->next=succNode;
succNode->prev=prevNode;
delete curr;
}
STL中的iterator的实现
// d_liter.h
class iterator
{
public:
friend classminiList<T>;
friend classconst_iterator;
iterator() {}
bool operator== (constiterator& rhs) const
{
return nodePtr ==rhs.nodePtr;
}
bool operator!= (constiterator& rhs) const
{
return nodePtr !=rhs.nodePtr;
}
T& operator* ()
{ if (nodePtr->next== nodePtr)
throw
referenceError("miniListiterator: reference error");
returnnodePtr->nodeValue;
}
iterator& operator++() //前++
{ nodePtr =nodePtr->next;
return *this; //return new iterator value
}
iteratoroperator++ (int) //后++
{ iterator tmp = *this;
nodePtr = nodePtr->next;
return tmp; //return original iterator value
}
iterator& operator--()
{
nodePtr =nodePtr->prev;
return *this; //return new iterator value
}
iteratoroperator-- (int)
{
iterator tmp =*this;
nodePtr =nodePtr->prev;
return tmp; //return original iterator value
}
private:
dnode<T> *nodePtr;
iterator(dnode<T> *p):nodePtr(p)
{}
};