Circular Doubly Linked List 双向循环链表 C++　例子 - c++编程基础

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

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

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

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