C++ Program to Implement Xor Linked List

C++ Program to Implement Xor Linked List

XOR linked list is a data structure. Its is same as double linked list and most efficient than double linked list,because it uses only one pointer to traversal backward and forward.
This XOR linked list an be in one statement that is :
node->next=(prev XOR next
let me illustrate
There are 3 nodes with 2 fields :one data and another link
data field  is data you entered.
link field is previous node address bitwise XOR next node address.
For display

#include <inttypes.h> #include <iostream> using namespace std; struct node{ int data; struct node* nXp; }; struct node* XOR(struct node* a,struct node* b){ return (struct node*)((uintptr_t)(a)^(uintptr_t)(b)); } void insert(struct node **head,int data){ struct node* new_node=(struct node*)malloc(sizeof(struct node)); new_node->data=data; new_node->nXp=XOR(*head,NULL); if(*head!=NULL){ struct node* nXp=XOR((*head)->nXp,NULL); (*head)->nXp=XOR(new_node,nXp); } *head=new_node; } void display(struct node* head){ struct node* curr=head; struct node* prev=NULL; struct node* next; cout<<"display elements"; while(curr!=NULL){ cout<<curr->data<<" "; next=XOR(prev,curr->nXp); prev=curr; curr=next; } } int main() { struct node* head=NULL; int n,i,a; cout<<"enter no of elements to insert:"; cin>>n; cout<<"enter elements:"; for(i=0;i<n;i++){ cin>>a; insert(&head,a); } display(head); return 0; }
enter no of elements to insert:5
enter elements:1 2 3 4 5
displaying elements
5 4 3 2 1

More Articles of Dasari Bhavani:

Name Views Likes
C++ Program to Implement Xor Linked List 399 20