Circular Linked List

Circular Linked List

• The circular linked list is as shown below

• The Circular Linked List (CLL) is similar to singly linked list except that the last node's next pointer points to first node.

Various operations that can be performed on circular linked list are,

1. Creation of circular linked list.

2. Insertion of a node in circular linked list.

3. Deletion of any node from linked list.

4. Display of circular linked list.

We will see each operation along with some example.

 

1. Creation of circular linked list

void sll ::Create()

{

char ans;

int flag=1;

node *New,*temp;

clrscr();

do

{

      New = new node;

      New‒>next=NULL;

      cout<<"\n\n\n\tEnter The Element\n";

      cin>>New‒>data;

      if(flag= =1) /*flag for setting the starting node*/

      {

            head = New;

            New‒>next =head;      // Single node in the Circular list

            flag = 0;/*reset flag*/

      }

      else                /* find last node in list */

      {

            temp=head;

            while (temp‒>next = head)/*finding the last node*/

            temp= temp‒>next; /*temp is a last node*/

            temp‒>next=New;

            New‒>next=head; /*each time making the list circular*/

      }

      cout<<"\n Do you want to enter more nodes?(y/n)";

      ans=getch();

      }while(ans= ='y' || ans = = 'Y');

}

Initially we will allocate memory for New node using a function get_node(). There is one variable flag whose purpose is to check whether first node is created or not. That means flag is 1 (set) then first node is not created. Therefore after creation of first node we have to reset the flag (making flag = 0).

Initially,

Suppose we have taken

element '10' the flag = 1,

head = New;

New← next= head;

flag = 0;

Here variable head indicates starting node.

Now as flag = 0, we can further create the nodes and attach them as follows.

When we have taken element '20'

If we want to insert 30 then

If we want to insert 40 then

Thus we can create a circular linked list by inserting one more element 50. It is as shown below ‒

 

2. Display of circular linked list

void sll::Display()

{

node *temp;

temp = head;

if(temp = = NULL)

      cout<<"\n Sorry,The List Is Empty\n";

else

{

      do

      {

            cout<<"\t"<<temp‒>data;

            temp = temp‒>next;   //  The next node of last node is head node

      }while(temp = head);/*Circular linked list*/

}

getch();

}

 

3. Insertion of circular linked list

While inserting a node in the linked list, there are 3 cases ‒

a) inserting a node as a head node

b) inserting a node as a last node

c) inserting a node at intermediate position

The functions for these cases is as given below ‒

void sll::insert head()

{

node *New,*temp;

New = new node;

New‒>next=NULL;

cout<<"\n Enter The element which you want to insert

cin>>New‒>data;

if(head= =NULL)

      head=New;

else

{

      temp = head;

      while(temp‒>next!=head)

      temp=temp‒>next;

      temp‒>next=New;

      New‒>next = head;

      head=New;

      cout<<"\n The node is inserted!";

}

}

/*Insertion of node at last position*/

void sll::insert_last()

{

      node *New,*temp;

      New = new node;

      New‒>next=NULL;

      cout<<"\n Enter The element which you want to insert

      cin>>New‒>data;

      if(head= = NULL)

      head=New;

      else

      {

            temp=head;

            while(temp‒>next!=head)

            temp=temp‒>next;

            temp‒>next=New;

            New‒>next = head;

            cout<<"\n The node is inserted!";

      }

}

void sll::insert_after()

{

      int key;

      node *New,*temp;

      New = new node;

      New‒>next=NULL;

      cout<<"\n Enter The element which you want to insert":

      cin>>New‒>data;

      if(head= = NULL)

      {

            head=New;

      }

      else

      {

            cout<<"\n Enter The element after which you want to insert the node":

            cin>>key;

            temp=head;

      do

      {

      if(temp‒>data= =key)

      {

            New‒>next = temp‒>next;

            temp‒>next=New;

            cout<<"\n The node is inserted";

            return;

      }

      else

            temp=temp‒>next;

      }while(temp!=head);

}

}

Suppose linked list is already created as ‒

If we want to insert a New node as a head node then,

Then

temp → next = New;

New → next = head;

head = New;

If we want to insert a New node as a last node consider a linked list

If we want to insert an element 35 after node 30 then,

As key = 30

and temp→ data = 30

New → next = temp → next;

temp→ next = New;

 

4. Deletion of any node

void sll::Delete()

{

int key;

struct node *temp, *temp1;

cout<<"\n Enter the element which is to be deleted";

cin>>key;

temp=head;

if(temp‒>data= =key)/*If header node is to be deleted*/

{

temp1=temp‒>next;

if(temp1= =temp)   //If a single node is present in the list and we want to delete it

/*if single node is present in circular linked list and we want to delete it*/

{

      temp=NULL;

      head=temp;

      cout<<"\n The node is deleted";

}

else /*otherwise*/

{

      while(temp‒>next!=head)

      temp=temp‒>next;/*searching for the last node*/

      temp‒>next=temp1;

      head=temp1;/*new head*/

      cout<<"\n The node is deleted";

}

}

else

{

      while(temp‒>next!=head) /* if intermediate node is to be deleted*/

{

if((temp‒>next)‒>data= =key)     // The previous node of the node to be deleted is searched. Here temp 1 is the node to be deleted and temp is the previous node of temp 1

{

      temp1=temp‒>next;

      temp‒>next=temp1‒>next;

      temp1‒>next=NULL;

      delete temp1;

      cout<<"\n The node is deleted";

}

else

      temp=temp‒>next;

}

}

}

 

Suppose we have created a linked list as,

If we want to delete temp→ data i.e. node 10 then,

If we want to delete an intermediate node from a linked list which is given below

Now

Then delete temp1; /* to deallocate memory */

The linked list can be ‒

Thus node with value 30 is deleted from CLL.

 

5. Searching a node from circular linked list

void sll::Search(int num)

{

node *temp;

int found;

temp=head;

if ( temp = = NULL)

{

      cout<<"The Linked List is empty\n";

      getch();

      clrscr();

}

found=0;

while(temp‒>next!=head && found = =0)

{

      if(temp‒>data = = num)

            found=1;/*if node is found*/

      else

            temp=temp‒>next;

}

if(found = =1)

{

      cout<<"\n The node is present";

      getch();

}

else

{

      cout<<"\n The node is not present";

      getch();

}

}

while searching a node from circular linked list we go on comparing the data field of each node starting from the head node. If the node containing desired data is found we declare that the node is present.

'C++' Program

/*

***************************************************************************

Program To Perform The Various Operations On The Circular Linked List

**************************************************************************

*/

#include<iostream>

#include<cstdlib>

using namespace std;

class sll

{

private:

struct node

{

      int data;

      struct node *next;

}*head;

public:

sll();

void Create();

void Display();

void Search(int key);

void insert head();

void insert_after();

void insert_ last();

void Delete();

~sll();

};

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Constructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

sll::sll()

head=NULL;//initialize head to NULL

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Destructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

sll::~sll()

{

node *temp, *temp1;

temp = head‒>next;

delete head;

while(temp!= NULL) //free the memory allocated

{

temp1= temp‒>next;

delete temp;

temp = temp1;

}

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Create function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void sll::Create()

{

char ans;

int flag=1;

node *New,*temp;

clrscr();

do

{

      New = new node;

      New‒>next=NULL;

      cout<<"\n\n\n\tEnter The Element\n";

      cin>>New‒>data;

      if(flag= =1)        /*flag for setting the starting node*/

      {

            head = New;

            New‒>nexthead; /*the circular list of a single node*/

            flag=0;/*reset flag*/

      }

      else        /* find last node in list */

      {

            temp=head;

            while (temp‒>next != head)/*finding the last node*/

             temp=temp‒>next; /*temp is a last node */

            temp‒>next=New;

            New‒>next‒head; /*each time making the list circular*/

      }

cout<<"\n Do you want to enter more nodes?(y/n)";

ans=getch();

}while(ans= ='y' || ans = = 'Y');

}

void sll::Display()

{

      node *temp;

      temp= head;

      if(temp = = NULL)

      cout<<"\n Sorry,The List Is Empty\n";

      else

      {

      do

      {

            cout<<"\t"<<temp‒>data;

            temp =  temp‒>next;

      }while(temp = head);/*Circular linked list*/

}

getch();

}

void sll::insert_head()

{

   node *New,*temp;

   New = new node;

   New‒>next=NULL;

   cout<<"\n Enter The element which you want to insert ";

   cin>>New‒>data;

   if(head= =NULL)

   head=New;

   else

   {

   temp = head;

   while(temp‒>next!=head)

   temp =temp‒>next;

   temp‒>next=New;

   New‒>next=head;

   head=New;

   cout<<"\n The node is inserted!";

   }

}/*Insertion of node at last position*/

void sll::insert_last()

{

   node *New,*temp;

   New‒>next=NULL;

   cout<<"\n Enter The element which you want to insert";

   cin>>New‒>data;

   if(head= NULL)

   head=New;

   else

   {

      temp=head;

      while(temp‒>next!=head)

      temp = temp‒>next;

      temp‒>next=New;

      New‒>next=head;

      cout<<"\n The node is inserted!";

   }

}

void sll::insert after()

{

   int key;

   node *New,*temp;

   New= new node;

   New‒>next=NULL;

   cout<<"\n Enter The element which you want to insert ";

   cin>>New‒>data;

   if(head= =NULL)

   {

      head=New;

   }

   else

   {

      cout<<"\n Enter The element after which you want to insert the node ";

      cin>>key;

      temp = head;

   do

   {

      if(temp‒>data= =key)

      {

         New‒>next‒temp‒>next;

         temp‒>next=New;

         cout<<"\n The node is inserted";

         return;

      }

      else

         temp=temp‒>next;

      }while(temp!=head);                    

   }

}

void sll::Search(int num)

{

   node *temp;

   int found;

   temp=head;

   if ( temp = = NULL)

   {

      cout<<"The Linked List is empty\n";

      getch();

      clrscr();

   }

   found=0;

   while(temp‒>next!=head && found = = 0)

   {

      if(temp‒>data = = num)

      found=1;/*if node is found*/

      else

      temp = temp‒>next;

   }

   if(found =1)

   {

      cout<<"\n The node is present";

      getch();

   }

   else

   {

      cout<<"\n The node is not present";

      getch();

   }

}

void sll::Delete()

{

   int key;

   struct node *temp, *temp1;

   cout<<"\n Enter the element which is to be deleted":

   cin>>key;

   temp = head;

   if(temp‒>data= =key)/*If header node is to be deleted*/

   {

      temp1= temp‒>next;

      if(temp1= = temp)

      /*if single node is present in circular linked list and we want to delete it*/

      {

         temp=NULL;

         head=temp;

         cout<<"\n The node is deleted";

      }

      else /*otherwise*/

      {

         while(temp‒>next!=head)

         temp=temp‒>next;/*searching for the last node*/

         temp‒>next=temp1;

         head=temp1;/*new head*/

         cout<<"\n The node is deleted";

      }

   }

else

{

while(temp‒>next!=head) /*    if intermediate node is to be deleted*/

{

if((temp‒>next)‒>data= =key)

{

   templ=temp‒>next;

   temp‒>next=temp1‒>next;

   temp1‒>next=NULL;

   delete temp1;

   cout<<"\n The node is deleted";

}

else

   temp=temp‒>next;

}

}

}

void main()

{

sll s;

char ch='y';

int num,choice,choice1;

do

{

   clrscr();

   cout<<"\n Program For Circular Linked List\n";

   cout<<"1.Insertion of any node\n\n";

   cout<<"2. Display of Circular List\n\n";

   cout<<"3. Insertion of a node in Circular List\n\n";

   cout<<" 4. Deletion of any node \n\n";

   cout<<" 5. Searching a Particular Element in The List\n\n";

   cout<<" 6.Exit ";

   cout<<"\n Enter Your Choice":

   cin>>choice;

   switch(choice)

   {

      case 1 :s.Create();

            break;

      case 2 :s.Display();

            break;

      case 3; cout<<"\n 1. Insert a node as a head node";

      cout<<"\n 2. Insert a node as a last node";

      cout<<"\n 3. Insert a node at intermediate position in the linked list":

      cout<<"\n Enter your choice for insertion of node";

      cin>>choice1;

      switch(choice1)

      {

         case 1:s.insert_head();

              break;

         case 2:s.insert_last();

               break;

         case 3:s.insert_after();

               break;

      }

            break;

      case 4:s.Delete();

            break;

      case 5:cout<<"\n Enter The Element Which Is To Be Searched ";

            cin>>num;

            s.Search(num);

      break;

      case 6:exit(0);

      }

   cout<<"\nDo you want to go to Main Menu?\n";

   ch = getch();

  }while(ch = = 'y' || ch = = 'Y');

}

Output

Program For Circular Linked List

1.Insertion of any node

2. Display of Circular List

3. Insertion of a node in Circular List

4. Deletion of any node

5. Searching a Particular Element in The List

6.Exit

Enter Your Choice 1

Enter The Element

10

 Do you want to enter more nodes?(y/n)

Enter The Element

20

Do you want to enter more nodes?(y/n)

Enter The Element

30

Do you want to enter more nodes?(y/n)

Enter The Element

40

Do you want to enter more nodes?(y/n)

Do you want to go to Main Menu?

Program For Circular Linked List

1.Insertion of any node

2. Display of Circular List

3. Insertion of a node in Circular List

4. Deletion of any node

5. Searching a Particular Element in The List

6.Exit

Enter Your Choice 2

10      20        30         40

 

Example : 1

Design an algorithm to split a circular list into two circular lists.

Solution :

void Split CLL(node *head)

{

node *temp, *head1,*head2;

temp = head;

int count,n;

int mid;

n=1;

while(temp‒>next!=head)

{

   n++://denotes total number of nodes in CLL

   temp=temp‒>next;

}

mid=n=n/2;

head1=new node;

head2=new node;

head1=temp;

while(count<=mid)

{

   temp = temp‒>next;

   count++;

}

head2=temp‒>next;

temp‒>next=head1; //making first split circular

temp=head2;

while(count< = n)

{

   temp=temp‒>next;

   count++;

}

temp‒>next=head2; //making second split circular

 

Review Question

1. Implement insertion, deletion and search operations in single linked list.