C++ Program to Implement Xor Linked List
#include <iostream>
#include <cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int data;
struct node* npx;
}*head;
/*
* Class Declaration
*/
class xor_list
{
public:
node* XOR (struct node *a, struct node *b);
void insert(struct node **head_ref, int data);
void display (struct node *head);
xor_list()
{
head = NULL;
}
};
/*
* Main Contains Menu
*/
int main()
{
xor_list xl;
int choice, item;
while (1)
{
cout<<"\n-------------"<<endl;
cout<<"Operations on XOR Linked List"<<endl;
cout<<"\n-------------"<<endl;
cout<<"1.Insert Element at First"<<endl;
cout<<"2.Display List"<<endl;
cout<<"3.Quit"<<endl;
cout<<"Enter your Choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter value to be inserted: ";
cin>>item;
xl.insert(&head, item);
break;
case 2:
xl.display (head);
break;
case 3:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
/*
* Returns XORed value of the node addressed
*/
node *xor_list::XOR (struct node *a, struct node *b)
{
return (node*) ((unsigned int) (a) ^ (unsigned int) (b));
}
/*
* Insert Node at Beginning
*/
void xor_list::insert(struct node **head_ref, int data)
{
node *new_node = new (struct node);
new_node->data = data;
new_node->npx = XOR (*head_ref, NULL);
if (*head_ref != NULL)
{
node* next = XOR ((*head_ref)->npx, NULL);
(*head_ref)->npx = XOR (new_node, next);
}
*head_ref = new_node;
}
// Display List
void xor_list::display (struct node *head)
{
node *curr = head;
node *prev = NULL;
node *next;
cout<<"Elements of XOR Linked List: "<<endl;
while (curr != NULL)
{
cout<<curr->data<<" ";
next = XOR (prev, curr->npx);
prev = curr;
curr = next;
}
cout<<endl;
}
Output:
$ g++ xor_list.cpp
$ a.out
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List:
100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 200
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List:
200 100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 300
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List:
300 200 100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 400
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List:
400 300 200 100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 500
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List:
500 400 300 200 100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 3
------------------
