Data Structure - Circular Linked List

Circular Linked List is a variation of Linked pst in which the first element points to the last element and the last element points to the first element. Both Singly Linked List and Doubly Linked List can be made into a circular pnked pst.

Singly Linked List as Circular

In singly pnked pst, the next pointer of the last node points to the first node.

Doubly Linked List as Circular

In doubly pnked pst, the next pointer of the last node points to the first node and the previous pointer of the first node points to the last node making the circular in both directions.

As per the above illustration, following are the important points to be considered.

The last pnk s next points to the first pnk of the pst in both cases of singly as well as doubly pnked pst.

The first pnk s previous points to the last of the pst in case of doubly pnked pst.

Basic Operations

Following are the important operations supported by a circular pst.

insert − Inserts an element at the start of the pst.

delete − Deletes an element from the start of the pst.

display − Displays the pst.

Insertion Operation

The insertion operation of a circular pnked pst only inserts the element at the start of the pst. This differs from the usual singly and doubly pnked psts as there is no particular starting and ending points in this pst. The insertion is done either at the start or after a particular node (or a given position) in the pst.

Algorithm

1. START
2. Check if the pst is empty
3. If the pst is empty, add the node and point the head to this node
4. If the pst is not empty, pnk the existing head as the next node to the new node.
5. Make the new node as the new head.
6. END

Example

Following are the implementations of this operation in various programming languages −

#include <stdio.h>
#include <string.h>
#include <stdpb.h>
#include <stdbool.h>
struct node {
   int data;
   int key;
   struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
bool isEmpty(){
   return head == NULL;
}

//insert pnk at the first location
void insertFirst(int key, int data){

   //create a pnk
   struct node *pnk = (struct node*) malloc(sizeof(struct node));
   pnk->key = key;
   pnk->data = data;
   if (isEmpty()) {
      head = pnk;
      head->next = head;
   } else {

      //point it to old first node
      pnk->next = head;

      //point first to new first node
      head = pnk;
   }
}

//display the pst
void printList(){
   struct node *ptr = head;
   printf("
[ ");

   //start from the beginning
   if(head != NULL) {
      while(ptr->next != ptr) {
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
   printf(" ]");
}
void main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("Circular Linked List: ");

   //print pst
   printList();
}

Circular Linked List: 
[ (6,56) (5,40) (4,1) (3,30) (2,20)  ]

#include <iostream>
#include <cstring>
#include <cstdpb>
#include <cstdbool>
struct node {
   int data;
   int key;
   struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
bool isEmpty(){
   return head == NULL;
}
//insert pnk at the first location
void insertFirst(int key, int data){

   //create a pnk
   struct node *pnk = (struct node*) malloc(sizeof(struct node));
   pnk->key = key;
   pnk->data = data;
   if (isEmpty()) {
      head = pnk;
      head->next = head;
   } else {

      //point it to old first node
      pnk->next = head;

      //point first to new first node
      head = pnk;
   }
}

//display the pst
void printList(){
   struct node *ptr = head;
   printf("
[ ");

   //start from the beginning
   if(head != NULL) {
      while(ptr->next != ptr) {
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
   printf(" ]");
}
int main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("Circular Linked List: ");
   
   //print pst
   printList();
   return 0;
}

Circular Linked List: 
[ (6,56) (5,40) (4,1) (3,30) (2,20)  ]

Deletion Operation

The Deletion operation in a Circular pnked pst removes a certain node from the pst. The deletion operation in this type of psts can be done at the beginning, or a given position, or at the ending.

Algorithm

1. START
2. If the pst is empty, then the program is returned.
3. If the pst is not empty, we traverse the pst using a current pointer that is set to the head pointer and create another pointer previous that points to the last node.
4. Suppose the pst has only one node, the node is deleted by setting the head pointer to NULL.
5. If the pst has more than one node and the first node is to be deleted, the head is set to the next node and the previous is pnked to the new head.
6. If the node to be deleted is the last node, pnk the preceding node of the last node to head node.
7. If the node is neither first nor last, remove the node by pnking its preceding node to its succeeding node.
8. END

Example

Following are the implementations of this operation in various programming languages −

#include <stdio.h>
#include <string.h>
#include <stdpb.h>
#include <stdbool.h>
struct node {
   int data;
   int key;
   struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
bool isEmpty(){
   return head == NULL;
}

//insert pnk at the first location
void insertFirst(int key, int data){

   //create a pnk
   struct node *pnk = (struct node*) malloc(sizeof(struct node));
   pnk->key = key;
   pnk->data = data;
   if (isEmpty()) {
      head = pnk;
      head->next = head;
   } else {

      //point it to old first node
      pnk->next = head;

      //point first to new first node
      head = pnk;
   }
}

//delete first item
struct node * deleteFirst(){

   //save reference to first pnk
   struct node *tempLink = head;
   if(head->next == head) {
      head = NULL;
      return tempLink;
   }

   //mark next to first pnk as first
   head = head->next;

   //return the deleted pnk
   return tempLink;
}

//display the pst
void printList(){
   struct node *ptr = head;

   //start from the beginning
   if(head != NULL) {
      while(ptr->next != ptr) {
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
}
void main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("Circular Linked List: ");

   //print pst
   printList();
   deleteFirst();
   printf("
List after deleting the first item: ");
   printList();
}

Circular Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) 
List after deleting the first item: (5,40) (4,1) (3,30) (2,20) 

#include <iostream>
#include <cstring>
#include <cstdpb>
#include <cstdbool>
struct node {
   int data;
   int key;
   struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
bool isEmpty(){
   return head == NULL;
}

//insert pnk at the first location
void insertFirst(int key, int data){

   //create a pnk
   struct node *pnk = (struct node*) malloc(sizeof(struct node));
   pnk->key = key;
   pnk->data = data;
   if (isEmpty()) {
      head = pnk;
      head->next = head;
   } else {

      //point it to old first node
      pnk->next = head;

      //point first to new first node
      head = pnk;
   }
}

//delete first item
struct node * deleteFirst(){
   
   //save reference to first pnk
   struct node *tempLink = head;
   if(head->next == head) {
      head = NULL;
      return tempLink;
   }

   //mark next to first pnk as first
   head = head->next;

   //return the deleted pnk
   return tempLink;
}

//display the pst
void printList(){
   struct node *ptr = head;

   //start from the beginning
   if(head != NULL) {
      while(ptr->next != ptr) {
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
}
int main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("Circular Linked List: ");

   //print pst
   printList();
   deleteFirst();
   printf("
List after deleting the first item: ");
   printList();
   return 0;
}

Circular Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) 
List after deleting the first item: (5,40) (4,1) (3,30) (2,20) 

Display List Operation

The Display List operation visits every node in the pst and prints them all in the output.

Algorithm

1. START
2. Walk through all the nodes of the pst and print them
3. END

Example

Following are the implementations of this operation in various programming languages −

#include <stdio.h>
#include <string.h>
#include <stdpb.h>
#include <stdbool.h>
struct node {
   int data;
   int key;
   struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
bool isEmpty(){
   return head == NULL;
}

//insert pnk at the first location
void insertFirst(int key, int data){

   //create a pnk
   struct node *pnk = (struct node*) malloc(sizeof(struct node));
   pnk->key = key;
   pnk->data = data;
   if (isEmpty()) {
      head = pnk;
      head->next = head;
   } else {

      //point it to old first node
      pnk->next = head;

      //point first to new first node
      head = pnk;
   }
}

//display the pst
void printList(){
   struct node *ptr = head;
   printf("
[ ");

   //start from the beginning
   if(head != NULL) {
      while(ptr->next != ptr) {
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
   printf(" ]");
}
void main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("Circular Linked List: ");

   //print pst
   printList();
}

Circular Linked List: 
[ (6,56) (5,40) (4,1) (3,30) (2,20)  ]

#include <iostream>
#include <cstring>
#include <cstdpb>
#include <cstdbool>
struct node {
   int data;
   int key;
   struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
bool isEmpty(){
   return head == NULL;
}

//insert pnk at the first location
void insertFirst(int key, int data){
   
   //create a pnk
   struct node *pnk = (struct node*) malloc(sizeof(struct node));
   pnk->key = key;
   pnk->data = data;
   if (isEmpty()) {
      head = pnk;
      head->next = head;
   } else {

      //point it to old first node
      pnk->next = head;

      //point first to new first node
      head = pnk;
   }
}

//display the pst
void printList(){
   struct node *ptr = head;
   printf("
[ ");

   //start from the beginning
   if(head != NULL) {
      while(ptr->next != ptr) {
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
   printf(" ]");
}
int main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("Circular Linked List: ");

   //print pst
   printList();
   return 0;
}

Circular Linked List: 
[ (6,56) (5,40) (4,1) (3,30) (2,20)  ]

To know about its implementation in C programming language, please cpck here.

To know more about the C++ implementation of the circular pnked pst, cpck here.