Tweet
/*Code for Program of singly link list with different functionalities in C++ Programming*/
#include <iostream.h>
#include <stdlib.h> //for exit(1)
#include <conio.h>
#define MAX 10
struct node{
int data;
struct node *next;
};
class sngllist{
node *A,*B,*MRG;
int cnt;
public:
sngllist(){
cnt=0;
A=NULL;
B=NULL;
MRG=NULL;
}
//ALL THE OPERATIONS ARE PERFORMED ON NODE A//Except Merge, union, intersection.void create(int); //initial data assignmentvoid display(int); //process is display (assumed)int count(int);
void insert();
void del();
void search();
void copy();
void reverse();
void sort();
void merge();
void unionList();
void intersectionList();
};
void sngllist :: create(int check){
node *start=NULL,*newl=NULL,*end=NULL;
int takedata;
clrscr();
cout<<"\n\t\t*****Create List*****\n";
while(1){
cout<<"\t\t-999 to Quit\n";
cout<<"\t\tEnter data : ";
cin>>takedata;
if(takedata == -999)
break;
else{
//create memory for new node
newl = new node;
if(newl == NULL){
cout<<"\n\t\tNot Enough Memory";
getch();
exit(1);
}
newl->data = takedata;
newl->next = NULL;
cnt++;
//check for first nodeif(start == NULL)
start = newl;
else
end->next = newl;
end = newl;
end->next = NULL;
}//end else
}//end while//check to create which listif(check==1){
A->next = start;
A = start;
}
if(check==2){
B->next = start;
B = start;
}
if(check==3){
MRG->next = start;
MRG = start;
}
}
void sngllist :: display(int check){
node *tmp;
//check to print which listif(check==1)
tmp=A;
if(check==2)
tmp=B;
if(check==3)
tmp=MRG;
cout<<"\n\t\t*****Display*****\n";
cout<<"\t\t";
for( ; tmp!=NULL; tmp=tmp->next){
cout<<tmp->data;
if(tmp->next != NULL)
cout<<"-->";
}//end for
getch();
}
int sngllist :: count(int check){
node *tmp;
int cnt;
for(tmp=A,cnt=0 ; tmp!=NULL; tmp=tmp->next,cnt++);//do nothingif(check==1){
cout<<"\n\t\t*****Status of List*****\n";
cout<<"\t\tTotal Items : "<<cnt;
getch();
return(cnt);
}
elsereturn(cnt); //To use count value in other functions
}
void sngllist :: insert(){
node *newl=NULL,*tmp=NULL;
int choice,takedata,pos,i;
while(1){
clrscr();
cout<<"\n\t\t*****Insertion*****\n";
cout<<"\t\t1) Begining\n";
cout<<"\t\t2) In Between\n";
cout<<"\t\t3) End\n";
cout<<"\t\t4) Return to Main Menu\n";
cout<<"\t\tEnter your choice : ";
cin>>choice;
if(choice==1 || choice==2 || choice==3){
//create memory for new node
newl = new node;
if(newl == NULL){
cout<<"\n\t\tNot Enough Memory";
getch();
exit(1);
}
cout<<"\n\t\tEnter data : ";
cin>>takedata;
newl->data = takedata;
newl->next = NULL;
}
elsereturn;
switch(choice){
case 1 : newl->next = A;
A = newl;
break;
case 2 : cout<<"\n\t\tEnter Position : ";
cin>>pos;
if(pos <=1 || pos >= count(2)){
cout<<"\n\t\tInvalid Position";
getch();
break;
}
else{
//to points to previous node from where//to insertfor(i=1,tmp=A; i < (pos-1); tmp=tmp->next,i++);
newl->next = tmp->next;
tmp->next = newl;
break;
}
case 3 : //For pointing to last nodefor(tmp=A; tmp->next != NULL; tmp=tmp->next);
tmp->next = newl;
}//end switch
}//end while
}
void sngllist :: del(){
node *delnode=NULL,*tmp=NULL;
int choice,deldata,pos,i;
while(1){
clrscr();
cout<<"\n\t\t*****Deletion*****\n";
cout<<"\t\t1) Begining\n";
cout<<"\t\t2) In Between\n";
cout<<"\t\t3) End\n";
cout<<"\t\t4) Return to Main Menu\n";
cout<<"\t\tEnter your choice : ";
cin>>choice;
switch(choice){
case 1 : delnode->next = A;
delnode = A;
A = A->next;
break;
case 2 : cout<<"\n\t\tEnter Position : ";
cin>>pos;
if(pos <=1 || pos >= count(2)){
cout<<"\n\t\tInvalid Position";
getch();
break;
}
else{
//to points to previous node from where//to insertfor(i=1,tmp=A; i < (pos-1); tmp=tmp->next,i++);
delnode = tmp->next;
tmp->next = tmp->next->next;
break;
}
case 3 : //For pointing to last nodefor(tmp=A; tmp->next->next != NULL; tmp=tmp->next);
delnode = tmp->next;
tmp->next = NULL;
break;
case 4 : return;
default : cout<<"\n\t\tInvalid Position";
getch();
}//end switch
delete(delnode);
}//end while
}
void sngllist :: search(){
node *tmp;
int item,n;
cout<<"\n\t\t*****Search*****\n";
cout<<"\t\tEnter data to be searched : ";
cin>>item;
for(tmp=A,n=1; tmp!=NULL; tmp=tmp->next,n++){
if(tmp->data == item){
cout<<"\n\t\tSearch is located at "<<n<<" location";
getch();
return;
}
}
cout<<"\n\t\tSearch Not Found";
getch();
}
void sngllist :: copy(){
node *tmp=NULL,*newl=NULL,*end=NULL;
B=NULL;
cout<<"\n\t\t*****Copy*****\n";
for(tmp=A; tmp!=NULL; tmp=tmp->next){
//create memory
newl = new node;
newl->data = tmp->data;
newl->next = NULL;
if(B == NULL){
B->next = newl;
B = newl;
}
else
end->next=newl;
end=newl;
}
cout<<"\n\t\tAfter Copy...";
cout<<"\n\n\t\t==List A==";
display(1); //List A
cout<<"\n\n\t\t==List B==";
display(2); //List B
}
void sngllist :: reverse(){
//Reversing Logic without using another list
node *prev=NULL,*curr=A,*succ=A->next;
while(succ!=NULL){
curr->next = prev;
prev = curr;
curr = succ;
succ = succ->next;
}
curr->next = prev;
prev = curr;
A = prev->next;
A = prev;
display(1);
}
void sngllist :: sort(){
node *i,*j;
int tmp;
cout<<"\n\t\t*****Sort*****\n";
for(i=A;i!=NULL;i=i->next){
for(j=i;j!=NULL;j=j->next){
if(i->data > j->data){
tmp = i->data;
i->data = j->data;
j->data = tmp;
}
}
}
cout<<"\n\t\tAfter Sort...";
cout<<"\n\n\t\t==List==";
display(1); //List B
}
void sngllist :: merge(){
node *i,*newl=NULL,*end=NULL;
MRG=NULL;
create(1); //Create List A
create(2); //Create List B
cout<<"\n\t\t*****Merge*****\n";
//Merging A to listfor(i=A;i!=NULL;i=i->next){
//create memory
newl = new node;
newl->data = i->data;
newl->next = NULL;
if(MRG == NULL){
MRG->next = newl;
MRG = newl;
}
else
end->next=newl;
end=newl;
}
//Merging B to listfor(i=B;i!=NULL;i=i->next){
//create memory
newl = new node;
newl->data = i->data;
newl->next = NULL;
end->next=newl;
end=newl;
}
cout<<"\n\t\tAfter Merge...";
cout<<"\n\n\t\t==List==";
display(3); //List MRG
}
void sngllist :: unionList(){
node *i,*j,*newl=NULL,*end=NULL;
MRG=NULL;
int flag=0;
create(1); //Create List A
create(2); //Create List B
cout<<"\n\t\t*****Union of List*****\n";
//Union A to listfor(i=A;i!=NULL;i=i->next){
if(MRG == NULL){
newl = new node;
newl->data = i->data;
newl->next = NULL;
MRG->next = newl;
MRG = newl;
end->next=newl;
end=newl;
continue;
}
for(j=MRG;j!=NULL;j=j->next){
if(i->data != j->data)
flag=1;
}
if(flag==1){
flag=0;
//create memory
newl = new node;
newl->data = i->data;
newl->next = NULL;
end->next=newl;
end=newl;
}//end if
}//end for//Union B to listfor(i=B;i!=NULL;i=i->next){
for(j=MRG;j!=NULL;j=j->next){
if(i->data != j->data)
flag=1;
}
if(flag==1){
flag=0;
//create memory
newl = new node;
newl->data = i->data;
newl->next = NULL;
end->next=newl;
end=newl;
}//end if
}//end for
cout<<"\n\t\tAfter Union...";
cout<<"\n\n\t\t==List==";
display(3); //List MRG
}
void sngllist :: intersectionList(){
node *i,*j,*newl=NULL,*end=NULL;
MRG=NULL;
int flag=0;
create(1); //Create List A
create(2); //Create List B
cout<<"\n\t\t*****Intersection of List*****\n";
//Intersection to listfor(i=A;i!=NULL;i=i->next){
for(j=B;j!=NULL;j=j->next){
if(i->data == j->data)
flag=1;
}
if(flag==1){
flag=0;
if(MRG == NULL){
newl = new node;
newl->data = i->data;
newl->next = NULL;
MRG->next = newl;
MRG = newl;
end->next=newl;
end=newl;
continue;
}
//create memory
newl = new node;
newl->data = i->data;
newl->next = NULL;
end->next=newl;
end=newl;
}//end if
}//end for
cout<<"\n\t\tAfter Intersection...";
cout<<"\n\n\t\t==List==";
display(3); //List MRG
}
void main()
{
int choice;
sngllist obj;
while(1){
clrscr();
cout<<"\n\t\tSINGLY LINK-LIST OPERATIONS\n\n";
cout<<"\t\t1) Create List\n";
cout<<"\t\t2) Display List\n";
cout<<"\t\t3) List Status\n";
cout<<"\t\t4) List Insertion\n";
cout<<"\t\t5) List Deletion\n";
cout<<"\t\t6) Search List\n";
cout<<"\t\t7) Copy List\n";
cout<<"\t\t8) Reverse List\n";
cout<<"\t\t9) Sort List\n";
cout<<"\t\t10) Merge List\n";
cout<<"\t\t11) Union of List\n";
cout<<"\t\t12) Intersection of List\n";
cout<<"\t\t13) Exit\n";
cout<<"\t\tEnter your Choice : ";
cin>>choice;
switch(choice){
case 1 : obj.create(1); // 1 for A listbreak;
case 2 : obj.display(1);// 1 for A listbreak;
case 3 : choice = obj.count(1);
//choice value is not used anywhere//it is just a placeholderbreak;
case 4 : obj.insert();
break;
case 5 : obj.del();
break;
case 6 : obj.search();
break;
case 7: obj.copy();
break;
case 8 : obj.reverse();
break;
case 9 : obj.sort();
break;
case 10 : obj.merge();
break;
case 11 : obj.unionList();
break;
case 12 : obj.intersectionList();
break;
case 13 : goto out;
default: cout<<"\n\n\t\tInvalid Choice\n\n";
getch();
break;
}
}
}
Single Linked List Operations in C++
