Data Structures

Progam To Merge Two Sorted Linked List


#include<iostream.h>
#include<conio.h>
#include<process.h>

//   Creating a NODE Structure
struct node
{
   int data;  // data
   struct node *next;  // link to next node and previous node
};

// Creating a class LIST
class list
{
   struct node *start;
   public:
      void create(); // to create a list
      void show();   // show
      void merge(list,list);  // Merge two list's
};

// Main function
int main()
{
   clrscr();
   list l1,l2,l3;
   cout<<"Enter the First List in ascending order.
";
   l1.create(); // to create a first list
   cout<<"
Enter the Second List in ascending order.
";
   l2.create(); // to create a second list
   cout<<"
The first list is
";
   l1.show();
   cout<<"
The second list is
";
   l2.show();
   l3.merge(l1,l2);
   l3.show();
   getch();
   return (0);
}

//    Functions

// Creating a new node
void list::create()
{
   struct node *nxt_node,*pre_node;
   int value,no,i;
   start=nxt_node=pre_node=NULL;
   cout<<"
How many nodes : ";
   cin>>no;
   cout<<"Enter "<<no<<" Elements: ";
   for(i=1;i<=no;i++)
   {
      cin>>value;
      nxt_node=new node;
      nxt_node->data=value;
      nxt_node->next=NULL;
      if(start==NULL)
start=nxt_node;
      else
pre_node->next=nxt_node;
      pre_node=nxt_node;
   }
   cout<<"
The list is created!

";
}

// Displaying LIST
void list::show()
{
   struct node *ptr=start;
   cout<<"

The List is
";
   while(ptr!=NULL)
   {
      cout<<ptr->data<<" -> ";
      ptr=ptr->next;
   }
   cout<<"   ";
}

void list::merge(list l1,list l2)
{
   struct node *nxt_node,*pre_node,*pptr,*qptr;
   int dat;
   pptr=l1.start;
   qptr=l2.start;
   start=nxt_node=pre_node=NULL;
   while(pptr!=NULL && qptr!=NULL)
   {
      if(pptr->data<=qptr->data)
      {
dat=pptr->data;
pptr=pptr->next;
      }
      else
      {
dat=qptr->data;
qptr=qptr->next;
      }
      nxt_node=new node;
      nxt_node->data=dat;
      nxt_node->next=NULL;
      if(start==NULL)
start=nxt_node;
      else
pre_node->next=nxt_node;
      pre_node=nxt_node;
   }
   if(pptr==NULL)
   {
      while(qptr!=NULL)
      {
nxt_node=new node;
nxt_node->data=qptr->data;
nxt_node->next=NULL;
if(start==NULL)
   start=nxt_node;
else
   pre_node->next=nxt_node;
pre_node=nxt_node;
qptr=qptr->next;
      }
   }
   else if(qptr==NULL)
   {
      while(pptr!=NULL)
      {
nxt_node=new node;
nxt_node->data=pptr->data;
nxt_node->next=NULL;
if(start==NULL)
   start=nxt_node;
else
   pre_node->next=nxt_node;
pre_node=nxt_node;
pptr=pptr->next;
      }
   }
   cout<<"
The lists are merged.";
   return;
}





Program to insert and delete (singly linked list)
 Single linked list



Single linked list

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>


class list
{
struct node
{
int data;
node *link;
}*p;
public:
void inslast(int);
void insbeg(int);
void insnext(int,int);
void delelement(int);
void delbeg();
void dellast();
void disp();
int seek(int);
list(){p=NULL;}
~list();
};

void list::inslast(int x)
{
node *q,*t;
if(p==NULL)
{
p=new node;
p->data=x;
p->link=NULL;
}
else
{
q=p;
while(q->link!=NULL)
q=q->link;
t=new node;
t->data=x;
t->link=NULL;
q->link=t;
}
cout<<"
 Inserted successfully at the end..
";
disp();
}

void list:: insbeg(int x)
{
node *q;
q=p;
p=new node;
p->data=x;
p->link=q;
cout<<"
 Inserted successfully at the begining..
";
disp();
}


void list::delelement(int x)
{
node *q,*r;
q=p;
if(q->data==x)
{
p=q->link;
delete q;
return;
}
r=q;
while(q!=NULL)
{
if(q->data==x)
{
r->link=q->link;
delete q;
return;
}
r=q;
q=q->link;
}
cout<<"
 Element u entered   "<<x<<"    is not found..
";
}

void list:: delbeg()
{
cout<<"
 The list before deletion:
";
disp();
node *q;
q=p;
if(q==NULL)
{
cout<<"
 No data is present..
";
return;
}
p=q->link;
delete q;
return;
}


void list:: dellast()
{
cout<<"
 The list before deletion:
";
disp();
node *q,*t;
q=p;
if(q==NULL)
{
cout<<"
 There is no data in the list..
";
return;
}
if(q->link==NULL)
{
p=q->link;
delete q;
return;
}

while(q->link->link!=NULL)
q=q->link;
q->link=NULL;
return;
}

list::~list()
{
node *q;
if(p==NULL) return;
while(p!=NULL)
{
q=p->link;
delete p;
p=q;
}
}

void list::disp()
{
node *q;
q=p;
if(q==NULL)
{
cout<<"
 No data is in the list..
";
return;
}
cout<<"
 The items present in the list are :
";
while(q!=NULL)
{
cout<<" "<<q->data;
q=q->link;
}
}

void list :: insnext(int value,int position)
{
node *temp,*temp1;
temp=p;
if(temp1==NULL)
{
temp1= new node;
temp1->data=value;
temp1->link=NULL;
p=temp1;
return;
}
for(int i=0;((i<position)&&(temp->link!=NULL)) ;i++)
{
if(i==(position-1))
{
temp1= new node;
temp1->data= value;
temp1->link=temp->link;
temp->link=temp1;
}
temp=temp->link;
}
//cout<<"
 Inserted successfully at the position.."<<position;
disp();
}


int list::seek(int value)
{
node *temp;
temp=p;
int position=0;
while(temp!=NULL)
{
if(temp->data==value)
return position+1;
else
{
temp=temp->link;
position=position+1;
}
}
cout<<"

 Element "<<value<<" not found";
return 0;
}


void main()
{
list l;
int ch,v,p,ps;
do
{
clrscr();
cout<<"
 Operations on List..
";
cout<<"
1.Insertion
2.Deletion
3.Display
4.Seek
5.Exit";
cout<<"
 Enter ur choice:";
cin>>ch;

switch(ch)
{
case 1:
cout<<"
1.Insertion at begining
2.Insertion at the end
";
cout<<"3.Insertion after the mentioned position
";
cout<<"
 Enter ur choice:";
cin>>ps;
cout<<"
 Enter the value to insert:";
cin>>v;
switch(ps)
{
case 1:
l.insbeg(v);
break;
case 2:
l.inslast(v);
break;
case 3:
cout<<"
 Enter the position to insert the value:";
cin>>p;
l.insnext(v,p);
break;

default:
cout<<"
 The choice is invalid
";
return;
}
break;

case 2:
cout<<"
1.Delete the first element
2.Delete the last element";
cout<<"
3.Enter the element to delete from the list";
cout<<"
 Enter ur choice:";
cin>>ps;
switch(ps)
{
case 1:
l.delbeg();
cout<<"
 The list after deletion:
";l.disp();
break;
case 2:
l.dellast();
cout<<"
 The list after deletion:
";l.disp();
break;
case 3:
l.disp();
cout<<"
 Enter the element to delete : ";
cin>>v;
l.delelement(v);
cout<<"
 The list after deletion:
";l.disp();
break;

default:
cout<<"
 The option is invalid...
";
break;
}
break;

case 3:
l.disp();
break;

case 4:
l.disp();
cout<<"
 Enter the element to search:";
cin>>v;
cout<<"
 The position of the element "<< v<<"  is "<<l.seek(v);
getch();
break;

case 5:
exit(1);

default:
cout<<"
 The option is invalid...
";
return;
}
getch();
}while(ch!=5);
getch();
return;
}