Circular Linked List in C++

Circular linked list in C++

What is a circular linked list in C++?

The circular linked list in C++ is another data structure, which is an enhancement of the linked list data structure. As we have studied that the linked list is a data structure in which every node in the list has the link of its next node and the last node is pointing to null. Similarly, in the circular linked list, every node has the link to its next node and the last node does not point to null like a linked list rather it points to the head of the list. 

Why Circular Linked List?

Traversing the list becomes easy

Entire list can be traversed from any node of the list as it forms a loop like structure. Going form last node to first node is just a single step process because of this.

Implementation of advance data structure

Circular linked list are used for the implementation of advance data structures like queues, etc.

Useful in applications that go around in a loop

Developing the applications that never ends or always go around in a loop become easy using circular linked list.

STRUCTURE

STRUCTURE

Structure of circular linked list

Circular linked can be of both singly and doubly type. So they can be defined in a program by using following set of code.

  • Singly circular linked list is :-
    struct node
    {
       int data;
       struct node *next;
    }
  • Doubly circular linked list is:-
    struct node   
    {  
    struct node *prev;
    int data;
    struct node *next;  
    }   
Circular Linked List in C++

Operation on circular linked list in C++

We can perform following operations on a circular linked list.

  • Counting the nodes
  •  Insertion
    • Inserting at Beginning of the list.
    • Inserting at End of the list.
    • Inserting at Specific location in the list.
  • Deletion
    • Deleting from Beginning of the list.
    • Deleting from End of the list.
    • Deleting a Specific Node from the list
  • Splitting a list into two halves
  • Sorted insertion in the list

C++ programming code for creating a circular linked list

#include <stdio.h>
#include <stdlib.h>

struct node {
    int num;
    struct node * nextptr;
}*startnode;
 

void creation(int n);
void display();

int main() //main method
{
    int n;
    startnode = NULL;

    printf("Enter the number of nodes : ");
    scanf("%d", &n);
 
    creation(n); 
    display();
    return 0;
}

void creation(int n)//function to create list
{
    int i, num;
    struct node *preptr, *newnode;

    if(n >= 1)
    {
        startnode = (struct node *)malloc(sizeof(struct node));

        printf("Enter data for node 1 : ");
        scanf("%d", &num);
        startnode->num = num;
        startnode->nextptr = NULL;
        preptr = startnode;
        for(i=2; i<=n; i++)
        {
            newnode = (struct node *)malloc(sizeof(struct node));
            printf("Enter data for node %d : ", i);
            scanf("%d", &num);
            newnode->num = num;
            newnode->nextptr = NULL;	
            preptr->nextptr = newnode;	
            preptr = newnode;   		
        }
        preptr->nextptr = startnode; 		
    }
}

void display() //function to display list 
{
    struct node *tmp;
    int n,i;

    if(startnode == NULL)
    {
        printf("List is empty");
    }
    else
    {
        tmp = startnode;
        printf("\nData entered in the list are :\n");

      do {
            printf("Node %d : %d\n", n, tmp->num);

            tmp = tmp->nextptr;
            n++;
        }while(tmp != startnode);
    }
}
Output:
Enter the number of nodes : 5
Enter data for node 1 : 11
Enter data for node 2 : 22
Enter data for node 3 : 33
Enter data for node 4 : 44
Enter data for node 5 : 55

Data entered in the list are :
Node 0 : 11
Node 1 : 22
Node 2 : 33
Node 3 : 44
Node 4 : 55

Disadvantages of circular linked list in C++

  1. To insert node at the beginning we have to traverse till the last node, hence insertion at the beginning becomes a lengthy task.
  2. End of the list does not point to NULL so it becomes harder to find the last node.
  3. Circular linked list could end up in infinite loop if not traversed correctly.
  4. Reversing a circular linked list is quite a difficult task when compared with singly and doubly linked list.