C++ Program to Implement Xor Linked List

«
»
This C++ Program demonstrates operations on Xor Linked List.

Here is source code of the C++ Program to demonstrate XOR Linked List. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* 
  2.  * C++ Program To Implement XOR Linked List 
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. using namespace std;
  7. /* 
  8.  * Node Declaration
  9.  */
  10. struct node
  11. {
  12.     int data;
  13.     struct node* npx;
  14. }*head;
  15.  
  16. /*
  17.  * Class Declaration
  18.  */
  19. class xor_list
  20. {
  21.     public:
  22.         node* XOR (struct node *a, struct node *b);
  23.         void insert(struct node **head_ref, int data);
  24.         void display (struct node *head);
  25.         xor_list()
  26.         {
  27.             head = NULL;	
  28.         }
  29. };
  30.  
  31. /*
  32.  * Main Contains Menu
  33.  */
  34. int main()
  35. {
  36.     xor_list xl;
  37.     int choice, item;
  38.     while (1)
  39.     {
  40.         cout<<"\n-------------"<<endl;
  41.         cout<<"Operations on XOR Linked List"<<endl;
  42.         cout<<"\n-------------"<<endl;
  43.         cout<<"1.Insert Element at First"<<endl;
  44.         cout<<"2.Display List"<<endl;
  45.         cout<<"3.Quit"<<endl;
  46.         cout<<"Enter your Choice: ";
  47.         cin>>choice;
  48.         switch(choice)
  49.         {
  50.         case 1:
  51.             cout<<"Enter value to be inserted: ";
  52.             cin>>item;
  53.             xl.insert(&head, item);
  54.             break;
  55.         case 2:
  56.             xl.display (head);
  57.             break;
  58.         case 3:
  59.             exit(1);
  60.             break;
  61.         default:
  62.             cout<<"Wrong Choice"<<endl;
  63.         }
  64.     }
  65.     return 0;
  66. }
  67.  
  68. /* 
  69.  * Returns XORed value of the node addressed
  70.  */
  71. node *xor_list::XOR (struct node *a, struct node *b)
  72. {
  73.     return (node*) ((unsigned int) (a) ^ (unsigned int) (b));
  74. }
  75.  
  76. /* 
  77.  * Insert Node at Beginning
  78.  */
  79. void xor_list::insert(struct node **head_ref, int data)
  80. {
  81.     node *new_node  = new (struct node);
  82.     new_node->data = data;
  83.     new_node->npx = XOR (*head_ref, NULL);
  84.     if (*head_ref != NULL)
  85.     {
  86.         node* next = XOR ((*head_ref)->npx,  NULL);
  87.         (*head_ref)->npx = XOR (new_node, next);
  88.     }
  89.     *head_ref = new_node;
  90. }
  91.  
  92. // Display List
  93. void xor_list::display (struct node *head)
  94. {
  95.     node *curr = head;
  96.     node *prev = NULL;
  97.     node *next;
  98.     cout<<"Elements of XOR Linked List: "<<endl;
  99.     while (curr != NULL)
  100.     {
  101.         cout<<curr->data<<" ";
  102.         next = XOR (prev, curr->npx);
  103.         prev = curr;
  104.         curr = next;
  105.     }
  106.     cout<<endl;
  107. }

advertisement
$ 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
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.