A circular single linked list is a type of linked list where the last node’s next pointer points back to the first node, creating a continuous loop. Unlike a regular singly linked list, there is no NULL pointer at the end, as the list has no true end. Traversal can begin from any node and continue indefinitely until the desired node is found. Circular linked lists are useful in scenarios where continuous looping through data is needed, such as in round-robin scheduling or when managing buffer systems. Additionally, insertion and deletion operations can be efficiently performed at both the beginning and the end of the list.
The structure is same as single linked list.
struct Node {
int data; // data can be any type : int , char, arrays, structures, etc.
struct Node* next; // Pointer to the next node
};Circular Single Linked list
- Entry point
- The head node of the list is the entry point for a circular linked list
- Exit point
- Unlike a regular linked list, there is no node with a
NULLnext pointer to indicate the end. Instead, the exit point is identified when a node’s next pointer points back to the head node.
- Unlike a regular linked list, there is no node with a
Managing nodes in a Circular single linked list
1. Traversing through nodes in list
Traversing through any type of linked list involves starting from the head node and following the next pointers until the end of the list is reached. In a circular linked list, the end is identified when a node’s next pointer points back to the head node.
struct Node *tmp = head; //assigning head node to a temporary pointer
if (tmp != NULL)
printf("list is empty\n");
do {
/* print each node's data */
printf("Data = %d\n", tmp->data);
tmp = tmp->data;
} while (tmp != head);2. Adding a node
Add at the end of list
To add a new node at the end of a circular singly linked list, follow these steps:
- Find the Last Node: Start from the head node and traverse the list by following the next pointers until you reach the node whose next pointer points back to the head. This indicates it is the last node in the circular list.
- Insert the New Node: Create a new node and set its next pointer to point to the head node. Then, update the last node’s next pointer to point to the new node.
void add_tail(struct node **head)
{
struct node *tmp;
struct node *new_node;
int val;
printf("enter a value to insert:");
scanf("%d", &val);
new_node = (struct node*)calloc(1, sizeof(struct node));
new_node->data = val;
new_node->next = *head;
if (*head == NULL) {
new_node->next = new_node;
*head = new_node;
} else {
tmp = *head;
while (tmp->next != *head)
tmp = tmp->next;
tmp->next = new_node;
}
}Add at the beginning
To add a new node at the beginning of a circular singly linked list, follow these steps:
- Create the New Node: Allocate memory for the new node and set its data.
- Find the Last Node: Start from the head node and traverse the list to find the last node, which is the node whose next pointer points back to the head.
- Insert the New Node:
- Set the new node’s next pointer to point to the current head node.
- Update the last node’s next pointer to point to the new node.
- Set the new node as the new head of the list.
void add_head(struct node **head)
{
struct node *new_node = NULL, *tmp;
int val;
new_node = (struct node*)calloc(1, sizeof(struct node));
printf("enter a value to insert:");
scanf("%d", &val);
new_node->data = val;
new_node->next = head;
if (*head == NULL) {
new_node->next = new_node;
*head = new_node;
}
tmp = *head;
while (tmp != *head)
tmp = tmp->next;
tmp->next = new_node;
new_node->next = *head;
*head = new_node;
}3. Deleting a node
Delete first node
To delete the first node in a circular singly linked list, follow these steps:
- Check for Empty List: If the list is empty (i.e., the head is
NULL), there is nothing to delete. - Update Head: Set the head node to the next node of the current head. This effectively makes the second node in the list the new head.
- Find the Last Node: Traverse the list starting from the new head to find the last node. This node’s next pointer needs to be updated to point to the new head.
- Free the Old Head: Deallocate or free the memory of the original head node.
void delete_first_node(struct node **head)
{
struct node *tmp;
if (*head == NULL) {
printf("list empty\n");
return;
}
tmp = *head;
if (tmp->next == *head) {
free(tmp);
*head = NULL;
return;
}
/* go to the last node */
while (tmp->next != *head)
tmp = tmp->next;
tmp->next = (*head)->next;
free(*head);
*head = tmp->next;
}Delete last node
To delete the last node in a circular singly linked list, follow these steps:
- Check for Empty List: If the list is empty (i.e., the head is
NULL), there is nothing to delete. - Handle Single Node Case: If there is only one node in the list, set the head to
NULLand free the node. The list will now be empty. - Traverse the List: Start from the head and traverse the list to find the node just before the last node. This can be done by moving to the next node until you find the node whose next pointer points back to the head node.
- Update Pointers:
- Set the
nextpointer of the second-to-last node to point to the head, effectively removing the last node from the list. - Free the memory of the last node.
- Set the
void delete_last_node(struct node **head)
{
struct node *tmp;
struct node *prev = NULL;
if (*head == NULL) {
printf("list empty\n");
return;
}
tmp = *head;
while (tmp->next != *head) {
prev = tmp;
tmp = tmp->next;
}
free(tmp);
if (prev)
prev->next = *head;
else
*head = NULL;
}Delete a selected node
To delete a selected node in a circular singly linked list, follow these steps:
- Check for Empty List: If the list is empty (i.e., the head is
NULL), there is nothing to delete. - Find the Node: Traverse the list to locate the node to be deleted. Track the previous node as you traverse, since you will need it to update the pointers.
- Handle Special Cases:
- Delete Head Node: If the node to be deleted is the head node, update the head to the next node. Then, find the last node (whose
nextpointer points to the old head) and update itsnextpointer to point to the new head. Finally, free the old head node. - Delete Non-Head Node: If the node to be deleted is not the head, update the
nextpointer of the previous node to skip the node to be deleted and point to the node after it. Free the node to be deleted.
- Delete Head Node: If the node to be deleted is the head node, update the head to the next node. Then, find the last node (whose
- Free the Node: After updating the pointers, deallocate or free the memory of the node to be deleted.
void delete_node(struct node **head)
{
int val;
struct node *tmp, *node;
if (*head == NULL) {
printf("List empty\n");
return;
}
printf("enter value to delete:");
scanf("%d", &val);
if ((*head)->data == val) {
*head = delete_first_node(*head);
return;
}
tmp = *head;
while (tmp->next != *head && tmp->next->data != val) {
tmp = tmp->next;
};
if (tmp->next == *head) {
printf("node not found with val:%d\n", val);
return;
}
printf("deleting a node\n");
node = tmp->next;
tmp->next = tmp->next->next;
free(node);
}Git hub link for Data Structures applications here