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