CIRCULARLY LINKED LIST

CIRCULARLY LINKED LIST (C++ CODE):

/*performing different operations on cll*/


#include<iostream.h>
#include<conio.h>
class cll
{
struct cnode
{
int data;
struct cnode *next;
}*last;
public:
cll()
{
last=NULL;
}
void create();
void display();
void insert_beg();
void insert_end();
void insert_mid();
void delete_beg();
void delete_end();
void delete_mid();
int length();

void search();
void concate(cll);
void sort();
void merge(cll);

};
void cll:: create()
{
cnode *new_node,*current;
char ch;
do
{
new_node=new cnode;
cout<<"\nenter the data:";
cin>>new_node->data;
new_node->next=new_node;
if(last==NULL)
{
last=new_node;
current=new_node;
}
else
{
new_node->next=current->next;
current->next=new_node;
last=new_node;
current=current->next;
}
cout<<"\ndo u want  to add more nodes?";
cin>>ch;
}while(ch=='y'||ch=='Y');
}
void cll::display()
{
cnode *temp;
if(last==NULL)
{
cout<<"\nList is empty";
}
else
{
temp=last->next;
cout<<" list is:";
while(temp!=last)
{
cout<<"\t"<<temp->data;
temp=temp->next;
}
cout<<"\t"<<last->data;
}
}
void cll::insert_beg()
{
cnode *node,*temp;
node=new cnode;
cout<<"\nenter the data:";
cin>>node->data;
if(last==NULL)
{
last=node;
last->next=last;
}
else
{
temp=last->next;
node->next=temp;
last->next=node;
}
}
void cll::insert_end()
{
cnode *temp,*node;
node=new cnode;
cout<<"\nenter the data:";
cin>>node->data;
temp=last;
node->next=temp->next;
temp->next=node;
last=node;
}
void cll::insert_mid()
{
cnode *temp,*node;
int count=1,pos;
node=new cnode;
cout<<"\nenter the data:";
cin>>node->data;
cout<<"\nenter the position:";
cin>>pos;
temp=last->next;
while(count<pos-1)
{
temp=temp->next;
count++;
}
node->next=temp->next;
temp->next=node;
}
void cll::delete_beg()
{
cnode *temp;
if(last==NULL)
{
cout<<"\n Cannot delete....";
}
else
{
temp=last->next;
last->next=temp->next;
cout<<"\n"<<temp->data<<"has been deleted from list\n";
delete temp;
}
}
void cll::delete_end()
{
cnode *temp1,*temp2;
int len;
if(last==NULL)
{
cout<<"\n Cannot delete....";
return;
}
else
{
  len=length();
if(len==1)
{
delete last;
last=NULL;
}
else
{
temp1=last;
temp2=last->next;
while(temp2->next!=temp1)
{
temp2=temp2->next;
}
temp2->next=last->next;
last=temp2;
cout<<"\n"<<temp1->data<<"has been deleted from list\n";
delete temp1;
}
}
}
int cll::length()
{
cnode *temp;
int count=1;
if(last==NULL)
{
cout<<"\nList is empty";
}
else
{
temp=last->next;
while(temp!=last)
{
temp=temp->next;
count++;
}
}
return count;
}

void cll::delete_mid()
{
cnode *temp1,*temp2;
int count=1,pos;
if(last==NULL)
{
cout<<"\nCannot delete....";
}
else
{
cout<<"\nenter the position:";
cin>>pos;
temp1=last->next;
temp2=last->next;
while(count<=pos-1)
{
temp1=temp1->next;
count++;
}
while(temp2->next!=temp1)
{
temp2=temp2->next;
}
temp2->next=temp1->next;
cout<<"\n"<<temp1->data<<"has been deleted from list\n";
delete temp1;
}
}
void cll::search()
{
cnode *temp;
int key,pos=1,flag=0;
if(last==NULL)
{
cout<<"\nList is empty.....";
}
else
{
temp=last->next;
cout<<"\nenter the data u want to search:";
cin>>key;
while(temp!=last)
{
if(key==temp->data)
{
flag=1;
}
pos++;
temp=temp->next;

}
}
if(flag==1||last->data==key)
{
cout<<"\nkey "<<key<<"found at position "<<pos;
}
else
cout<<"\nkey not found";

}
void cll::concate(cll b)
{
cnode *temp1,*temp2;
if(last==NULL)
{
cout<<"\nenter the first list:";
create();
display();
}
cout<<"\nenter the second list:";
b.create();
b.display();
temp1=last->next;
temp2=b.last->next;
last->next=temp2;
b.last->next=temp1;
last=b.last;

}
void cll::sort()
{
cnode *temp1,*temp2,*temp3;
int temp,count=1,len;
temp1=last->next;
temp3=last->next;
len=length();
while(count<=len)
{
temp2=last->next;
while(temp2->next!=temp3)
{
if(temp2->data>temp2->next->data)
{
temp=temp2->data;
temp2->data=temp2->next->data;
temp2->next->data=temp;
}
temp2=temp2->next;
}
temp1=temp1->next;
count++;
}
}

void main()
{
cll a,b,c;
int ch,len;
char choice;
clrscr();
do
{
cout<<"\nMENU....";
cout<<"\n1.create";
cout<<"\n2.display";
cout<<"\n3.insert at beg";
cout<<"\n4.insert at end";
cout<<"\n5.insert at middle";
cout<<"\n6.delete at start";
cout<<"\n7.delete at end";
cout<<"\n8.delete at middle";
cout<<"\n9.searching";
cout<<"\n10.length";
cout<<"\n11.concatenation";
cout<<"\n12.sort";

cout<<"\nenter the choice:";
cin>>ch;
switch(ch)

{
case 1:
a.create();
a.display();
break;
case 2:
a.display();
break;
case 3:
a.insert_beg();
a.display();
break;
case 4:
a.insert_end();
a.display();
break;
case 5:
a.insert_mid();
a.display();
break;
case 6:
a.delete_beg();
a.display();
break;
case 7:
a.delete_end();
a.display();
break;
case 8:
a.delete_mid();
a.display();
break;
case 9:
a.search();
break;
case 10:
      len=a.length();
cout<<"\nNo. of nodes="<<len;
break;
case 11:
a.concate(b);
a.display();
break;
case 12:
a.sort();
a.display();
break;
}
cout<<"\ndo u want to continue:";
cin>>choice;
}while(choice=='y'||choice=='Y');
getch();
}