Doubly-linked list is a more sophisticated form of
linked list data structure. Each node contains two fields, called links that
are references to the previous and to the next node in the sequence of nodes. The
two node links allow traversal of the list in either direction. The previous
link of the first node and the next link of the last node points to NULL.
While adding or removing a node in a doubly linked
list requires changing more links than the same operations on a singly linked
list, the operations are simpler and potentially more efficient (for nodes
other than first nodes) because there is no need to keep track of the previous
node during traversal or no need to traverse the list to find the previous
node, so that its link can be modified.
Example: A doubly linked list whose nodes contain
three fields of integer value, the link to the next node, and the link to the
previous node.
#include
<stdio.h>
#include
<stdlib.h>
struct
node {
struct
node *prev;
int
n;
struct
node *next;
}*h,*temp,*temp1,*temp2,*temp4;
void
insert1();
void
insert2();
void
insert3();
void
delete1();
void
traversebeg();
void
traverseend(int);
void
sort();
void
search();
void
update();
int
count = 0;
main(void)
{
int
ch;
h
= NULL;
temp
= temp1 = NULL;
printf("\n
1 - Insert At Beginning");
printf("\n
2 - Insert At End");
printf("\n
3 - Insert At Any Position");
printf("\n
4 - Delete From Any Position");
printf("\n
5 - Display The List");
printf("\n
6 - Reverse The List");
printf("\n
7 - Search For Element");
printf("\n
8 - Sort The List");
printf("\n
9 - Update The List");
printf("\n
10 - Exit");
while
(1) {
printf("\n\n
Enter Your Choice : ");
scanf("%d",
&ch);
switch
(ch) {
case
1: insert1(); break;
case
2: insert2(); break;
case
3: insert3(); break;
case
4: delete1(); break;
case
5: traversebeg(); break;
case
6: temp2 = h;
if
(temp2 == NULL)
printf("\n
Error : List Empty To display.\n");
else
{
printf("\n
Reverse Order Of Linked List Is : ");
traverseend(temp2->n);
printf("\n");
}
break;
case
7: search(); break;
case
8: sort(); break;
case
9: update(); break;
case
10: exit(0);
default:
printf("\n Error : Wrong Menu Choice!\n");
}}}
/*
To create an empty node */
void
create()
{
int
data;
temp
=(struct node *)malloc(1*sizeof(struct node));
temp->prev
= NULL;
temp->next
= NULL;
printf("\n
Enter A Value To List : ");
scanf("%d",
&data);
temp->n
= data;
count++;
}
/*
To insert at beginning */
void
insert1()
{
if
(h == NULL) {
create();
h
= temp;
temp1
= h;
}
else
{
create();
temp->next
= h;
h->prev
= temp;
h
= temp;
}}
/*
To insert at end */
void
insert2()
{
if
(h == NULL) {
create();
h
= temp;
temp1
= h;
}
else
{
create();
temp1->next
= temp;
temp->prev
= temp1;
temp1
= temp;
}}
/*
To insert at any position */
void
insert3() {
int
pos, i = 2;
printf("\n
Enter Position To Be Inserted : ");
scanf("%d",
&pos);
temp2
= h;
if
((pos < 1) || (pos >= count + 1)) {
printf("\n
Error : Position Out Of Range To Insert.\n");
return;
}
if
((h == NULL) && (pos != 1)) {
printf("\n
Error : Empty List, You Cannot Insert Other Than 1st Position.\n");
return;
}
if
((h == NULL) && (pos == 1))
{
create();
h
= temp;
temp1
= h;
return;
}
else
{
while
(i < pos) {
temp2
= temp2->next;
i++;
}
create();
temp->prev
= temp2;
temp->next
= temp2->next;
temp2->next->prev
= temp;
temp2->next
= temp;
}}
/*
To delete an element */
void
delete1() {
int
i = 1, pos;
printf("\n
Enter Position To Be Deleted : ");
scanf("%d",
&pos);
temp2
= h;
if
((pos < 1) || (pos >= count + 1)) {
printf("\n
Error : Position Out Of Range To Delete.\n");
return;
}
if
(h == NULL) {
printf("\n
Error : Empty List! No Element To Delete.\n");
return;
}
else
{
while
(i < pos) {
temp2
= temp2->next;
i++;
}
if
(i == 1) {
if
(temp2->next == NULL)
{
printf("\n
Node Deleted From List.\n");
free(temp2);
temp2
= h = NULL;
return;
}}
if
(temp2->next == NULL) {
temp2->prev->next
= NULL;
free(temp2);
printf("\n
Node Deleted From List.\n");
return;
}
temp2->next->prev
= temp2->prev;
if
(i != 1)
temp2->prev->next
= temp2->next; /* Might not need this statement if i == 1
check */
if
(i == 1)
h
= temp2->next;
printf("\n
Node Deleted From List.\n");
free(temp2);
}
count--;
}
/*
Traverse from beginning */
void
traversebeg() {
temp2
= h;
if
(temp2 == NULL) {
printf("\n
Error : List Empty To Display.\n");
return;
}
printf("\n
Linked List Elements From Begining : ");
while
(temp2->next != NULL) {
printf("
%d ", temp2->n);
temp2
= temp2->next;
}
printf("
%d ", temp2->n);
printf("\n");
}
/*
To traverse from end recursively */
void
traverseend(int i) {
if
(temp2 != NULL)
{
i
= temp2->n;
temp2
= temp2->next;
traverseend(i);
printf("
%d ", i);
}}
/*
To search for an element in the list */
void
search() {
int
data, count = 0;
temp2
= h;
if
(temp2 == NULL) {
printf("\n
Error : List Empty To Search For Data.\n");
return;
}
printf("\n
Enter Value To Search : ");
scanf("%d",
&data);
while
(temp2 != NULL)
{
if
(temp2->n == data) {
printf("\n
Data Found In %d Position.\n",count + 1);
return;
}
else
temp2
= temp2->next;
count++;
}
printf("\n
Error : %d Not found In List.\n", data);
}
/*
To update a node value in the list */
void
update() {
int
data, data1;
printf("\n
Enter The Data To Be Updated : ");
scanf("%d",
&data);
printf("\n
Enter New Data : ");
scanf("%d",
&data1);
temp2
= h;
if
(temp2 == NULL) {
printf("\n
Error : List Empty, No node To Update.\n");
return;
}
while
(temp2 != NULL)
{
if
(temp2->n == data) {
temp2->n
= data1;
traversebeg();
return;
}
else
temp2
= temp2->next;
}
printf("\n
Error : %d Not Found In List To Update.\n", data);
}
/*
To sort the linked list */
void
sort() {
int
i, j, x;
temp2
= h;
temp4
= h;
if
(temp2 == NULL) {
printf("\n
Error : List Empty To Sort.\n");
return;
}
for
(temp2 = h; temp2 != NULL; temp2 = temp2->next) {
for
(temp4 = temp2->next; temp4 != NULL; temp4 = temp4->next) {
if
(temp2->n > temp4->n) {
x
= temp2->n;
temp2->n
= temp4->n;
temp4->n
= x;
}}}
traversebeg();
}