XOR Linked List | C ++ program for the above approach ; Structure of a node in XOR linked list ; Stores data value of a node ; Stores XOR of previous pointer and next pointer ; Function to find the XOR of two nodes ; Function to insert a node with given value at beginning position ; If XOR linked list is empty ; Initialize a new Node ; Stores data value in the node ; Stores XOR of previous and next pointer ; Update pointer of head node ; If the XOR linked list is not empty ; Stores the address of current node ; Stores the address of previous node ; Initialize a new Node ; Update curr node address ; Update new node address ; Update head ; Update data value of current node ; Function to print elements of the XOR Linked List ; Stores XOR pointer in current node ; Stores XOR pointer of in previous Node ; Stores XOR pointer of in next node ; Traverse XOR linked list ; Print current node ; Forward traversal ; Update prev ; Update curr ; Function to reverse the XOR linked list ; Stores XOR pointer in current node ; Stores XOR pointer of in previous Node ; Stores XOR pointer of in next node ; Forward traversal ; Update prev ; Update curr ; Update the head pointer ; Driver Code ; Create following XOR Linked List head -- > 40 < -- > 30 < -- > 20 < -- > 10 ; Reverse the XOR Linked List to give head -- > 10 < -- > 20 < -- > 30 < -- > 40
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * nxp ; } ; Node * XOR ( Node * a , Node * b ) { return ( Node * ) ( ( uintptr_t ) ( a ) ^ ( uintptr_t ) ( b ) ) ; } Node * insert ( Node * * head , int value ) { if ( * head == NULL ) { Node * node = new Node ( ) ; node -> data = value ; node -> nxp = XOR ( NULL , NULL ) ; * head = node ; } else { Node * curr = * head ; Node * prev = NULL ; Node * node = new Node ( ) ; curr -> nxp = XOR ( node , XOR ( NULL , curr -> nxp ) ) ; node -> nxp = XOR ( NULL , curr ) ; * head = node ; node -> data = value ; } return * head ; } void printList ( Node * * head ) { Node * curr = * head ; Node * prev = NULL ; Node * next ; while ( curr != NULL ) { cout << curr -> data << " ▁ " ; next = XOR ( prev , curr -> nxp ) ; prev = curr ; curr = next ; } cout << endl ; } Node * reverse ( Node * * head ) { Node * curr = * head ; if ( curr == NULL ) return NULL ; else { Node * prev = NULL ; Node * next ; while ( XOR ( prev , curr -> nxp ) != NULL ) { next = XOR ( prev , curr -> nxp ) ; prev = curr ; curr = next ; } * head = curr ; return * head ; } } int main ( ) { Node * head = NULL ; insert ( & head , 10 ) ; insert ( & head , 20 ) ; insert ( & head , 30 ) ; insert ( & head , 40 ) ; cout << " XOR ▁ linked ▁ list : ▁ " ; printList ( & head ) ; reverse ( & head ) ; cout << " Reversed ▁ XOR ▁ linked ▁ list : ▁ " ; printList ( & head ) ; return 0 ; }