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

[cpp]
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::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;
}

Circular Double Linked List Customized Class

[cpp]
#ifndef _List_
#define _List_

#include

using namespace std;

//exception
class OutOfBounds{
public:
OutOfBounds(){}
};

template class List;

template
class Node{
friend List;
private:
T data;
Node* pre,* next;
};


template
class List{
//overwrite operator <<
template friend ostream& operator<<(ostream& ,List&);
private:
Node* first;
int size;

bool firstTime;//used for print list element.
Node* current;

public:

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->