Friday, May 9, 2014

Sorted Linked List Program in C++




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

class node
{
public:
 int data;
 node*next;
 node (int n, node*p=NULL)
 {
  data=n;
  next=NULL;
 }
};

class SSLL
{
 node*head;
 node*tail;
public:
 SSLL()
 {
  head=tail=NULL;
 }
 void addtohead(int n);
 void addtotail(int n);
 int isempty();
 int deletefromhead();
 int deletefromtail();
 void deletelement(int n);
 void print();
 void insert(int n);
 void merge(SSLL sl2);
};

void SSLL::addtohead(int n)
{
 node*p=new node(n,head);
 if(isempty())
  head=tail=p;
 else
 {
  node*temp;
  temp=head;
  head=p;
  p->next=temp;
 }
}

void SSLL::addtotail(int n)
{
 node*p=new node(n);
 if(isempty())
  head=tail=p;
 else
 {
  tail->next=p;
  tail=p;
 }
}

int SSLL::isempty()
{
 if(head==NULL)
  return 1;
 else
  return 0;
}

int SSLL::deletefromhead()
{
 node*p;
 if(head==0)
  throw"EMPTY LIST";
 p=head;
 head=head->next;
 if(head==NULL)
  tail=NULL;
 int temp=p->data;
 delete p;
 return temp;
}

int SSLL::deletefromtail()
{
 node*p=0;
 if(head==0)
  throw"EMPTY LIST";
 p=head;
 if(head==tail)
  head=tail=NULL;
 else
 {
  while(p->next!=tail)
   p=p->next;
  tail=p;
  p=p->next;
  tail->next=NULL;
 }
int data1=p->data;
delete p;
return(data1);
}

void SSLL::deletelement(int n)
{
 node*p=head;
 node*prev=NULL;
 while(p!=NULL && p->data!=n)
 {
  prev=p;
  p=p->next;
 }
 if(p!=NULL)
 {
  if(prev==NULL)
  {
   deletefromhead();
  }
  else
   if(p->next==NULL)
    deletefromtail();
   else
   {
    node*temp;
    temp=p->next;
    prev->next=temp;
    cout<<"\nElement Deleted Successfully";
     delete p;
   }
 }
 else
 {
  throw"ELEMENT NOT PRESENT IN THE LIST";
 }
}

void SSLL::print()
{
 if(head==NULL)
  cout<<"LIST IS EMPTY";
 else
 {
  node*p=head;
  while(p!=NULL)
  {
   cout<<"\t"<<p->data;
   p=p->next;
  }
 }
}


void SSLL::insert(int n)
{
 node*pl;
 pl=head;
 if(pl==NULL)
 {
  node*p=new node(n);
  head=tail=p;
 }
 else
 {
  if(n<head->data)
   addtohead(n);
  else if(n>tail->data)
   addtotail(n);
  else
  {
   node*prev=NULL;
   while(pl->data<n)
   {
    prev=pl;
    pl=pl->next;
   }
   node*temp=NULL;
   temp=new node(n);
   temp->next=pl;
   prev->next=temp;
  }
 }
}

void SSLL::merge(SSLL sl2)
{
 SSLL sl3;
 node*p1;
 node*p2;
 p1=this->head;
 p2=sl2.head;
 while(p1!=0 && p2!=0)
 {
  if(p1->data<p2->data)
  {
   sl3.insert(p1->data);
   p1=p1->next;
  }
  else
   if(p1->data>p2->data)
   {
    sl3.insert(p2->data);
    p2=p2->next;
   }
   else
   {
    sl3.insert(p1->data);
    sl3.insert(p2->data);
    p1=p1->next;
    p2=p2->next;
   }
 }
 while(p1!=0)
 {
  sl3.insert(p1->data);
  p1=p1->next;
 }
 while(p2!=0)
 {
  sl3.insert(p2->data);
  p2=p2->next;
 }
 cout<<"\n";
 sl3.print();
}


void main()
{
 SSLL s1,s2;
 int ch,ele,ch1,ch2,ele1;
 do
 {
  cout<<"\n\nWhat Do You Want To Do";
  cout<<"\n1.)Insert An Element Into The List";
  cout<<"\n2.)View Sorted List";
  cout<<"\n3.)Delete An Element";
  cout<<"\n4.)Merge 2 Lists";
  cout<<"\n5.)Exit";
  cout<<"\nEnter Your Choice: ";
  cin>>ch;
  switch(ch)
  {
  case 1:cout<<"\nEnter The Elment You Want To Insert: ";
      cin>>ele;
      cout<<"\nEnter The Linked List You Want To Access: ";
      cin>>ch1;
      if(ch1==1)
       s1.insert(ele);
      if(ch1==2)
       s2.insert(ele);
      cout<<"\nElement Added Successfully";
      break;
  case 2:cout<<"\nEnter The List You Want To View: ";
      cin>>ch2;
      if(ch2==1)
      {
       cout<<"\n";
       s1.print();
      }
      if(ch2==2)
      {
       cout<<"\n";
       s2.print();
      }
      break;
  case 3:cout<<"\nEnter The Element You Want to Delete: ";
      cin>>ele1;
      cout<<"\nEnter The Linked List You Want To Access: ";
      cin>>ch1;
      if(ch1==1)
       s1.deletelement(ele1);
      else
       s1.deletelement(ele1);
               break;
  case 4:s1.merge(s2);
      break;
  case 5:exit(10);
      break;
  default:cout<<"\nWrong Choice!!!";
       break;
  }
 }while(ch!=5);
}

No comments:

Post a Comment