Wednesday, October 17, 2012

C program for double linked list using single pointer


Below is the C program to implement the double linked list using single pointer.  Or we can say it as backward traversal of a single linked list. For implementing this program I used the logic of XOR. click here for clear explaination.


#include<stdio.h>
#include<stdlib.h> 
//linked list structure
struct node
{
    int info;
    struct node *next;
};
 
//making typdef so we can use Node instead of 'struct node'
typedef struct node Node;

//back traverse of single linked list 
// for that first we need to traverse till the last node in the list 
void backTraverse(Node *h)
{
     Node *temp = h;
     Node *tempPrev = NULL;
     Node *prev = NULL;

     //need to traverse to the last node
     while (temp->next!=NULL)
     {
           tempPrev = temp;
           temp= (Node *)((unsigned long)temp->next ^ (unsigned long)prev);
           prev = tempPrev;
     }
    //Now temp is at last node
    tempPrev = prev;
    while(temp!=h)
    {
       printf("%d->",temp->info); 
       prev = (Node *)((unsigned long)prev->next ^ (unsigned long)temp);
       temp = tempPrev;
       tempPrev = prev;
    }
    printf("%d\n",temp->info); 
}
 
//inserting node or creating the list or adding the element @ end
Node* insert(Node *h, int info)
{
     Node *tempHead=h;
     Node *prev = NULL;
     Node *tempPrev = NULL;
     Node *newNode = (Node*)malloc(sizeof(Node));
     newNode->info = info;
     newNode->next = NULL;
     if(tempHead == NULL) // if the list has zero elements. make new node as a head
     {
          h=newNode;
     }
     else if(tempHead->next==NULL)  // if the list is having only one node
     {
          tempHead->next = (Node *)((unsigned long)prev ^ (unsigned long)newNode);
     }
     else
     {
          Node *tempNode = h;
          while(tempNode->next != NULL)  //moving to the last node
          {
               tempPrev = tempNode;
               tempNode = (Node *)((unsigned long)tempNode->next ^ (unsigned long)prev);
               prev = tempPrev;
               //tempNode = tempNode->next;
          }
          tempNode->next =(Node *) ((unsigned long)prev ^ (unsigned long)newNode);
     }
     return h;
}
 
/*****************************************************************************
for displaying the nodes in the list
*****************************************************************************/
void display(Node *h)
{
     Node *temp = h;
     while (temp->next!=NULL)
     {
          printf("%d->",temp->info);
          temp = temp->next;
     }
     printf("%d\n",temp->info);
}
 
int main()
{
     Node *head = NULL;
     int i;
     for (i=1;i<=10;i++)
     {
          head = insert(head,i*2);
     }
     //traversing the single linked list farward and displaying 
     display(head);

     //travrsing the single linked list backwards from last or end
     backTraverse(head);
} 

Popular Posts