XOR Linked List â €“ A Memory Efficient Doubly Linked List | Set 2 | C ++ Implementation of Memory efficient Doubly Linked List ; Node structure of a memory efficient doubly linked list ; XOR of next and previous node ; returns XORed value of the node addresses ; Insert a node at the beginning of the XORed linked list and makes the newly inserted node as head ; Allocate memory for new node ; Since new node is being inserted at the beginning , npx of new node will always be XOR of current head and NULL ; If linked list is not empty , then npx of current head node will be XOR of new node and node next to current head ; * ( head_ref ) -> npx is XOR of NULL and next . So if we do XOR of it with NULL , we get next ; Change head ; prints contents of doubly linked list in forward direction ; print current node ; get address of next node : curr -> npx is next ^ prev , so curr -> npx ^ prev will be next ^ prev ^ prev which is next ; update prev and curr for next iteration ; Driver code ; Create following Doubly Linked List head -- > 40 < -- > 30 < -- > 20 < -- > 10 ; print the created list
#include <bits/stdc++.h> NEW_LINE #include <cinttypes> NEW_LINE using namespace std ; class Node { public : int data ; Node * npx ; } ; Node * XOR ( Node * a , Node * b ) { return reinterpret_cast < Node * > ( reinterpret_cast < uintptr_t > ( a ) ^ reinterpret_cast < uintptr_t > ( b ) ) ; } void insert ( Node * * head_ref , int data ) { Node * new_node = new Node ( ) ; new_node -> data = data ; new_node -> npx = * head_ref ; if ( * head_ref != NULL ) { ( * head_ref ) -> npx = XOR ( new_node , ( * head_ref ) -> npx ) ; } * head_ref = new_node ; } void printList ( Node * head ) { Node * curr = head ; Node * prev = NULL ; Node * next ; cout << " Following ▁ are ▁ the ▁ nodes ▁ of ▁ Linked ▁ List : ▁ STRNEWLINE " ; while ( curr != NULL ) { cout << curr -> data << " ▁ " ; next = XOR ( prev , curr -> npx ) ; prev = curr ; curr = next ; } } int main ( ) { Node * head = NULL ; insert ( & head , 10 ) ; insert ( & head , 20 ) ; insert ( & head , 30 ) ; insert ( & head , 40 ) ; printList ( head ) ; return ( 0 ) ; }