Doubly Circular Linked List
Sep 8, 2018 · 1 min read
Similar to the doubly linked list. Just put it here for completeness:)
You can still use the head node as the tail of the linked list as I did for the previous post. But you can also just use head node for the real head since now you can easily get the tail node, and this is what I did in the codes below.
template <typename Type> class Node{
public:
Node<Type> *prior, *next;
Type data;
Node(Type _data){
data=_data;
prior=NULL;
next=NULL;
}
};//here head is the real head, not tail
template <typename Type> class List{
private:
Node<Type> *head;
public:
List(){
head=NULL;
}
~List(){
if(head==NULL) return;
Node<Type> *cur=head;
head->prior->next=NULL;
while(cur!=NULL){
Node<Type> *del=cur;
cur=cur->next;
delete del;
}
}
void append(Node<Type> *node){
if(head==NULL){
head=node;
head->prior=head;
head->next=head;
return;
}
Node<Type> *tail=head->prior;
node->next=tail->next;
tail->next->prior=node;
tail->next=node;
node->prior=tail;
}
//output all values before value
void output(Type value){
Node<Type> *cur=head;
while(cur->data!=value){
cur=cur->next;
}
Node<Type> *mark=cur;
do{
if(cur!=mark) cout<<" ";
cout<<cur->data;
cur=cur->prior;
}while(cur!=mark);
}
};//sample test code
int main(){
int n,t;
cin>>n;
List<int> list;
for(int i=0;i<n;i++){
cin>>t;
Node<int> *temp=new Node<int>(t);
list.append(temp);
}
cin>>t;
list.output(t);
}
