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);
}