Circular Doubly Linked List 双向循环链表 C++　例子 (四)

List(){first = 0; size = 0;}
~List();
void Delete(const int& position, T& out);
void Delete(const int& position);
void Insert(const int& position, const T& x);
void Push_Back(const T& v);
int Size()const;
T Front()const;
T Back()const;
void Begin();
void MoveNext();
bool Valid();
T GetItemData() const;
void Clear();

};

template
ostream& operator<< (ostream& out,List& list){
out << "The list's size: " << list.Size() << endl;
out << "The list's front: ";
try{
out << list.Front() << endl;
}catch(OutOfBounds ){
out << "No element in the list" << endl;
}
out << "The list's back: ";
try{
out << list.Back() << endl;
}catch(OutOfBounds ){
out << "No element in the list" << endl;
}
out << "Elements in the list:" << endl;
for(list.Begin(); list.Valid(); list.MoveNext()){
out << list.GetItemData() << ' ';
}
out << endl;
return out;
}

template
List::~List(){
Clear();
}

template
void List::Delete(const int& position){
T value;
Delete(position, value);
}

template
void List::Delete(const int& position, T& out){
if(position < 0 || position > Size() || !first){
throw OutOfBounds();
}

if(position == 0){// at the beginning of the list
out = first->data;
Node* tmp = first->next;
if(tmp == first){ //only one node,just delete it
delete first;
first = 0;
}else{ // set first node's next node to be the new first node,delete the old first node
first->pre->next = first->next;
first->next->pre = first->pre;
delete first;
first = tmp;
}
}else{//at the middle or end of the list
Node* nodeDelete = first;
//find the node which need to delete
for(int i = 0; i< position && nodeDelete->next != first; ++i){
nodeDelete = nodeDelete->next;
}
nodeDelete->pre->next = nodeDelete->next;
nodeDelete->next->pre = nodeDelete->pre;
out = nodeDelete->data;
delete nodeDelete;

}
--size;
}

template
void List::Insert(const int& position, const T& v){
if(position < 0 || position > Size()){
throw OutOfBounds();
}
Node* newNode = new Node;
newNode->data = v;

if(position == 0){// at the beginning of the list
if(!first){ //the list is empty
first = newNode;
first->next = first->pre = first;
}else{ //the new node became the first node
newNode->next = first;
first->pre = newNode;

newNode->pre = first->pre;
first->pre->pre->next = newNode;
first = newNode;
}
}else{ //at the middle or end of the list
Node* nodeBeforePostion = first;
//find the node before insert position
for(int i = 1; i < position && nodeBeforePostion; ++i){
nodeBeforePostion = nodeBeforePostion->next;
}
newNode->next = nodeBeforePostion->next;
newNode->next->pre = newNode;
newNode->pre = nodeBeforePostion;
nodeBeforePostion->next = newNode;
}
++size;
}

template
void List::Push_Back(const T& v){
Node* newNode = new Node;
newNode->data = v;
if(!first){ // the list is empty
first = newNode;
first->next = first->pre = first;
}else{
Node* lastNode = first->pre;
first->pre = newNode;
newNode->next = first;
lastNode->next = newNode;
newNode->pre = lastNode;
}
++size;
}

template
int List::Size() const{
return size;
}

template
T List::Front() const{
if(!first){
throw OutOfBounds();
}else{
return first->data;
}
}

template
T List::Back() const{
if(!first){
throw OutOfBounds();
}else{
return first->pre->data;
}
}

template
void List::Begin(){
current = first;
firstTime = true;
}

template
void List::MoveNext(){
current = current->next;
}

template
bool List::Valid(){
if(!first || (current == first && !firstTime)){
return false;
}else{
firstTime = false;
return true;
}
}

template
T List::GetItemData()const{
return current->data;
}

template
void List::Clear(){
while(Size() != 0){
Delete(0);
}
size = 0;
}

#endif

Test the clas