text: 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 program to test above functions ; Create following Doubly Linked List head -- > 40 < -- > 30 < -- > 20 < -- > 10 ; print the created list
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE #include <inttypes.h> NEW_LINE struct Node { int data ; struct Node * npx ; } ; struct Node * XOR ( struct Node * a , struct Node * b ) { return ( struct Node * ) ( ( uintptr_t ) ( a ) ^ ( uintptr_t ) ( b ) ) ; } void insert ( struct Node * * head_ref , int data ) { struct Node * new_node = ( struct Node * ) malloc ( sizeof ( struct 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 ( struct Node * head ) { struct Node * curr = head ; struct Node * prev = NULL ; struct Node * next ; printf ( " Following ▁ are ▁ the ▁ nodes ▁ of ▁ Linked ▁ List : ▁ STRNEWLINE " ) ; while ( curr != NULL ) { printf ( " % d ▁ " , curr -> data ) ; next = XOR ( prev , curr -> npx ) ; prev = curr ; curr = next ; } } int main ( ) { struct Node * head = NULL ; insert ( & head , 10 ) ; insert ( & head , 20 ) ; insert ( & head , 30 ) ; insert ( & head , 40 ) ; printList ( head ) ; return ( 0 ) ; }