Thursday 29 November 2012

Doubly Linked List operations


/*Program to impelement Doubly Linked List operations
compiler- Turbo c++     author- Mangilal Sharma
--------------------------------------------------------*/
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

class doubly
{
 struct d_node
 {
  int data;
  d_node *rnext;
  d_node *lnext;
 }*new1,*head,*tail,*ptr,*temp;
 public:
 void creation();
 void insertion();
 void deletion();
 void display();
 doubly();
};

void doubly :: creation()
{
 if(head==NULL)
 {
  new1=new d_node[sizeof(d_node)];
  new1->rnext=NULL;
  new1->lnext=NULL;
  cout<<"enter No. of nodes:";
  cin>>new1->data;
  head=new1;
  tail=new1;
  head->rnext=tail;
  head->lnext=tail;
  tail->rnext=head;
  tail->lnext=head;
 }
 else
 cout<<"Creation done only once  !";
}

void doubly :: insertion()
{
 int i,pos;
 new1=new d_node[sizeof(d_node)];
 new1->rnext=NULL;
 new1->lnext=NULL;
 cout<<"enter number:";
 cin>>new1->data;
 cout<<"enter position you want to insert:";
 cin>>pos;
 if(pos==1)
 {
  new1->rnext=head;
  head=new1;
  tail->lnext=head;
  tail->rnext=head;
  head->lnext=tail;
 }
 else
 {
  i=1;
  temp=head;
  while(i < pos-1 && temp->rnext!=tail)
  {
   i++;
   temp=temp->rnext;
  }
  if(temp->rnext==tail)
  {
   new1->rnext=tail->rnext;
   tail->rnext=new1;
   new1->lnext=tail;
   tail=new1;
   head->lnext=tail;
  }
  else
  {
   new1->rnext=temp->rnext;
   new1->lnext=temp;
   temp->rnext=new1;
   new1->rnext->lnext=new1;
  }
 }
}

void  doubly::deletion()
{
 int pos,i;
 cout<<"Enter Position you want to Delete ?";
 cin>>pos;
 if(pos==1 && head!=tail)
 {
  ptr=head;
  head=head->rnext;
  head->lnext=tail;
  tail->rnext=head;
  delete ptr;
 }
 else
 {
  i=1;
  temp=head;
  while(i < pos-1 && temp->rnext!=tail)
  {
   i++;
   temp=temp->rnext;
  }
  if(temp->rnext!=tail)
  {
   ptr=temp->rnext;
   temp->rnext=ptr->rnext;
   ptr->rnext->lnext=ptr->lnext;
   delete ptr;
  }
  else
  {
   if(temp->rnext==tail && head!=tail)
   {
    ptr=tail;
    tail=temp;
    tail->rnext=head;
    head->lnext=tail;
    delete ptr;
   }
   else
   {
    head=NULL;
    tail=NULL;
    delete head;
    delete tail;
   }
  }
 }
}

void doubly::display()
{
 int ch;
 cout<<"1.forward traverse\n2.backward traverse";
 cout<<"Enter your choice<1/2>?  :";
 cin>>ch;
 switch(ch)
 {
  case 1:
  if(head!=NULL)
  {
   temp=head;
   while(temp!=tail)
   {
    cout<<temp->data<<"    ";
    temp=temp->rnext;
   }
   if(temp==tail)
   cout<<temp->data;
  }
  break;

  case 2 :
  if(tail!=NULL)
  {
   temp=tail;
   while(temp!=head)
   {
    cout<<temp->data<<"    ";
    temp=temp->lnext;
   }
   if(temp==head)
   cout<<temp->data;
  }
  break;
 }
}

doubly::doubly()
{
 head=tail=NULL;
 int choice;
 while(1)
 {
  cout<<"\n\t\tOperations on Doubly linked List..\n";
  cout<<"\t\t1. To Create a linked list\n";
  cout<<"\t\t2. To Insert an Element from  linked list\n";
  cout<<"\t\t3. To Delete the Elements of  linked list\n";
  cout<<"\t\t4. To Display the elements\n";
  cout<<"\t\t5. To Main menu\n";
  cout<<"\t\t6. To Exit from Programme\n";
  cout<<"\n\t\t Enter Your Choice= ";
  cin>>choice;
  switch(choice)
  {
   case 1 : creation();break;
   case 2 : insertion();break;
   case 3 : deletion();break;
   case 4 : display();break;
   case 5 : return;
   case 6 : exit(1);
   }
 }
}
/*=========================10Nov.,2010=============================*/

No comments:

Post a Comment

You are welcome, your comment helps me to make this blog more better.