Updated April 10, 2023
Definition of Circular Doubly Linked List in C
Circular doubly linked list in C or in any programming language is a very useful data structure. Circular double linked list is a type of linked list that consists of node having a pointer pointing to the previous node and the next node points to the previous node in the defined array. Circular doubly linked list is considered as one of the complex data structures in a way it works and plays with lots of pointers and addresses management within the implemented list. It doesn’t contain a null pointer in the defined list.
Syntax
There is no particular syntax for the Circular doubly linked list but still needs to perform some of the initial steps of the creation of data structure and once created many operations can be performed on that linked list accordingly which is represented below :
#include <stdio.h>
Struct node_1
{
Struct node *prvs;
int some_data;
Struct node *nxt;
}
Follow scenarios:
– Insertion at the beginning
– Insertion at the end
– Removal from the beginning
– Removal from the end
Close the data structure and perform the further operation.
How Circular doubly linked list works in C?
Since Circular doubly linked list is a two-way list where the pointers somehow point to each other and no concept of null is present thus the pointer concept works internally. This is a type of linked list which is considered complex because of the previous node and the next node pointing to the previous node. Thus a fact can be concluded that the last node contains the address of the previous or the first node of the entire list.
The first node present in the list contains address of the last node for the pointer in its previous node. Since a circular double-linked list demands three structures, therefore, it is required to have more space and more expensive operations especially on the basics part of it. Searching in the case of a doubly linked list becomes quite easy and efficient as manipulation with the pointers is easy. But sometimes developers don’t prefer such data structure due to costly basic operation applied on the entire linked list.
Another factor that plays a good role in memory management with respect to the circular double-linked list because it provides proper memory to each element present within the cell. The head as a variable contains the address of the first element of list. This first element is then the starting node of the list, the next node contains the second element, and so on till the last pointer which points back to the first node again proves the fact that the node is the last node that is pointing to the first since it does not contain any null element concept. There are various operations that are performed as part of the circular double linked list like insertion at the beginning, insertion at the end, deletion from the beginning, deletion at the end.
Examples
Let us discuss examples of Circular Doubly Linked List in C.
Example #1
This example represents an implementation of circular double-linked list with the operations of insertion at the beginning, insertion at the last, deletion at the beginning, and deletion at last which further displays the operation.
Code:
#include<stdio.h>
#include<stdlib.h>
struct nd_0
{
struct nd_0 *prv_1;
struct nd_0 *nxt_1;
int dta;
};
struct nd_0 *head;
void insrtion_begnng();
void insrtion_lst();
void delnt_begnng();
void deln_lst();
void show();
void srch();
void main ()
{
int choce =0;
while(choce != 8)
{
printf("\n*********Main_Menu_for_Display*********\n");
printf("\nChoose_any_one_option_from_list ...\n");
printf("\n----------------------------------------------------\n"); printf("\n1.Insertion_At_start\n2.Insertion_At_last\n3.Delet_at_Beginning\n4.Deletion_frm_end\n5.find\n6.display_val\n7.stop\n");
printf("\nSelect_the_desired_choice?\n");
scanf("\n%d",&choce);
switch(choce)
{
case 1:
insrtion_begnng();
break;
case 2:
insrtion_lst();
break;
case 3:
delnt_begnng();
break;
case 4:
deln_lst();
break;
case 5:
srch();
break;
case 6:
show();
break;
case 7:
exit(0);
break;
default:
printf("Select_entry_of_your_choicce..");
}
}
}
void insrtion_begnng()
{
struct nd_0 *ptr_0,*temp_1;
int item_0;
ptr_0 = (struct nd_0 *)malloc(sizeof(struct nd_0));
if(ptr_0 == NULL)
{
printf("\nList_Overflow");
}
else
{
printf("\nEnter desired_element");
scanf("%d",&item_0);
ptr_0->dta=item_0;
if(head==NULL)
{
head = ptr_0;
ptr_0 -> nxt_1 = head;
ptr_0 -> prv_1 = head;
}
else
{
temp_1 = head;
while(temp_1 -> nxt_1 != head)
{
temp_1 = temp_1 -> nxt_1;
}
temp_1 -> nxt_1 = ptr_0;
ptr_0 -> prv_1 = temp_1;
head -> prv_1 = ptr_0;
ptr_0 -> nxt_1 = head;
head = ptr_0;
}
printf("\nInserted_Node..\n");
}
}
void insrtion_lst()
{
struct nd_0 *ptr_0,*temp_1;
int itm_0;
ptr_0 = (struct nd_0 *) malloc(sizeof(struct nd_0));
if(ptr_0 == NULL)
{
printf("\niList_overflow");
}
else
{
printf("\nEnter desired_val");
scanf("%d",&itm_0);
ptr_0->dta=itm_0;
if(head == NULL)
{
head = ptr_0;
ptr_0 -> nxt_1 = head;
ptr_0 -> prv_1 = head;
}
else
{
temp_1 = head;
while(temp_1->nxt_1 !=head)
{
temp_1 = temp_1->nxt_1;
}
temp_1->nxt_1 = ptr_0;
ptr_0 ->prv_1=temp_1;
head -> prv_1 = ptr_0;
ptr_0 -> nxt_1 = head;
}
}
printf("\nnode_insertd_at_lst\n");
}
void delnt_begnng()
{
struct nd_0 *temp_1;
if(head == NULL)
{
printf("\n List_UNDERFLOW");
}
else if(head->nxt_1 == head)
{
head = NULL;
free(head);
printf("\ndelete_node_at_beginning\n");
}
else
{
temp_1 = head;
while(temp_1 -> nxt_1 != head)
{
temp_1 = temp_1 -> nxt_1;
}
temp_1 -> nxt_1 = head -> nxt_1;
head -> nxt_1 -> prv_1 = temp_1;
free(head);
head = temp_1 -> nxt_1;
}
}
void deln_lst()
{
struct nd_0 *ptr_1;
if(head == NULL)
{
printf("\n List_Underflow");
}
else if(head->nxt_1 == head)
{
head = NULL;
free(head);
printf("\nDeleted_Node\n");
}
else
{
ptr_1 = head;
if(ptr_1->nxt_1 != head)
{
ptr_1 = ptr_1 -> nxt_1;
}
ptr_1 -> prv_1 -> nxt_1 = head;
head -> prv_1 = ptr_1 -> prv_1;
free(ptr_1);
printf("\nDeleted_Node\n");
}
}
void show()
{
struct nd_0 *ptr_0;
ptr_0=head;
if(head == NULL)
{
printf("\nnot_to_print_anything;;");
}
else
{
printf("\n Need_to_print_some_values ... \n");
while(ptr_0 -> nxt_1 != head)
{
printf("%d\n", ptr_0 -> dta);
ptr_0 = ptr_0 -> nxt_1;
}
printf("%d\n", ptr_0 -> dta);
}
}
void srch()
{
struct nd_0 *ptr_0;
int itm,i_0=0,flag=1;
ptr_0 = head;
if(ptr_0 == NULL)
{
printf("\nBlank_all_elements.\n");
}
else
{
printf("\nSearch_for_items?\n");
scanf("%d",&itm);
if(head ->dta == itm)
{
printf("found_location_item %d",i_0+1);
flag=0;
}
else
{
while (ptr_0->nxt_1 != head)
{
if(ptr_0->dta == itm)
{
printf("element_at_location %d ",i_0+1);
flag=0;
break;
}
else
{
flag=1;
}
i_0++;
ptr_0 = ptr_0 -> nxt_1;
}
}
if(flag != 0)
{
printf("Element_Not_found\n");
}
}
}
Output:
Conclusion
Circular Doubly linked list is a type of linked list and is part of data structure which has lot of advantages when it comes to memory management. It supports complex pointer concepts with ease. Lot of manipulations and operations can be performed on this data structure containing elements in a row.
Recommended Articles
This is a guide to Circular Doubly Linked List in C. Here we discuss the definition, syntax, and parameters, How Circular doubly linked list works in C? examples with code implementation. You may also have a look at the following articles to learn more –