XOR Linked List | C ++ program to implement 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 given position ; If XOR linked list is empty ; If given position is equal to 1 ; Initialize a new Node ; Stores data value in the node ; Stores XOR of previous and next pointer ; Update pointer of head node ; If required position was not found ; If the XOR linked list is not empty ; Stores position of a node in the XOR linked list ; Stores the address of current node ; Stores the address of previous node ; Stores the XOR of next node and previous node ; Traverse the XOR linked list ; Update prev ; Update curr ; Update next ; Update Pos ; If the position of the current node is equal to the given position ; Initialize a new Node ; Stores pointer to previous Node as ( prev ^ next ^ next ) = prev ; Stores XOR of prev and new node ; Connecting new node with next ; Update pointer of next ; Connect node with curr and next curr < -- node -- > next ; Insertion node at beginning ; 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 ; Driver Code ; Create following XOR Linked List head -- > 20 < -- > 40 < -- > 10 < -- > 30 ; Print the new list
#include <bits/stdc++.h> NEW_LINE 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 ) ) ; } struct Node * insert ( struct Node * * head , int value , int position ) { if ( * head == NULL ) { if ( position == 1 ) { struct Node * node = new Node ( ) ; node -> data = value ; node -> nxp = XOR ( NULL , NULL ) ; * head = node ; } else { cout << " Invalid ▁ Position STRNEWLINE " ; } } else { int Pos = 1 ; struct Node * curr = * head ; struct Node * prev = NULL ; struct Node * next = XOR ( prev , curr -> nxp ) ; while ( next != NULL && Pos < position - 1 ) { prev = curr ; curr = next ; next = XOR ( prev , curr -> nxp ) ; Pos ++ ; } if ( Pos == position - 1 ) { struct Node * node = new Node ( ) ; struct Node * temp = XOR ( curr -> nxp , next ) ; curr -> nxp = XOR ( temp , node ) ; if ( next != NULL ) { next -> nxp = XOR ( node , XOR ( next -> nxp , curr ) ) ; } node -> nxp = XOR ( curr , next ) ; node -> data = value ; } else if ( position == 1 ) { struct Node * node = new Node ( ) ; curr -> nxp = XOR ( node , XOR ( NULL , curr -> nxp ) ) ; node -> nxp = XOR ( NULL , curr ) ; * head = node ; node -> data = value ; } else { cout << " Invalid ▁ Position STRNEWLINE " ; } } return * head ; } void printList ( struct Node * * head ) { struct Node * curr = * head ; struct Node * prev = NULL ; struct Node * next ; while ( curr != NULL ) { cout << curr -> data << " ▁ " ; next = XOR ( prev , curr -> nxp ) ; prev = curr ; curr = next ; } } int main ( ) { struct Node * head = NULL ; insert ( & head , 10 , 1 ) ; insert ( & head , 20 , 1 ) ; insert ( & head , 30 , 3 ) ; insert ( & head , 40 , 2 ) ; printList ( & head ) ; return 0 ; }