Circular Linked List In C
A circular linked list is a list in which each node is connected in turn and always points to the head (first) node of the linked list. In a singly or doubly linked list, the final node often contains NULL, signifying the list's conclusion.
However, because the last node always points to the list's first node, circular linked lists lack any endpoints.
We must use beware when navigating circular linked lists in order to prevent further traversing the list. The fact that each node in circularly linked lists has a subsequent node in a linear sequence rather than any nodes with a NULL pointer should be underlined. This is in contrast to conventionally linked lists.
Mainly two types of Circular Linked Lists are there. They are:
1. Singly Circular Linked List
2. Doubly Circular Linked List
Singly Circular Linked List:
A circular singly linked list has nodes that each have a data block and a next block that has the address of the node after it. The address of the first (head) node is contained in the block immediately after that of the last node.
Syntax:
struct node{
data_type data_value;
struct node* next;
};
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c1.png)
Doubly Circular Linked List:
In a circular doubly linked list, each node comprises a data block, a block for storing addresses of the preceding and following nodes, and a block for storing addresses of the node after it.
The first (head) node contains the address of the final node in the preceding block, and the last node has the address of the first (head) node in the following block.
Syntax:
struct node{
data_type data_value;
struct node* next;
struct node* prev;
};
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c2.png)
Implementation of various operations of Circular Linked List:
1. Inserting a new node in the beginning:
To add a node to the starting circular linked list, follow the instructions below:
- You need to construct a temporary variable before you can assign a new node to it.
- If our list is empty (head is NULL), provide the new node's head pointer and next pointer the address of the new node.
- If the list is not empty, the head node's address should be allocated to a new current variable before traversing the list. Give the new node the (current) address of the previous node.
- The head pointer will be modified to point at the new node once the head node's address is assigned to the new node's next block, causing it to point to the first node that already exists.
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c3.png)
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
// Programme code for adding a new node
struct node* Node_Create()
{
struct node *n;
n = (struct node*)malloc(sizeof(struct node));
return n;
}
void Node_Insertion_begin(struct node** head, int data)
{
struct node* temp, *curr;
//Establishing a new node
temp = Node_Create();
temp->data = data;
temp->next = NULL;
//list is empty
if(*head == NULL)
{
*head = temp;
temp->next = *head;
return;
}
//If there are already multiple nodes in the list.
curr = *head;
while(curr->next != *head)
{
curr = curr->next;
}
curr->next = temp;
temp->next = *head;
*head = temp;
return;
}
// code for output that shows the list
void display(struct node** head)
{
struct node *temp;
//If the list is empty
if(*head == NULL)
{
printf("List is empty.\n");
return;
}
else
{
// if there are one or more nodes in the list.
temp = *head;
printf("List: ");
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while(temp != *head);
}
}
int main()
{
struct node* head = NULL;
Node_Insertion_begin(&head, 6);
Node_Insertion_begin(&head, 5);
Node_Insertion_begin(&head, 4);
Node_Insertion_begin(&head, 3);
Node_Insertion_begin(&head, 2);
Node_Insertion_begin(&head, 1);
display(&head);
return 0;
}
OUTPUT:
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c4.png)
2. Inserting a new node in the end:
The below steps can be used for the addition of a node to the end of the circular linked list:
- To a temporary variable, create a new node and assign it to it.
- The address of the new node should be assigned to the head pointer and the next pointer if our list is empty (the head is NULL).
- A new current variable should be set to the head node address if the list is not empty in order to traverse it. The final node (current) will receive the address of the new node.
- Assign the address of the head node to the new node's next block so that it will now point to the current first node.
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c5.png)
//Inserting node at the end of the list
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
// Programme code for adding a new node
struct node* Node_Create()
{
struct node *n;
n = (struct node*)malloc(sizeof(struct node));
return n;
}
void Node_Insertion_end(struct node** head, int data)
{
struct node* temp, *curr;
//Establishing a new node
temp = Node_Create();
temp->data = data;
temp->next = NULL;
//list is empty
if(*head == NULL)
{
*head = temp;
temp->next = *head;
return;
}
//If there are already multiple nodes in the list.
curr = *head;
while(curr->next != *head)
{
curr = curr->next;
}
curr->next = temp;
temp->next = *head;
}
// code for output that shows the list
void display(struct node** head)
{
struct node *temp;
//If the list is empty
if(*head == NULL)
{
printf("List is empty.\n");
return;
}
else
{
// if there are one or more nodes in the list.
temp = *head;
printf("List: ");
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while(temp != *head);
}
}
int main()
{
struct node* head = NULL;
Node_Insertion_end(&head, 1);
Node_Insertion_end(&head, 10);
Node_Insertion_end(&head, 4);
Node_Insertion_end(&head, 8);
Node_Insertion_end(&head, 9);
Node_Insertion_end(&head, 6);
display(&head);
return 0; }
OUTPUT:
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c6.png)
3. Inserting a new node at any point:
Following the steps listed below, we can add a node to the circular linked list after a certain element:
- Assign a new node to a new node variable.
- Create a new temporary variable, assign the head node address to it, then iterate the list until the next node contains the desired value.
- Give the new node variable the address of the following node.
- Change the next block address of the existing node to point to the new node.
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c7.png)
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
// Programme code for adding a new node
struct node* Node_Create()
{
struct node *n;
n = (struct node*)malloc(sizeof(struct node));
return n;
}
void Node_Insertion_end(struct node** head, int data)
{
struct node* temp, *curr;
//Establishing a new node
temp = Node_Create();
temp->data = data;
temp->next = NULL;
//list is empty
if(*head == NULL)
{
*head = temp;
temp->next = *head;
return;
}
//If there are already multiple nodes in the list.
curr = *head;
while(curr->next != *head)
{
curr = curr->next;
}
curr->next = temp;
temp->next = *head;
return;
}
void insertAtpoint(struct node** head, int data, int value){
struct node* temp, *newnode
// new node creation
new node = Node_Create();
newnode->data = data;
new node->next = NULL;
//traversing list until an element is found
temp = *head;
while(temp->data != value){
temp = temp->next;
}
// adding the newNode b/w the "value" data node and next node.
new node->next = temp->next;
temp->next = new node;
return;
}
// code for output that shows the list
void display(struct node** head)
{
struct node *temp;
//If the list is empty
if(*head == NULL)
{
printf("List is empty.\n");
return;
}
else
{
// if there are one or more nodes in the list.
temp = *head;
printf("List: ");
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while(temp != *head);
}
printf("\n");
}
int main()
{
struct node* head = NULL;
Node_Insertion_end(&head, 3);
Node_Insertion_end(&head, 6);
Node_Insertion_end(&head, 4);
Node_Insertion_end(&head, 8);
Node_Insertion_end(&head, 7);
Node_Insertion_end(&head, 2);
display(&head);
insertAtpoint(&head,12,4);
display(&head);
return 0;
}
OUTPUT:
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c8.png)
4. Deleting node at the beginning:
We can remove the first node from a circular linked list in C:
- If the list only contains one node, use the free () function to explicitly remove the head node from the list.
- The head address should be placed in two temporary variables that you create.
- To assign the head's next node address to the last node, move along the list to the last node.
- Refresh the head pointer to point to the following node.
- Release the temporary variable that still refers to the root node.
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c9.png)
#include<stdio.h>
#include<stdlib.h>
struct node
//If there are already multiple nodes in the list.
curr = *head;
while(curr->next != *head)
{
curr = curr->next;
}
curr->next = temp;
temp->next = *head;
return;
}
// deleting a node
void delete_First(struct node** head){
struct node* temp = *head;
struct node* curr = *head;
if(*head == NULL)
{
printf("List empty.");
return;
}
else if((*head)->next == *head)
{
*head = NULL;
free(temp);
return;
}
while(curr->next != *head){
curr = curr->next;
}
curr->next = (*head)->next;
*head = (*head)->next;
free(temp);
return;
}
// code for output that shows the list
void display(struct node** head)
{
struct node *temp;
//If the list is empty
if(*head == NULL)
{
printf("List is empty.\n");
return;
}
else
{
// if there are one or more nodes in the list.
temp = *head;
printf("List: ");
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while(temp != *head);
}
printf("\n");
}
int main()
{
struct node* head = NULL;
Node_Insertion_end(&head, 3);
Node_Insertion_end(&head, 6);
Node_Insertion_end(&head, 4);
Node_Insertion_end(&head, 8);
Node_Insertion_end(&head, 7);
Node_Insertion_end(&head, 2);
display(&head);
delete_First(&head);
display(&head);
return 0;
}
OUTPUT:
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c10.png)
5. Deleting node at the end:
- Following the steps below, we can remove the final node from a circular linked list:
- If the list only contains one node, use the free() function to explicitly remove the head node from the list.
- Make two temporary variables, one of which you should store the head address in.
- When you reach the second-to-last node on the list, assign the address of that node to a temporary node variable.
- The head node should now be the second-to-last node's pointer.
- Destroy the temporary variable, which still refers to the final node.
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c11.png)
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
// Programme code for adding a new node
struct node* Node_Create()
{
struct node *n;
n = (struct node*)malloc(sizeof(struct node));
return n;
}
void Node_Insertion_end(struct node** head, int data)
{
struct node* temp, *curr;
//Establishing a new node
temp = Node_Create();
temp->data = data;
temp->next = NULL;
//list is empty
if(*head == NULL)
{
*head = temp;
temp->next = *head;
return;
}
//If there are already multiple nodes in the list.
curr = *head;
while(curr->next != *head)
{
curr = curr->next;
}
curr->next = temp;
temp->next = *head;
*head=temp;
}
// deleting a node
void delete_Last(struct node** head){
struct node* temp;
struct node* curr = *head;
if(*head == NULL)
{
printf("List empty.");
return;
}
while(curr->next->next != *head){
curr = curr->next;
}
temp=curr->next;
curr->next=*head;
free(temp);
return;
}
// code for output that shows the list
void display(struct node** head)
{
struct node *temp;
//If the list is empty
if(*head == NULL)
{
printf("List is empty.\n");
return;
}
else
{
// if there are one or more nodes in the list.
temp = *head;
printf("List: ");
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while(temp != *head);
}
printf("\n");
}
int main()
{
struct node* head = NULL;
Node_Insertion_end(&head, 1);
Node_Insertion_end(&head, 3);
Node_Insertion_end(&head, 5);
Node_Insertion_end(&head, 7);
Node_Insertion_end(&head, 11);
Node_Insertion_end(&head, 17);
display(&head);
delete_Last(&head);
display(&head);
return 0;
}
OUTPUT:
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c12.png)
6. Deleting node at a given point:
Using the following method, we may remove the final node from a circular linked list:
- The procedure for removing the top node from a circular linked list (discussed above) should then be used after determining if the position is first.
- The head address should be placed in one of the temporary variables you create.
- When the preceding node is the one to be deleted, move through the list until that node is in that place. Then, assign the position's next node address to a temporary node variable.
- In order to point to the current node's next node, update the previous node pointer.
- Remove the temporary variable, which still points to the position node.
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c13.png)
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
// Programme code for adding a new node
struct node* Node_Create()
{
struct node *n;
n = (struct node*)malloc(sizeof(struct node));
return n;
}
void Node_Insertion_end(struct node** head, int data)
{
struct node* temp, *curr;
//Establishing a new node
temp = Node_Create();
temp->data = data;
temp->next = NULL;
//list is empty
if(*head == NULL)
{
*head = temp;
temp->next = *head;
return;
}
//If there are already multiple nodes in the list.
curr = *head;
while(curr->next != *head)
{
curr = curr->next;
}
curr->next = temp;
temp->next = *head;
*head=temp;
}
// deleting a node
void delete_At_Position(struct node** head, int pos)
{
if(pos > 6 || pos < 1)
{
printf("Invalid position to delete a node.\n");
return;
}
int i = 1;
struct node *temp, *position;
temp = *head;
if (*head == NULL)
{ // if list is empty
printf("\nList is empty.\n");
}
else
{
printf("Deleting node position: %d\n", pos);
if(pos == 1)
{
position = *head;
while(temp->next != *head)
{
temp = temp->next;
}
temp->next = (*head)->next;
*head = (*head)->next;
free(position);
return;
}
while (i <= pos - 2)
{
temp = temp->next;
i++;
}
position = temp->next;
temp->next = position->next;
free(position);
return;
}
}
// code for output that shows the list
void display(struct node** head)
{
struct node *temp;
//If the list is empty
if(*head == NULL)
{
printf("List is empty.\n");
return;
}
else
{
// if there are one or more nodes in the list.
temp = *head;
printf("List: ");
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while(temp != *head);
}
printf("\n");
}
int main()
{
struct node* head = NULL;
Node_Insertion_end(&head, 1);
Node_Insertion_end(&head, 3);
Node_Insertion_end(&head, 5);
Node_Insertion_end(&head, 7);
Node_Insertion_end(&head, 11);
Node_Insertion_end(&head, 17);
display(&head);
delete_At_Position(&head,5);
display(&head);
return 0;
}
OUTPUT:
![Circular Linked List In C](https://static.tutorialandexample.com/c/circular-linked-list-in-c14.png)
Conclusion:
- The only difference between a circular and regular linked list is that its end node points to its start node and all other nodes are connected sequentially.
- Since the last node always includes the address of the first (head) node, the circular linked lists are circular and lack any ends.
- To avoid endlessly examining the list, we need to be careful when navigating circular linked lists.
- Circular linked lists are used to manage the computational resources on a computer. Implementing stacks and queues can alternatively be done using circular linked lists.