Circular Double Linked Lists - Introduction and Implementation


Circular linked lists may be circular single linked lists or circular double linked lists. Read this article for a brief introduction of circular double linked lists and the C programs to implement circular single linked lists.

Circular Double Linked Lists


If in a double linked list, the last node is connected to the first node, it is called a circular double linked list. The operations on circular double linked lists are similar to that of double linked lists i.e. insertion, deletion, display etc,. The last element contains some data and pointer to the first element but not a NULL pointer. The first element contains some data and pointer to the last element but not a NULL pointer.

C Program to implement Circular Double Linked List


Program
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *prev,*next;
};
struct node *head=NULL,*tail=NULL;
struct node* create_node(int data)
{
struct node *ptr=(struct node*)malloc(sizeof(struct node));
ptr->data=data;
ptr->prev=NULL;
ptr->next=NULL;
return ptr;
}
void insert_node(int data)
{
struct node *temp,*ptr=create_node(data);
if(!head)
{
head=ptr;
head->next=head;
head->prev=head;
tail=head;
return;
}
else
{
if(head->next==head&&head->prev==head)
{
temp=head;
ptr->next=temp;
ptr->prev=temp->prev;
temp->prev=ptr;
temp->next=ptr;
tail=ptr;
}
else
{
temp=head->next;
ptr->next=temp;
ptr->prev=temp->prev;
temp->prev->next=ptr;
temp->prev=ptr;
}
}
}
void delete_node(int data)
{
struct node *ptr,*temp=head;
if(head==NULL)
{
printf("\n Circular Double Linked List is Empty");
return;
}
else if(temp->data==data)
{
if(head==tail)
{
temp->prev=NULL;
temp->next=NULL;
free(temp);
head=tail=NULL;
}
else
{
temp->next->prev=tail;
tail->next=temp->next;
head=temp->next;
temp->next=temp->prev=NULL;
free(temp);
}
}
else
{
while(temp->next!=head&&temp->data!=data)
{
ptr=temp;
temp=temp->next;
}
if(temp->next==head&&temp->data!=data)
return;
else if(temp->next!=head&&temp->data==data)
{
ptr->next=temp->next;
temp->next->prev=temp->prev;
temp->next=NULL;
temp->prev=NULL;
free(temp);
}
else if(temp->next==head&&temp->data==data)
{
ptr->next=temp->next;
temp->next->prev=ptr;
tail=ptr;
free(temp);
}
}
}
void display()
{
struct node *ptr=head;
int i=0;
printf("\n Circular Double Linked List is : ");
while(ptr)
{
printf("%d ",ptr->data);
if(ptr->next==head)
break;
ptr=ptr->next;
i++;
}
}
void main()
{
int choice,data;
clrscr();
while(1)
{
printf("\n\n Circular Double Linked List Operations");
printf("\n 1.Insert");
printf("\n 2.Delete");
printf("\n 3.Display");
printf("\n 4.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter the value of node to insert : ");
scanf("%d",&data);
insert_node(data);
break;
case 2:
printf("\n Enter the value of node to delete : ");
scanf("%d",&data);
delete_node(data);
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\n Your choice is invalid");
break;
}
}
}

Output
Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the value of node to insert : 0

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the value of node to insert : 2

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the value of node to insert : 4

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Circular Double Linked List is : 0 2 4

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the value of node to insert : 6

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the value of node to insert : 8

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Circular Double Linked List is : 0 2 4 6 8

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Enter the value of node to delete : 8

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Enter the value of node to delete : 6

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Enter the value of node to delete : 4

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Enter the value of node to delete : 2

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Enter the value of node to delete : 0

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Circular Double Linked List is :

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 5
Your choice is invalid

Circular Double Linked List Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 4


More articles: Computer programs

Comments



  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: