What is Doubly Link List
In a doubly linked list, each node contains, two links one is called next which points to the next node and one is called prev which points to the previous node in the sequence.
Why Circular Doubly Link List
As you can see in the previous image that the head->prev is null and so the last->next but if head->prev is pointing to the last node and last->next is pointing to the head node is called doubly circular link list
Necessary Function
However it is dependent on how you like to manage the link list but the following function would be useful addition which can make any Doubly Link List useful in most of the situations -
struct node* create_node(int info)
void add_node(int info)
void insert_at_first(int info)
void insert_at_last(int info)
void insert_at_position(int info, int position)
void sort_list()
void delete_node_position(int position)
void update(int olddata, int newdata)
void search(int key)
void display_from_begining()
void display_in_reverse()
Sample Code
Here is the sample code (only the functions) written in C, any taker for C++
struct node
{
int data;
struct node *next;
struct node *prev;
};
/* We can have additional structure which can have head and last node is node pointer and
additionally can have length variable which contains the length of the link list */
struct node *head = NULL, *last = NULL;
int length = 0;
struct node* create_node(int info)
{
struct node *new;
length++;
new = (struct node *)malloc(sizeof(struct node));
new->data = info;
new->next = NULL;
new->prev = NULL;
return new;
}
void add_node(int info)
{
struct node *new;
new = create_node(info);
if (head == last && head == NULL)
{
head = last = new;
head->next = last->next = NULL;
head->prev = last->prev = NULL;
}
else
{
last->next = new;
new->prev = last;
last = new;
last->next = head;
head->prev = last;
}
}
void insert_at_first(int info)
{
struct node *new;
new = create_node(info);
if (head == last && head == NULL)
{
head = last = new;
head->next = last->next = NULL;
head->prev = last->prev = NULL;
}
else
{
new->next = head;
head->prev = new;
head = new;
head->prev = last;
last->next = head;
}
}
void insert_at_last(int info)
{
struct node *new;
new = create_node(info);
if (head == last && head == NULL)
{
head = last = new;
head->next = last->next = NULL;
head->prev = last->prev = NULL;
}
else
{
last->next = new;
new->prev = last;
last = new;
head->prev = last;
last->next = head;
}
}
void insert_at_position(int info, int position)
{
struct node *new, *ptr, *prevnode;
int len = 0, i;
new = create_node(info);
if (head == last && head == NULL)
{
if (position == 1)
{
head = last = new;
head->next = last->next = NULL;
head->prev = last->prev = NULL;
}
else
printf("\n empty linked list you cant insert at that particular position");
}
else
{
if (length < position)
printf("\n node cant be inserted as position is exceeding the linkedlist length");
else
{
for (ptr = head, i = 1;i <= length;i++)
{
prevnode = ptr;
ptr = ptr->next;
if (i == position-1)
{
prevnode->next = new;
new->prev = prevnode;
new->next = ptr;
ptr->prev = new;
break;
}
}
}
}
}
void sort_list()
{
struct node *temp, *ptr;
int tempdata, i, j;
if (head == last && head == NULL)
printf("\nlinked list is empty no elements to sort");
else
{
for (ptr = head,i = 0;i < length;ptr = ptr->next,i++)
{
for (temp = ptr->next,j=i;j<length;j++)
{
if (ptr->data > temp->data)
{
tempdata = ptr->data;
ptr->data = temp->data;
temp->data = tempdata;
}
}
}
for (ptr = head, i = 0;i < length;ptr = ptr->next,i++)
printf("\n%d", ptr->data);
}
}
void delete_node_position(int position)
{
int count = 0, i;
struct node *ptr, *temp, *prevnode;
if (head == last && head == NULL)
printf("\n empty linked list you cant delete");
else
{
if (length < position)
printf("\n node cant be deleted at position as it is exceeding the linkedlist length");
else
{
for (ptr = head,i = 1;i <= length;i++)
{
prevnode = ptr;
ptr = ptr->next;
if (position == 1)
{
length--;
last->next = prevnode->next;
ptr->prev = prevnode->prev;
head = ptr;
free(prevnode);
break;
}
else if (i == position - 1)
{
length--;
prevnode->next = ptr->next;
ptr->next->prev = prevnode;
free(ptr);
break;
}
}
}
}
}
void update(int olddata, int newdata)
{
int i, f = 0;
struct node *ptr;
if (head == last && head == NULL)
printf("\n list is empty no elemnts for updation");
else
{
for (ptr = head, i = 0; i < length; ptr = ptr->next,i++)
{
if (ptr->data == olddata)
{
ptr->data = newdata;
printf("value is updated to %d", ptr->data);
f = 1;
}
}
if (f == 0)
printf("\n no such old value to be get updated");
}
}
void search(int key)
{
int count = 0, i, f = 0;
struct node *ptr;
if (head == last && head == NULL)
printf("\nlist is empty no elemnets in list to search");
else
{
for (ptr = head,i = 0; i < length; i++,ptr = ptr->next)
{
count++;
if (ptr->data == key)
{
printf("\n the value is found at position at %d", count);
f = 1;
}
}
if (f == 0)
printf("\n the value is not found in linkedlist");
}
}
void display_from_begining()
{
int i;
struct node *ptr;
if (head == last && head == NULL)
printf("\nlist is empty no elemnts to print");
else
{
printf("\n%d number of nodes are there", length);
for (ptr = head, i = 0;i < length;i++,ptr = ptr->next)
printf("\n %d", ptr->data);
}
}
void display_in_reverse()
{
int i;
struct node *ptr;
if (head == last && head == NULL)
printf("\nlist is empty there are no elments");
else
{
for (ptr = last, i = 0;i < length;i++,ptr = ptr->prev)
{
printf("\n%d", ptr->data);
}
}
}