September 24, 2012 / IST / Language, Software Development.

Circular Lists

A circular list is one in which the last node is followed by the first node:

Circular lists are usually preferable to non-circular ones, for two reasons:

  • They provide easy access to both ends of a list: notice that we do not need the first pointer in the header, because we can easily reach the first node with L->last->next
  • the code for processing a circular list is often simpler than the code for processing a non-circular list – mainly because you don’t have to constantly check if the next node is defined – it is always defined.

At the implementation level, however, circularity does create one very tricky case that is a very common source of bugs, and that is singleton lists. When there is only one node in a circular list, it points to itself as the next node. You have to think carefully to handle this correctly.

/* Q14-> WAP In C++ To Create A Circular List And Then Count The Number Of
	  Nodes Into It*/

#include<iostream.h>
#include<conio.h>
#include<process.h>
int ctr=0;
class circlst                 //Class Declaration
{
   private:
	   struct node
	       { int info;             //Node Structure
		 node *next;
	       }*ptr,*first,*last,*track,*temp;
   public:
	   circlst()                       //Constructor
	   {ptr=first=last=track=temp=NULL;}
	   void insrt(int);
	   void delnde();
	   void displst();      //Memeber Functions
};
void circlst::insrt(int n)
{
  ptr=new node;
     if(ptr==NULL)
	{ cout<<"\nNode Cannot Be Created!!!";
	  getch();
	  exit(0);
	}
   ptr->info=n;
   ptr->next=ptr;            //Function To Insert Node

   if(first==NULL)
      {first=last=ptr;ctr++;}
   else
      { ctr++;
	last->next=ptr;
	ptr->next=first;
	last=ptr;
      }
}
void circlst::delnde()
{   if(first==NULL)
       cout<<"\nThe List Is Empty!!!";
  else
  { first=first->next;
    last->next=first;                          //Function To Delete Node
    ctr--;
    cout<<"\n\nNode Deleted Succesfully!!!";
  }
}
void circlst::displst()
{ track=temp=first;
  if(first==NULL)
     cout<<"\nThe List Is Empty!!!";
  else
  {  do
      { cout<<track->info<<" ";		//Function To Display Node
	track=track->next;
      }while((track->next)!=(first->next));
    cout<<"\n\nThere Are "<<ctr<<" Nodes Present In The List.";
  }
}
void main()                     //Main
{
  circlst ob;
  char choice;
  int data,ch;
  do
  { clrscr();
    cout<<"\n\n\t\tCOUNTING NO. OF NODES IN CIRCULAR LINKED LIST";
    cout<<"\n\t\t--------------------------------------------";
    cout<<"\n\n1.INSERT ELEMENT";
    cout<<"\n2.DISPLAY LIST";
    cout<<"\n3.DELETE ELEMENT";         //menu
    cout<<"\n4.EXIT";
    cout<<"\n\nWhich Operation Do You Want To Perform:";
    cin>>ch;
	 switch(ch)
	      {
		 case 1: cout<<"\nEnter the Data To Be Inserted:";
			 cin>>data;
			 ob.insrt(data);
			 break;
		 case 2: ob.displst();
			 break;             //calling functions
		 case 3: ob.delnde();
			 break;
		 case 4: exit(1);
		 default: cout<<"\nPleasae Enter A valid Choice(1-4)!!!";
	       }
    cout<<"\n\nDo you Want to Continue(Y/N):";
    cin>>choice;
   }while(choice=='Y' || choice=='y');
}                   //end of program