A circular double linked list is a type of linked list where each node has two pointers: one pointing to the next node and another pointing to the previous node. In this structure, the last node’s next pointer links back to the first node, and the first node’s previous pointer links to the last node, forming a continuous loop in both directions. Unlike a regular doubly linked list, there is no NULL pointer, as the list has no true start or end.
The structure is same as double linked list
struct node {
int data;
struct node *next;
struct node *prev;
};- Entry point
- In a circular doubly linked list, the head node serves as the entry point. It is the starting reference for traversing the list.
- Exit point
- Unlike a regular doubly linked list, there is no node with a NULL pointer to indicate the end. Instead, the exit point is identified when a node’s next pointer loops back to the head node, and the head node’s previous pointer connects to the last node.
Managing nodes in a Circular single linked list
1. Traversing through the nodes
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;
if (head == NULL) {
printf("List empty\n");
return;
}
tmp = head;
printf("printing the list\n");
do {
printf("data=%d\n", tmp->data);
tmp = tmp->next;
} while (tmp != head);
2. Adding a node to list
Add at the end of list
To add a new node at the end of a circular doubly linked list, follow these steps:
- Find the Last Node: Start from the head node and traverse the list using the next pointers until you reach the node whose next pointer points back to the head. This is the last node in the circular doubly linked list.
- Insert the New Node: Create a new node and set its next pointer to point to the head node and its previous pointer to the last node. Then, update the last node’s next pointer to point to the new node, and the head node’s previous pointer to point to the new node, completing the circular structure.
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;
if (*head == NULL) {
*head = new_node;
(*head)->next = (*head)->prev = new_node;
} else {
tmp = *head;
while (tmp->next != *head)
tmp = tmp->next;
tmp->next = new_node;
new_node->prev = tmp;
new_node->next = *head;
}
}Add at the beginning of list
To add a new node at the beginning of a circular doubly linked list, follow these steps:
- Create the New Node: Allocate memory for the new node and set its data value.
- Find the Last Node: Start from the head node and traverse the list by following the
nextpointers to find the last node, which is the node whosenextpointer points back to the head node. - Insert the New Node:
- Set the new node’s
nextpointer to point to the current head node. - Set the new node’s
prevpointer to point to the last node. - Update the current head’s
prevpointer to point to the new node. - Update the last node’s
nextpointer to point to the new node. - Set the new node as the new head of the list.
- Set the new node’s
void add_head(struct node **head)
{
struct node *new_node = NULL;
struct node *tmp = NULL;
int val;
new_node = (struct node*)calloc(1, sizeof(struct node));
printf("enter a value to insert:");
scanf("%d", &val);
new_node->data = val;
if (*head == NULL) {
new_node->next = new_node->prev = new_node;
*head = new_node;
return;
}
tmp = *head;
while(tmp->next != *head)
tmp = tmp->next;
tmp->next = new_node;
new_node->next = *head;
new_node->prev = (*head)->prev;
(*head)->prev = new_node;
*head = new_node;
}3. Delete a node
Delete first node
To delete the first node in a circular doubly 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.
- Check for Single Node: If there is only one node in the list (i.e., the next and prev pointers of the head point to itself), set the head to NULL and free the memory of the node.
- Update Head: Set the head to the next node of the current head. This makes the second node the new head.
- Update Pointers:
Set the last node’s next pointer to point to the new head.
Set the new head’s prev pointer to point to the last node. - 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;
}
if ((*head)->next == *head) {
free(*head);
*head = NULL;
return;
}
/* set the last node next pointer */
tmp = *head;
while (tmp->next != *head)
tmp = tmp->next;
tmp->next = (*head)->next;
/* delete first node */
tmp = *head;
*head = tmp->next;
(*head)->prev = tmp->prev;
free(tmp);
return;
}Delete last node
To delete the last node in a circular doubly 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 the list has only one node (i.e., the next and prev pointers of the head point to itself), set the head to NULL and free the memory of the node. The list will now be empty.
- Traverse the List: Start from the head and traverse the list to find the last node (the node whose next pointer points back to the head).
- Update Pointers:
- Set the next pointer of the second-to-last node (i.e., prev of the last node) to point to the head.
- Set the prev pointer of the head to point to the second-to-last node.
- Free the Last Node:
Deallocate or free the memory of the last node.
void delete_last_node(struct node **head)
{
struct node *tmp;
if (*head == NULL) {
printf("list empty\n");
return;
}
if ((*head)->next == *head) {
free(*head);
*head = NULL;
return;
}
tmp = *head;
while (tmp->next != *head)
tmp = tmp->next;
tmp->prev->next = *head;
(*head)->prev = tmp->prev;
free(tmp);
}Delete a selected node
To delete a selected node in a circular doubly 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. Keep track of the previous node as you go, since you will need it to update the pointers.
- Handle Special Cases:
Delete Head Node is same as the delete first node.
If the node to be deleted is not the head:- Update the next pointer of the previous node to skip the node to be deleted and point to the node after it.
- Update the prev pointer of the node after the one being deleted to point to the previous node.
Free the memory of the node to be deleted.
- 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;
if (*head == NULL) {
printf("List empty\n");
return;
}
printf("enter value to delete:");
scanf("%d", &val);
if ((*head)->data == val) {
delete_first_node(head);
return;
}
tmp = *head;
while (tmp->data != val && tmp->next != *head)
tmp = tmp->next;
if (tmp->data != val && tmp->next == *head) {
printf("node not found with val:%d\n", val);
return;
}
printf("deleting a node\n");
tmp->prev->next = tmp->next;
tmp->next->prev = tmp->prev;
free(tmp);
}For full C application on circular double linked list click here.