OPERATION ON SINGLY LINKED LIST

OPERATIONS ON SINGLE LINKED LIST

Posted by Vinod on December 17, 2006

/*********************************************************
-> This C++ program is to perform the following operations
   on a singly linked list
   1)insertion
   2)deletion
   3)forward traversal
   4)reverse traversal
   5)search

->node structure
  1) integer data
  2) pointer to next node

-> This program works in microsoft VC++ environment
   in windows xp
-> This program uses the following header files
   1)iostream.h
********************************************************/

#include<iostream.h>

class sll
{
private:
 int data;
 sll *next;
public:
 sll* insert_one(int,sll*);
 sll* delete_one(int,sll*);
 void ftraverse(sll*);
 void rtraverse(sll*);
 void search(int,sll*);
 void function();
};

void sll::function()
{
 cout<<”******************************************\n”;
 cout<<”program to implement a singly linked list \n”;
 cout<<”******************************************\n”;

 sll * head;
 head=NULL;

 cout<<”\n\nMENU :\n”;
 cout<<”1)insertion\n”
  <<”2)deletion\n”
  <<”3)forward traversal\n”
  <<”4)reverse traversal\n”
  <<”5)search\n”
  <<”6)exit\n\n”;
 cout<<”Enter your option :”;
 int opt;
 cin>>opt;
 int d;

 while(opt!=6)
 {
  switch(opt)
  {
  case 1:
   cout<<”Enter data to the node :”;
   cin>>d;
   head=insert_one(d,head);
   cout<<”inserted\n”;
   break;
  case 2:
   cout<<”Enter the data to be deleted :”;
   cin>>d;
   head=delete_one(d,head);
   break;
  case 3:
   cout<<”The forward traversal is :\n”;
   ftraverse(head);
   break;
  case 4:
   cout<<”The reverse traversal is :\n”;
   rtraverse(head);
   cout<<”NULL\n”;
   break;
  case 5:
   cout<<”Enter the element to be searched :”;
   int d;
   cin>>d;
   search(d,head);
   break;
  case 6:
   break;
  }
  cout<<”\n\nMENU :\n”;
  cout<<”1)insertion\n”
   <<”2)deletion\n”
   <<”3)forward traversal\n”
   <<”4)reverse traversal\n”
   <<”5)search\n”
   <<”6)exit\n\n”;
  cout<<”Enter your option :”;
  cin>>opt;
 }
}

sll* sll::insert_one(int d,sll* s)
{
 sll*NEW;
 NEW=new sll;
 NEW->data=d;
 NEW->next=NULL;

 if(s==NULL)
  s=NEW;
 else
 {
  sll*s1=s;
  while(s1->next!=NULL)
   s1=s1->next;
  s1->next=NEW;
 }
 return s;
}

sll* sll::delete_one(int d,sll* s)
{
 if(s==NULL)
 {
  cout<<”list empty \n”;
  return NULL;
 }
 if(s->data==d)
  s=s->next;
 else
 {
  sll *s1=s;
  while( s1->next && s1->next->data!=d )
  {
   if(s1->next->data==d)
   {
    cout<<”deleted”;
    s1->next=s1->next->next;
    return s;
   }
   s1=s1->next;
  }
  cout<<”not found”;
 }
 return s;
}

void sll::ftraverse(sll* s)
{
 sll * s1=s;
 while(s1!=NULL)
 {
  cout<<s1->data<<” -> “;
  s1=s1->next;
 }
 cout<<”NULL\n”;
}

void sll::rtraverse(sll* s)
{
 if(s==NULL)
  return;
 else
  rtraverse(s->next);
 cout<<s->data<<”->”;
}

void sll::search(int d,sll* s)
{
 while(s!=NULL)
 {
  if(s->data==d)
  {
   cout<<”found\n”;
   return ;
  }
  s=s->next;
 }
 cout<<” search unsuccess ful \n”;
}

void main()
{
 sll list;
 list.function();
}