Sunday, December 6, 2020

3. Implement Linked List using templates. Include functions for insertion, deletion and search of a number, reverse the list and concatenate two linked lists (include a function and also overload operator +).

 CMSACOR05P: Data Structures Lab


3. Implement Linked List using templates. Include functions for insertion, deletion and search of a number, reverse the list and concatenate two linked lists (include a function and also overload operator +).



#include <iostream>


using namespace std;


struct node


{


int data;


node *next;


};


class linked_list


{


private:


node *head,*tail;


public:


linked_list()


{


head = NULL;


tail = NULL;


}


void add_node(int n)


{


int x;


for(int i=1;i<=n;i++)


{


cout<<"\nDATA"<<i<<"=";


cin>>x;


node *tmp = new node;


tmp->data = x;


tmp->next = NULL;


if(head == NULL)


{


head = tmp;


tail = tmp;


}


else


{


tail->next = tmp;


tail = tail->next;


}


}


}


node* gethead()


{


return head;


}


void Search(node *head_ref,int key)


{


node *current=head_ref;


int c;


bool Flag=false;


while(current!=NULL)


{


if(current->data==key)


{




cout<<"\nSearch Successful !!!";


Flag=true;


break;


}


else


{


current=current->next;


}


c++;


}


if(Flag==true)


{


c++;


cout<<"\n"<<key<<" is in Position "<<c;


}


else


{


cout<<"\n"<<key<<" is not found";


}


}


void Insert(int pos,int x,node *head_ref)


{


node *tmp = new node;


tmp->data = x;


tmp->next = NULL;


node *ptr=NULL;


ptr=head_ref;//points 1st element


if(pos==1)


{


head=tmp;//head updated


tmp->next=ptr;


}


else


{


for(int i=1;i<pos-1;i++)


{


ptr=ptr->next;


}


node *ptr1=NULL;


ptr1=ptr->next;


ptr->next=tmp;


tmp->next=ptr1;


}


}


void Deletion(int pos,node *head_ref)


{


if(pos==1)


{


node *temp1=head_ref;


head=head_ref->next;


delete temp1;


}


else


{


node *temp=head_ref;


for(int i=0;i<pos-2;i++)


{


if(temp->next!=NULL)


{


temp=temp->next;


}


}


node *temp2=temp->next;


temp->next=temp->next->next;


delete temp2;


}


}


void reverse(node *head_ref,int n)//n= number of elements in linked list


{


int i;


node *pre,*in,*next;


pre=head_ref;//initially


in=NULL;//initially


next=NULL;//initially




while(pre!=NULL)


{


next=pre->next;


pre->next=in;//join


in=pre;//updated


pre=next;//updated


}


head=in;//at last iteration in points the last node so...


}


linked_list operator+(linked_list ob2)


{


linked_list ob3;


node *link=gethead();


while(link->next!=NULL)


{


link=link->next;


}


link->next=ob2.gethead();


ob3.head=head;


return ob3;


}


void display(node *head_ref)


{


if(head_ref == NULL)


{


cout << "NULL" << endl;


}


else


{


cout << head_ref->data <<" ";


display(head_ref->next);


}


}


~linked_list()


{


cout<<"\nThank U...";


}


};


int main()


{


cout<<"\n******PRESENTING LINKEDLIST OPERATIONS******\n";


cout<<"\nLet's create linked lists:";


linked_list a;


linked_list b;


linked_list c;


node *head;


int n1;


cout<<"\nEnter the Number of elements u want to insert in 1st linkedlist: ";


cin>>n1;


a.add_node(n1);


cout<<"\nNOW the linked list is:\n";


a.display(a.gethead());


while(1){


cout<<"\n1.Search An Element\n2.Insertion\n3.Delition\n4.Reversing\n5.Concatenate\n6.exit";


int ch;


cout<<"\nPlease enter ur Choice: ";


cin>>ch;


switch (ch)


{


case 1:


int y;


cout<<"\nEnter the Element to search: ";


cin>>y;


a.Search(a.gethead(),y);


break;


case 2:


int posI,x;


cout<<"\nEnter the position to insert element: ";


cin>>posI;


cout<<"\nEnter the NEW DATA to insert: ";


cin>>x;


a.Insert(posI,x,a.gethead());


cout<<"\nNOW the UPDATED linked list AFTER insertion:\n";


a.display(a.gethead());


break;




case 3:


int pos;


cout<<"\nEnter the position u want to DELETE: ";


cin>>pos;


a.Deletion(pos,a.gethead());


cout<<"\nNOW the UPDATED linked list AFTER deletion:\n";


a.display(a.gethead());


break;


case 4:


a.reverse(a.gethead(),n1);


cout<<"\nThe REVERSED linked list is:\n";


a.display(a.gethead());


break;


case 5:


int n2;


cout<<"\nnumber of elements u want to insert in 2nd linkedlist: ";


cin>>n2;


b.add_node(n2);


c=a+b;


cout<<"\nPresenting the Marged linked list\n";


c.display(c.gethead());


break;


case 6: cout<<"END";


default:


cout << "Sorry! Invalid Choice ";


break;


}


if(ch==6)


break;


}


return 0;


}


Posted by

No comments:

Post a Comment