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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
/*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; } |