DS (RM) Program - Linked List - Implementation of Circular Linked List

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

typedef struct node
{
   int data;
   struct node *link;
}NODE;

typedef struct {
  int count;
  int *pos;
  struct node *rear;
  struct node *link;
}HEAD;

int flag;

class circularll
{
 HEAD *pNew;
 public:
 HEAD *createHead()
 {
  HEAD *pNew;
  pNew = new HEAD;
  if(pNew)
  {
   pNew->link = NULL;
   pNew->count = 0;
   pNew->rear=NULL;
   cout<<"Memory allocated\n";
 }
 else
  pNew = NULL;
 return pNew;
 }
 void insertNode(HEAD *,int);
 void traverse(HEAD *);
 void deleteNode(HEAD *);
 void searchList(HEAD *,int);
void copyList(HEAD *);
 void reverseList(HEAD *);
 void destroyList(HEAD *);
 void count(HEAD *);
};

void circularll::insertNode(HEAD *pList, int dain)
{
 int loc,i;
 NODE *pNew,*pPre,*temp;
 pPre = pList->link;

 pNew = new NODE;
 if(pNew == NULL)
  cout<<"Memory overflow.\n";
 else
 {
  pNew->data = dain;

 }
 temp = pList->link;
 if (dain<temp->data)
  pPre=NULL;
 i=1;
 while (i<=pList->count) 
 {
  if(dain>temp->data)
  {
   pPre=temp;
   temp=temp->link;

  }
  else
   temp=temp->link;
  i++;

 }
 if(pPre==NULL)

 {
  pNew->link = pList->link;
  pList->link = pNew;
  pNew->link=pNew;
  if(pList->count==0)
   pList->rear=pNew;
  pList->count = pList->count+1;
 cout<<"\ndata is inserted.\n";
 }
else
 {
   pNew->link = pPre->link;
   pPre->link = pNew;
   if(temp==pList->link)
    pList->rear=pNew;
   pList->count = pList->count+1;
   cout<<"\ndata is inserted.\n";
  }


}
void circularll::traverse(HEAD *pList)
{
 NODE *pWalk;
 int i;
 if(pList->link==NULL)
  cout<<"List is empty\n";
 else
 {
  pWalk = pList->link;
  i=0;
  cout<<"\n";
  while (i<pList->count)
  {
   cout<<pWalk->data<<"\t";
   pWalk=pWalk->link;
   i++;
  }
  cout<<"Number of elements in linked list is \t"<<pList->count;
 }
}
void circularll::deleteNode(HEAD *pList)
{
 NODE *pWalk,*temp,*pPre;
 int num,i;
 pWalk=pPre=pList->link;
 cout<<"Enter the location to be deleted:\n";
 cin>>num;
 if(num>pList->count)
  cout<<"Location is invalid\n";
 else
 {
 if(num==1 && pList->count==1)
 {
  pList->link =NULL;
  pList->rear=NULL;
 free(pPre);
  pList->count = pList->count-1;
  cout<<"Number is deleted\n";
 }
 else if(num==1)
 {
  pList->link =pPre->link;
  free(pPre);
  pList->count = pList->count-1;
  cout<<"Number is deleted\n";

 }
 else
 {
  for(i=1;i<num;i++)
  {
   pPre=pWalk;
   pWalk=pWalk->link;
  }
  pPre->link = pWalk->link;
  free(pWalk);
  if(num==pList->count)
   pList->rear=pPre;
  pList->count = pList->count-1;
  cout<<"Number is deleted\n";
 }

 cout<<"Number of elements in linked list is \t"<<pList->count;
 }
}
void circularll::searchList(HEAD *pList,int data)
{
 NODE *pWalk,*pStart;
 int i,flag;
 pStart=pList->link;
 pWalk=pList->rear; 
 flag=1;
 if(pStart->data==data)
  cout<<"Data is present at first location\n";
 else if(pWalk->data==data)
  cout<<"Data is present at last location\n";

 else
 {
  i=2; 
  pWalk=pStart->link;

  while(pWalk->link!=pList->link)
{
   if(pWalk->data==data)
   {
    cout<<"Data is present at location\t "<<i;
    flag=1;
    break;
   }
   else
   {
    pWalk=pWalk->link;
    i++;
   }
  }
 }
 if(i>=pList->count)
  flag=0;
 if(flag==0)
 {
  cout<<"Data is not present\n";

 }
}

void circularll::count(HEAD *pList)
{
 cout<<"The number of elements in list is \t"<<pList->count;
}

void circularll::reverseList(HEAD *pList1)
{
 HEAD *pList2;
 NODE *pwalk1,*pRev,*pPre2;
 circularll cl1;
 int cnt,i;
 pList2 = cl1.createHead();
 cnt = pList1->count;
 while(cnt!=0)
 {
  i=1;
  pwalk1 = pList1->link;
  pRev = new NODE;
  while(i<cnt)
  {
   pwalk1=pwalk1->link;
   i++;
  }
  pRev->data = pwalk1->data;
  if(pList2->count==0)
{
   pList2->link=pRev;
   pList2->count=pList2->count+1;
   pPre2=pRev;
  }
  else
  {
   pPre2->link=pRev;
   pPre2=pPre2->link;
   pList2->count=pList2->count+1;
  }
  cnt--;
 }

 cl1.traverse(pList2);
}

void main()
{
 HEAD *pList;
 circularll cl;
 int choice,datain;
 clrscr();
 pList = cl.createHead();
 while(1)
 {
  cout<<"1. Insert linked list node\n";
  cout<<"2. Traverse list\n";
  cout<<"3.Delete Node\n";
  cout<<"4.Search Element\n";
  cout<<"5. Count\n";
  cout<<"7. Reverse List\n";
  cout<<"8. Exit\n";

  cout<<"\nEnter choice:";
  cin>>choice;

  switch(choice)
  {
   case 1:
    cout<<"\nEnter the element to be inserted\n";
    cin>>datain;
    cl.insertNode(pList,datain);
    break;

   case 2:
    cl.traverse(pList);
    break;
 case 3:
    cl.deleteNode(pList);
    break;
   case 4:
    cout<<"\nEnter the element to be searched:\n";
    cin>>datain;
    cl.searchList(pList,datain);
    break;
   case 5:
    cl.count(pList);
   break;
   case 6:
    cl.reverseList(pList);
    break;

   case 7:
    exit(1);        
   break;

   default: 
cout<<"Illegal option\n";
  }
 }
}

Output:

Memory allocated
1. Insert linked list node
2. Traverse list
3.Delete Node
4.Search Element
5. Count
6. Reverse List
7. Exit

Enter choice:1
Enter the element to be inserted
12

data is inserted.
1. Insert linked list node
2. Traverse list
3.Delete Node
4.Search Element
5. Count
6. Reverse List
7. Exit

Enter choice:1

Enter the element to be inserted
15

data is inserted.
1. Insert linked list node
2. Traverse list
3.Delete Node
4.Search Element
5. Count
6. Reverse List
7. Exit
Enter choice:1

Enter the element to be inserted
18

data is inserted.
1. Insert linked list node
2. Traverse list
3.Delete Node
4.Search Element
5. Count
6. Reverse List
7. Exit

Enter choice:2

12      15      18      Number of elements in linked list is    3
1. Insert linked list node
2. Traverse list
3.Delete Node
4.Search Element
5. Count
6. Reverse List
7. Exit
Enter choice: 4
Enter the element to be searched:
33
Data is not present
1. Insert linked list node
2. Traverse list
3.Delete Node
4.Search Element
5. Count
6. Reverse List
7. Exit

Enter choice:5
The number of elements in list is       3

1. Insert linked list node
2. Traverse list
3.Delete Node
4.Search Element
5. Count
6. Reverse List
7. Exit

Enter choice:6
Memory allocated
18      15      12      Number of elements in linked list is    3

1. Insert linked list node
2. Traverse list
3.Delete Node
4.Search Element
5. Count
6. Reverse List
7. Exit

Enter choice:3
Enter the location to be deleted:
1
Number is deleted
Number of elements in linked list is    2

1. Insert linked list node
2. Traverse list
3.Delete Node
4.Search Element
5. Count
6. Reverse List
7. Exit

Enter choice:2
15      18      Number of elements in linked list is    2
1. Insert linked list node
2. Traverse list
3. Delete Node
4. Search Element
5. Count
6. Reverse List
7. Exit

Enter choice:   7

Filed Under: Codes DS2, DS2, Prog DS2 on

DS (RM) Program - Linked List - Implementation of Circular Linked List

Categories

Popular Posts