Doubly linked list in C Archives

So far we have seen doubly linked list which have two pointers next and previous. but in efficient doubly linked list we will use only one pointer to move at next and previous nodes.

We know XOR is used for bit recovery the same concept we will use here to store both the ptr (next and previous) information in single variable.

structure for efficient doubly linked list :

struct ednode{
int val;
struct ednode *ptr;
}

Suppose we have linked list of 4 nodes [ W | X | Y | Z ]

W->ptr= NULL ^ X

X->ptr= W ^ Y

Y->ptr= X ^ Z

Z->ptr= Y->NULL

To move at W from X

(W^Y)^Y ==> which is (X->ptr^Y) ==> which is W

similar way to move at Y from X

(W^Y)^W ==> which is (X->ptr^W) ==> which is Y

/*C Code for Memory Efficient Doubly linked list by Codingstreet.com*/
#include<stdio.h>
#include<stdlib.h>
struct ednode{
int val;
struct ednode *ptr;
};
int create_ednode(int val,struct ednode **node){
struct ednode *tmp;
tmp=malloc(sizeof(struct ednode));
if(tmp==NULL) return 0; 
tmp->val=val;
tmp->ptr=NULL;
(*node)=tmp;
return 1;
}
void insert_ednode(struct ednode **head,struct ednode **node,struct ednode **tail){
struct ednode *prev,*next,*tmp;
if((*head)==NULL && (*tail)==NULL){
(*head)=(*tail)=(*node);
(*head)->ptr=NULL;
}
else if((*head)->ptr==NULL){
next=(*node);
(*head)->ptr=(struct ednode *)((unsigned int)(NULL)^(unsigned int)(next));
next->ptr=(struct ednode *)((unsigned int)(*head)^(unsigned int)(NULL)); 
(*tail)=(*node); 
}
else {
prev=(*tail);
next=(*node);
tmp=(struct ednode *)((unsigned int)(NULL)^(unsigned int)(prev));
prev->ptr=(struct ednode *)((unsigned int)(tmp)^(unsigned int)(next));
next->ptr=(struct ednode *)((unsigned int)(NULL)^(unsigned int)(prev));
(*tail)=next; 
}

}
void print_ednode(struct ednode **head,struct ednode **tail){
struct ednode *tmp,*prev,*next;
if((*head)==NULL) return;
tmp=(*head);
prev=NULL;
while(tmp!=(*tail)){
printf(" %d ",tmp->val);
tmp=(struct ednode *)((unsigned int)(tmp->ptr)^(unsigned int)(prev));
prev=tmp;
}
printf(" %d ",tmp->val);
}
void printrev_ednode(struct ednode **head,struct ednode **tail){
struct ednode *tmp,*prev,*next;
if((*head)==NULL) return;
tmp=(*tail);
prev=NULL;
while(tmp!=(*head)){
printf(" %d ",tmp->val);
tmp=(struct ednode *)((unsigned int)(tmp->ptr)^(unsigned int)(prev)); 
prev=tmp; 
}
printf(" %d ",tmp->val);
}
int main(){
printf("\n Efficient Doubly Linked List ");
struct ednode *head=NULL,*node=NULL,*tail=NULL,*prev=NULL,*tmp;
int key,ival;
do{
printf("\n************* Efficient Doubly Linked List Menu *************");
printf("\n************* Coded by Codingstreet.com *************");
printf("\n[1] Insert Node : ");
printf("\n[2] Print List : ");
printf("\n[3] print rev list : ");
printf("\n[4] (Exit) ");
printf("\nEnter the key : ");
scanf("%d",&key);
printf("\n");
switch(key){
case 1:
printf("\nEntet the input value ");
scanf("%d",&ival);
if(create_ednode(ival,&node))
insert_ednode(&head,&node,&tail);
else printf("\n System id out of Memory !! ");
break;
case 2:
print_ednode(&head,&tail);
break;
case 3:
printrev_ednode(&head,&tail);
break;
case 4:
break;
default:
printf("\n Enter the VALID KEY [1,2,3,4] ");
break;}
}while(key!=4);
printf("\n Thanks for using codingstreet.com 's Data structure solution ");
return 0; 
}

/*C Code for Memory Efficient Doubly linked list by Codingstreet.com*/

#include<stdio.h>

#include<stdlib.h>

struct ednode{

int val;

struct ednode *ptr;

};

int create_ednode(int val,struct ednode **node){

struct ednode *tmp;

tmp=malloc(sizeof(struct ednode));

if(tmp==NULL) return 0;

tmp->val=val;

tmp->ptr=NULL;

(*node)=tmp;

return 1;

}

void insert_ednode(struct ednode **head,struct ednode **node,struct ednode **tail){

struct ednode *prev,*next,*tmp;

if((*head)==NULL && (*tail)==NULL){

(*head)=(*tail)=(*node);

(*head)->ptr=NULL;

}

else if((*head)->ptr==NULL){

next=(*node);

(*head)->ptr=(struct ednode *)((unsigned int)(NULL)^(unsigned int)(next));

next->ptr=(struct ednode *)((unsigned int)(*head)^(unsigned int)(NULL));

(*tail)=(*node);

}

else {

prev=(*tail);

next=(*node);

tmp=(struct ednode *)((unsigned int)(NULL)^(unsigned int)(prev));

prev->ptr=(struct ednode *)((unsigned int)(tmp)^(unsigned int)(next));

next->ptr=(struct ednode *)((unsigned int)(NULL)^(unsigned int)(prev));

(*tail)=next;

}

void print_ednode(struct ednode **head,struct ednode **tail){

struct ednode *tmp,*prev,*next;

if((*head)==NULL) return;

tmp=(*head);

prev=NULL;

while(tmp!=(*tail)){

printf(" %d ",tmp->val);

tmp=(struct ednode *)((unsigned int)(tmp->ptr)^(unsigned int)(prev));

prev=tmp;

}

printf(" %d ",tmp->val);

}

void printrev_ednode(struct ednode **head,struct ednode **tail){

struct ednode *tmp,*prev,*next;

if((*head)==NULL) return;

tmp=(*tail);

prev=NULL;

while(tmp!=(*head)){

printf(" %d ",tmp->val);

tmp=(struct ednode *)((unsigned int)(tmp->ptr)^(unsigned int)(prev));

prev=tmp;

}

printf(" %d ",tmp->val);

}

int main(){

printf("\n Efficient Doubly Linked List ");

struct ednode *head=NULL,*node=NULL,*tail=NULL,*prev=NULL,*tmp;

int key,ival;

do{

printf("\n************* Efficient Doubly Linked List Menu *************");

printf("\n************* Coded by Codingstreet.com *************");

printf("\n[1] Insert Node : ");

printf("\n[2] Print List : ");

printf("\n[3] print rev list : ");

printf("\n[4] (Exit) ");

printf("\nEnter the key : ");

scanf("%d",&key);

printf("\n");

switch(key){

case 1:

printf("\nEntet the input value ");

scanf("%d",&ival);

if(create_ednode(ival,&node))

insert_ednode(&head,&node,&tail);

else printf("\n System id out of Memory !! ");

break;

case 2:

print_ednode(&head,&tail);

break;

case 3:

printrev_ednode(&head,&tail);

break;

case 4:

break;

default:

printf("\n Enter the VALID KEY [1,2,3,4] ");

break;}

}while(key!=4);

printf("\n Thanks for using codingstreet.com 's Data structure solution ");

return 0;

}

Structure for doubly linked list

struct dnode{
int val;
struct dnode *next,*prev;
};
/* Doubly linked list Menu
[1] Insert Node:
[2] Delete Node:
[3] Print List:
[4] Print List Reverse :
[5] Find Node :
[6] Exit:
*/

/* C Code for Doubly linked list by Codingstreet.com */
 #include<stdio.h> 
#include<stdlib.h>
 struct dnode{ int val;
 struct dnode *next,*prev;
 };
 int create_dnode(int val,struct dnode **node){ struct dnode *tmp;
tmp=malloc(sizeof(struct dnode));
 if(tmp==NULL) return 0;
 tmp->val=val;
 tmp->next=NULL;
 tmp->prev=NULL;
 *node=tmp;
 return 1;
 }
 int insert_dnode(struct dnode **head,struct dnode **node ){ if((*head)==NULL){ (*head)=(*node);
 (*head)->next=NULL;
 (*head)->prev=NULL;
 } else { struct dnode *root;
 root=(*head);
 struct dnode *next,*prev,*tmp;
 next=root->next;
 prev=tmp=root;
 while(next!=NULL){ prev=tmp;
 tmp=tmp->next;
 next=tmp;
 } prev->next=(*node);
 (*node)->prev=prev;
 next=prev->next;
 next->next=NULL;
 } return 1;
 } void print_dll(struct dnode **head){ struct dnode *tmp;
 tmp=(*head);
 while(tmp!=NULL){ printf(" %d ",tmp->val);
 tmp=tmp->next;
 } printf("\n");
 } void print_dll_reverse(struct dnode **head){ struct dnode *tmp;
 tmp=(*head);
 if(tmp==NULL) return;
 while(tmp->next!=NULL){ tmp=tmp->next;
 } while(tmp!=NULL){ printf(" %d ",tmp->val);
 tmp=tmp->prev;
 } printf("\n");
 } int delete_dnode(struct dnode **head,struct dnode **node){ struct dnode *root,*tmp,*next,*prev,*dlnode;
 root=*head;
 dlnode=*node;
 if(root==NULL){ return 0;
 } else if(root==dlnode && root->next==NULL){ free(root);
 *head=NULL;
 } else if(root==dlnode){ next=root->next;
 root->next=NULL;
 next->prev=NULL;
 free(root);
 root=next;
 *head=root;
 return 1;
 } else { tmp=*head;
 next=tmp->next;
 prev=tmp;
 while(tmp!=NULL){ if(tmp==dlnode){ prev->next=tmp->next;
 tmp->next=prev;
 tmp->next=NULL;
 tmp->prev=NULL;
 free(tmp);
 return 1;
 } prev=tmp;
 tmp=tmp->next;
 } return 0;
 } } struct dnode *find_dnode(struct dnode **head,int val){ struct dnode *root;
 root=*head;
 if(root==NULL){ return NULL;
 } else if(root->val==val){ return root;
} else { struct dnode *tmp;
 tmp=root;
 while(tmp!=NULL){ if(tmp->val==val){ return tmp;
 } tmp=tmp->next;
} return tmp;
 } } int main(){ struct dnode *head=NULL,*node=NULL;
 int val,ival;
 do { printf("\n----------------------------------");
 printf("\n Doubly Linked List Menu : \n");
 printf("[1] Insert Node: \n");
 printf("[2] Delete Node: \n");
 printf("[3] Print List: \n");
 printf("[4] Print List Reverse : \n");
 printf("[5] Find Node :\n");
 printf("[6] Exit: \n");
 printf("Enter the input:");
 scanf("%d",&val);
 printf("----------------------------------\n");
 switch(val){ case 1: printf("\n Enter the Val :");
 scanf("%d",&ival);
 if(create_dnode(ival,&node)){ insert_dnode(&head,&node);
} else printf("!!!@@@ System is outof Memory @@@!!!\n");
 break;
 case 2: printf("\n Delete the Val :");
 scanf("%d",&ival);
 node=find_dnode(&head,ival);
 if(node!=NULL){ delete_dnode(&head,&node);
 } else printf(" The Node Value not found \n");
 break;
 case 3: printf("\n The Doubly List is : \n");
 print_dll(&head);
 break;
 case 4: print_dll_reverse(&head);
 break;
 case 5: printf("\n Enter the Val to Find:");
 scanf("%d",&ival);
 node=find_dnode(&head,ival);
 if(node==NULL) printf("\t *** Value Not Found !! ***\n");
 else printf("\t ** Value Found ***\n");
 break;
 case 6: break;
 default: printf("===> [ Enter the Correct input] <==== \n");
 break;
 } }while(val!=6);
 printf(" \n[Thank you!! for using codingstreet.com 's Data Structure Solutions !!] \n\n");
 return 0;
 }

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

/* C Code for Doubly linked list by Codingstreet.com */

#include<stdio.h>

#include<stdlib.h>

struct dnode{ int val;

struct dnode *next,*prev;

};

int create_dnode(int val,struct dnode **node){ struct dnode *tmp;

tmp=malloc(sizeof(struct dnode));

if(tmp==NULL) return 0;

tmp->val=val;

tmp->next=NULL;

tmp->prev=NULL;

*node=tmp;

return 1;

}

int insert_dnode(struct dnode **head,struct dnode **node ){ if((*head)==NULL){ (*head)=(*node);

(*head)->next=NULL;

(*head)->prev=NULL;

} else { struct dnode *root;

root=(*head);

struct dnode *next,*prev,*tmp;

next=root->next;

prev=tmp=root;

while(next!=NULL){ prev=tmp;

tmp=tmp->next;

next=tmp;

} prev->next=(*node);

(*node)->prev=prev;

next=prev->next;

next->next=NULL;

} return 1;

} void print_dll(struct dnode **head){ struct dnode *tmp;

tmp=(*head);

while(tmp!=NULL){ printf(" %d ",tmp->val);

tmp=tmp->next;

} printf("\n");

} void print_dll_reverse(struct dnode **head){ struct dnode *tmp;

tmp=(*head);

if(tmp==NULL) return;

while(tmp->next!=NULL){ tmp=tmp->next;

} while(tmp!=NULL){ printf(" %d ",tmp->val);

tmp=tmp->prev;

} printf("\n");

} int delete_dnode(struct dnode **head,struct dnode **node){ struct dnode *root,*tmp,*next,*prev,*dlnode;

root=*head;

dlnode=*node;

if(root==NULL){ return 0;

} else if(root==dlnode && root->next==NULL){ free(root);

*head=NULL;

} else if(root==dlnode){ next=root->next;

root->next=NULL;

next->prev=NULL;

free(root);

root=next;

*head=root;

return 1;

} else { tmp=*head;

next=tmp->next;

prev=tmp;

while(tmp!=NULL){ if(tmp==dlnode){ prev->next=tmp->next;

tmp->next=prev;

tmp->next=NULL;

tmp->prev=NULL;

free(tmp);

return 1;

} prev=tmp;

tmp=tmp->next;

} return 0;

} } struct dnode *find_dnode(struct dnode **head,int val){ struct dnode *root;

root=*head;

if(root==NULL){ return NULL;

} else if(root->val==val){ return root;

} else { struct dnode *tmp;

tmp=root;

while(tmp!=NULL){ if(tmp->val==val){ return tmp;

} tmp=tmp->next;

} return tmp;

} } int main(){ struct dnode *head=NULL,*node=NULL;

int val,ival;

do { printf("\n----------------------------------");

printf("\n Doubly Linked List Menu : \n");

printf("[1] Insert Node: \n");

printf("[2] Delete Node: \n");

printf("[3] Print List: \n");

printf("[4] Print List Reverse : \n");

printf("[5] Find Node :\n");

printf("[6] Exit: \n");

printf("Enter the input:");

scanf("%d",&val);

printf("----------------------------------\n");

switch(val){ case 1: printf("\n Enter the Val :");

scanf("%d",&ival);

if(create_dnode(ival,&node)){ insert_dnode(&head,&node);

} else printf("!!!@@@ System is outof Memory @@@!!!\n");

break;

case 2: printf("\n Delete the Val :");

scanf("%d",&ival);

node=find_dnode(&head,ival);

if(node!=NULL){ delete_dnode(&head,&node);

} else printf(" The Node Value not found \n");

break;

case 3: printf("\n The Doubly List is : \n");

print_dll(&head);

break;

case 4: print_dll_reverse(&head);

break;

case 5: printf("\n Enter the Val to Find:");

scanf("%d",&ival);

node=find_dnode(&head,ival);

if(node==NULL) printf("\t *** Value Not Found !! ***\n");

else printf("\t ** Value Found ***\n");

break;

case 6: break;

default: printf("===> [ Enter the Correct input] <==== \n");

break;

} }while(val!=6);

printf(" \n[Thank you!! for using codingstreet.com 's Data Structure Solutions !!] \n\n");

return 0;

}

Codingstreet

Tag Archives: Doubly linked list in C

Memory Efficient doubly linked list in C

Doubly Linked List in C

A place to brush your coding skills