### C Program to insert/delete/traverse/display XOR Linked List

Here is the C Program to insert/delete/traverse/display XOR Linked List.XOR linked list is said to be memory efficient version of doubly linked list.

_________________________________________________________________________________

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

struct Node{

int data;

struct Node *ptr;

};

struct Node* XOR(struct Node *a,struct Node *b){

return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));

}

void insertIntoXORLL(struct Node **head,int pos,int data){

struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));

newNode->data=data;

if(*head==NULL){ //Insert first Node

newNode->data=data;

newNode->ptr=NULL;

*head=newNode;

}else{

struct Node *current=*head;

struct Node *previous=NULL,*next=NULL;

struct Node *nextNode=NULL;

if(pos<=1){

newNode->ptr=XOR(previous,*head);

nextNode=XOR((*head)->ptr,previous);

(*head)->ptr=XOR(newNode,nextNode);

*head=newNode;

}else if(pos>1){

int count=1;

while(current!=NULL && count<(pos-1)){

next=XOR(current->ptr,previous);

previous=current;

current=next;count++;

}

if(current!=NULL){

next=XOR(current->ptr,previous);

}else{next=NULL;}

if(next!=NULL){

nextNode=XOR(next->ptr,current);

next->ptr=XOR(newNode,nextNode);

}

newNode->ptr=XOR(current,next);

current->ptr=XOR(previous,newNode);

}

}

}

void deleteElement(struct Node **head,int data){

struct Node *current=*head;

struct Node *previous=NULL,*next=NULL;

struct Node *previousNode,*nextNode;

while(current!=NULL && current->data!=data){

next=XOR(current->ptr,previous);

previous=current;

current=next;

}

if(current==NULL){

printf("There is no element with data=%d",data);

}else{

if(current==(*head) && current->ptr==NULL){

free(current);

}else if(current==(*head)){

next=XOR(current->ptr,previous);

next->ptr=XOR(current,next->ptr);

(*head)=next;

free(current);

}else if(current->ptr==NULL){

previous->ptr=NULL;

free(current);

}else{

next=XOR(current->ptr,previous);

previousNode=XOR(previous->ptr,current);

previous->ptr=XOR(previousNode,next);

nextNode=XOR(next->ptr,current);

next->ptr=XOR(previous,nextNode);

free(current);

}

}

}

void displayList(struct Node **head){

struct Node *current=*head;

struct Node *next=*head;

struct Node *previous=NULL;

printf("Linked list:\n");

while(current!=NULL){

printf("%d\n",current->data);

next=XOR(current->ptr,previous);

previous=current;

current=next;

}

}

void main(){

int choice,pos=0,data;

struct Node *head=NULL;

while(1){

printf("Enter Your Choice:\n");

printf("1.Insert Node at the certain position\n");

printf("2.Delete Node at the certain position\n");

printf("3.Display list\n");

printf("4.Exit\n");

scanf("%d",&choice);

switch(choice){

case 1:

printf("Enter Position(starts from 1) where you want to insert:");

scanf("%d",&pos);

printf("Enter Data Value you want to insert:");

scanf("%d",&data);

insertIntoXORLL(&head,pos,data);

break;

case 2:

printf("Enter Element You want to delete:");

scanf("%d",&data);

deleteElement(&head,data);

break;

case 3:

displayList(&head);

break;

case 4:

break;

}

}

}

_________________________________________________________________________________

## Comments

## Post a Comment