Doubly Linked List using Single Pointer

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:

1. For, after creating the first node, make its pointer point to NULL.
2. Now, create a next node and then make it point to the predecessor node.
3. The pointer of the predecessor node is XOR with the current node. i.e. pred->pointer= pred->pointer ^ current_node
4. Jump to Step 2 to add more elements

Displaying the DLL

1. Check the list to be displayed is empty. If so, return.
2. Use two additional pointers prev and temp. Initialize prev to NULL.
3. Now, save list to temp variable.
4. Find new value of list by: list=list->ptr ^ prev.
5. Set prev=temp.
6. 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;iptr=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;
}