Double Linked List Program

– Doubly linked list

• Pointers exist between adjacent nodes in both
directions.
• The list can be traversed either forward or backward.
• Usually two pointers are maintained to keep track of
the list, head and tail.

head tail

A B C D

Programming and Data Structure 2

– Doubly Circular linked list

head tail

A B C D

Programming and Data Structure 3

 Double Linked List complete program
#include<stdio.h>
#include<stdio.h>
struct link {
int roll;
struct link *first;
struct link *next;
};

/* A user-defined data type called “node” */

typedef struct link node;

node *head, *tail;
 Double Linked List complete program –cont..
// CREATE D-LIST FUNCTION
node *create_Dlist()
{ int k, n;
node *tmp,*cr, *head;
printf ("\n How many elements to create ?");
scanf ("%d", &n);
for (k=0; k<n; k++)
{ tmp = (node *) malloc(sizeof(node));
printf("enter data");
scanf("%d",&tmp->roll);
if (k == 0) { tmp->first=NULL;tmp->next=NULL;
head = tmp; tail=tmp; }
else { tmp->first=tail;tmp->next=NULL;
tail->next=tmp; tail=tmp;
}
}
return (head);
}
 Double Linked List complete program –cont..
// PRINT_Forward FUNCTION
void print_forward()
{
node *ptr = head;
printf("\n[ "); //start from the beginning
while(ptr != NULL)
{
printf("(%d) ",ptr->roll);
ptr = ptr->next;
}
printf(" ]");
}
 Double Linked List complete program –cont..
// PRINT_Backward FUNCTION
void print_backward()
{
node *ptr = tail;
printf("\nReverse direction"); //start from the beginning
printf("\n[ "); //start from the end
while(ptr != NULL)
{
printf("(%d) ",ptr->roll);
ptr = ptr->first;
}
printf(" ]");
}
 Double Linked List complete program –cont..
// INSERT NODE FUNCTION
void insert()
{ int ch,p,i;
node *tmp, *cr,*pr;
tmp = (node *) malloc(sizeof(node)); //create a link
printf("\n Insert Node :: Enter rollno :");
scanf ("%d", &tmp ->roll);
printf("enter 1- to insert at begining, 2-at end, 3- middle , option : ");
scanf("%d",&ch);
if(ch==2) if(ch==3)
{tmp->first=tail; { cr = head;
if(ch==1) printf("enter position to
{tmp->first=NULL; tmp->next = NULL;
tail->next=tmp; insert : ");
tmp->next = head; scanf("%d", &p);
head->first=tmp; tail = tmp;
} for(i=1;i<(p-1);i++)
head = tmp; { cr=cr->next; }
} tmp->next=cr->next;
(cr->next)->first=tmp;
} tmp->first=cr;
cr->next=tmp; }
 Double Linked List complete program –cont..
// DELETE NODE FUNCTION (for a given roll number )
node* deletelink(int key)
{ // key is roll number to delete pass, from main function
//start from the first link
node* current = head; node* previous = NULL;
if(head == NULL){
return NULL; //if list is empty //found a match, update the link
} if(current == head) {
head = head->next;
//navigate through list head->first=NULL;
while(current->roll != key){ }
//if it is last node else if(current==tail)
if(current->next == NULL){ { previous->next=NULL;
return NULL; tail=previous;
}else { }
//store reference to current link else {
previous = current; previous->next = current->next;
//move to next link (current->next)->first=previous;
} current = current->next;} }
} return current;
 Double Linked List complete program –cont..
// SEARCH NODE FUNCTION (for a given roll number)
node* search(int key) // key is roll number to search , pass from main function
{//start from the first link
node* current = head;
//if list is empty
if(head == NULL)
{ return NULL;
}
while(current->roll != key) //navigate through list
{ if(current->next == NULL) //if it is last node
{ return NULL; }
else { current = current->next; //go to next link }
}
//if data found, return the current Link
return current;
}
 Single Linked List complete program –cont..
// MAIN FUNCTION
main()
{ head = create_Dlist();
while(ch!=0)
{printf("enter 1-diaplay, 2- insert, 3-search,4-delete 0-exit");
scanf("%d",&ch);

switch(ch) case 4: printf(" enter roll number

{ case 1: print_forward(); to delete : ");
print_backward();break; scanf("%d", &roll);
case 2: insert();print_forward();break; elem=deletelink(roll);
case 3: printf("enter roll number to if(elem==NULL)
sreach : "); {printf(" node not existing\n");}
scanf("%d", &roll); else{free(elem);
elem=search(roll); print_forward(); }
if(elem==NULL) break;
{printf(" search node not existing\n");} default: ch=0;
else{ printf("roll No: %d existing in }
} list\n",elem->roll);
//close while }
} break;