Circular Linked List
Circular Linked List
A circular linked list where all nodes are connected to their next node and last node is connected to the starting node or we can say all nodes are connected in circular fashion to form a circle. In circular linked list, there is no null node at the end. There are two types of circular linked that can be singly circular linked list or doubly circular linked list.
Why we use Circular Linked List
- In circular linked list, any node can be a starting point. We can traverse the entire list by any point and stop when we revisit the starting point.
- By circular linked list, we can implement the queue. In queue, we have to maintain two pointers for front and rear but in circular linked list we don’t need to have these pointers.
- It is used to implement the advanced data structure like Fibonacci Heap
Operations on Circular Linked List: -
- Insert a node in the linked list:
We can insert a node into the linked list at the front, the end or anywhere in the linked list. The time complexity of these operations is as follows:
- If we insert the node at the front of linked list; takes O(1)
- If we insert the node at the end of linked list; takes O(n)
- If we insert the node anywhere in the linked list; takes O(n)
- Remove a node from the linked list:
We can remove a node from the linked list from the front, the end or anywhere of the linked list. The time complexity of these operations is as follows:
- If we remove the node from the front of linked list; takes O(1).
- If we remove the node from the end of linked list; takes O(n)
- If we remove the node from anywhere in the linked list; takes O(n)
- Search a node in the linked list:
Searching a node in the linked list takes O(n) time in the worst case.
Note: - In circular linked list, if we take starting address of the list then the time complexity will be increased for inserting a node at the end of the list and if we take last address of the list then inserting a node at the end of linked list takes constant time e.g. O(1).
Circular Linked List Program in C Language: -
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void insertAtBeginning(int);
void insertAtEnd(int);
void insertAfter(int,int);
void deleteBeginning();
void deleteEnd();
void deleteSpecific(int);
void display();
struct Node
{
int data;
struct Node *next;
}*head = NULL;
void main()
{
int n,pos,item;
while(1)
{
printf(" 1. insert at begin");
printf("\n 2. insert at specific position");
printf("\n 3. insert at End");
printf("\n 4. delete at beginning");
printf("\n 5. delete specific position");
printf("\n 6. delete at End");
printf("\n 7. Traverse the list");
printf("\n 8.Exit\n");
printf("Enter the choice:-\n");
scanf("%d",&n);
switch(n)
{
case 1:
printf("Enter the item do wanna insert:-\n");
scanf("%d",&item);
insertAtBeginning(item);
break;
case 2:
printf("Enter the position where do wanna insert:-\n");
scanf("%d",&pos);
printf("Enter the item do wanna insert at position:-\n");
scanf("%d",&item);
insertAfter(item,pos);
break;
case 3:
printf("Enter the item do wanna insert at end:-\n");
scanf("%d",&item);
insertAtEnd(item);
break;
case 4:
deleteBeginning();
break;
case 5:
printf("Enter the item which do wanna delete :-\n");
scanf("%d",&item);
deleteSpecific(item);
break;
case 6:
deleteEnd();
break;
case 7:
printf("your list is:");
display();
break;
case 8:
exit(0);
}
}
}
void insertAtBeginning(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode -> data = value;
if(head == NULL)
{
head = newNode;
newNode -> next = head;
}
else
{
struct Node *temp = head;
while(temp -> next != head)
temp = temp -> next;
newNode -> next = head;
head = newNode;
temp -> next = head;
}
}
void insertAtEnd(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode -> data = value;
if(head == NULL)
{
head = newNode;
newNode -> next = head;
}
else
{
struct Node *temp = head;
while(temp -> next != head)
temp = temp -> next;
temp -> next = newNode;
newNode -> next = head;
}
}
void insertAfter(int value, int location)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode -> data = value;
if(head == NULL)
{
head = newNode;
newNode -> next = head;
}
else
{
struct Node *temp = head;
while(temp -> data != location)
{
if(temp -> next == head)
{
printf("Given node is not found in the list !!!");
}
else
{
temp = temp -> next;
}
}
newNode -> next = temp -> next;
temp -> next = newNode;
printf("\nInsertion success!!!");
}
}
void deleteBeginning()
{
if(head == NULL)
printf("List is Empty!!! Deletion not possible !!!");
else
{
struct Node *temp = head;
if(temp -> next == head)
{
head = NULL;
free(temp);
}
else{
head = head -> next;
free(temp);
}
printf("\nDeletion success!!!");
}
}
void deleteEnd()
{
if(head == NULL)
printf("List is Empty!!! Deletion not possible !!!");
else
{
struct Node *temp1 = head, *temp2;
if(temp1 -> next == head)
{
head = NULL;
free(temp1);
}
else{
while(temp1 -> next != head){
temp2 = temp1;
temp1 = temp1 -> next;
}
temp2 -> next = head;
free(temp1);
}
printf("\nDeletion success!!!");
}
}
void deleteSpecific(int delValue)
{
if(head == NULL)
printf("List is Empty!!! Deletion not possible!!!");
else
{
struct Node *temp1 = head, *temp2;
while(temp1 -> data != delValue)
{
if(temp1 -> next == head)
{
printf("\nGiven node is not found in the list !!!");
}
else
{
temp2 = temp1;
temp1 = temp1 -> next;
}
}
if(temp1 -> next == head){
head = NULL;
free(temp1);
}
else{
if(temp1 == head)
{
temp2 = head;
while(temp2 -> next != head)
temp2 = temp2 -> next;
head = head -> next;
temp2 -> next = head;
free(temp1);
}
else
{
if(temp1 -> next == head)
{
temp2 -> next = head;
}
else
{
temp2 -> next = temp1 -> next;
}
free(temp1);
}
}
printf("\nDeletion success !!!");
}
}
void display()
{
if(head==NULL)
{
printf(" Linked list is empty\n");
}
struct Node *temp=head;
while(temp -> next!=head)
{
printf("%d -> ",temp -> data);
temp=temp -> next;
}
printf("%d\n",temp-> data);
}
Output
Applications of the Circular Linked List
- It is used to implement round-robin algorithm in operating system
- It is used in token-ring scheduling in computer networks