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

Popular posts from this blog

Getting started with Deep Learning Caffe Framework - Fastest way(Installation +Web Demo)

Sudoku using dancing link - Java implementation

OpenCV 2.4.9 JAVA/CPP/Python Installation in Ubuntu 14.04