Doubly Linked List needs two pointers to maintain the previous and next pointer value so that we can traverse in both forward and reverse direction. However, maintaining two pointers may be costly for the system with low memory. For such circumstances we have an option to create a double linked list with a single pointer. This is attainable by the use of XOR.
Steps to create DLL:
- For, after creating the first node, make its pointer point to NULL.
- Now, create a next node and then make it point to the predecessor node.
- The pointer of the predecessor node is XOR with the current node. i.e. pred->pointer= pred->pointer ^ current_node
- Jump to Step 2 to add more elements
Displaying the DLL
- Check the list to be displayed is empty. If so, return.
- Use two additional pointers prev and temp. Initialize prev to NULL.
- Now, save list to temp variable.
- Find new value of list by: list=list->ptr ^ prev.
- Set prev=temp.
- Jump to Step 3 until list become NULL
Displaying in Reverse direction
It can be done in the same way as Displaying element but here you need to be in the last element and then you can traverse forward.
Code:
#include#include struct node; typedef struct node NODE; struct node { int info; struct node *ptr; }; void create_list(int a[],NODE **list,int size) { NODE *temp,*new_node; temp=*list; int i; for(i=0;i ptr=NULL; temp->info=a[0]; *list=temp; } else { new_node=(NODE*)malloc(sizeof(struct node)); new_node->info=a[i]; new_node->ptr=temp; temp->ptr=(NODE*)((long)temp->ptr ^ (long)new_node); temp=new_node; } } } void display_normal(NODE *list) { NODE *temp,*prev; prev=NULL; if(list==NULL) return; printf("\n\n\n"); do { printf(" %d ",list->info); temp=list; list=(NODE*)((long)list->ptr ^ (long)prev); prev=temp; }while(list!=NULL); } void display_rev(NODE *list) { NODE *temp,*prev; prev=NULL; if(list==NULL) return; do { temp=list; list=(NODE*)((long)list->ptr ^ (long)prev); prev=temp; }while(list!=NULL); printf("\n\n\n"); list=prev; prev=NULL; do { printf(" %d ",list->info); temp=list; list=(NODE*)((long)list->ptr ^ (long)prev); prev=temp; }while(list!=NULL); } int main() { int a[]={23,45,78,90,12,10}; NODE *list; list=NULL; create_list(a,&list,sizeof(a)/sizeof(a[0])); display_normal(list); display_rev(list); getchar(); return 0; }
I'm happy to find numerous useful info here in the post. I would really like to come back again right here for likewise good articles or blog posts. Thanks for sharing...
ReplyDeleteTop MBA Colleges in Mumbai
top MBA schools in Mumbai
Your article has piqued a lot of positive interest. I can see why since you have done such a good job of making it interesting. beko ana bayi
ReplyDelete