Optimized Linked list using XOR operation over pointers.

xor_linked_list.cpp

// this implementation use xor to show the capability over pointers.
// let have 4 nodes A, B, C, D with their respective `next` pointer having
// a reference to the next and previous node(which make the list double linked).
//
// the linked list is built backward(new node become head). This implementation state that.
//
// A.pxor = B.xor(null) which is B.
// B.pxor = A.xor(C) which serve us to find both A & C
// C.pxor = B.xor(D) which serve us to find both B & D
// D.pxor = C.xor(null) which point to the prev node.
//
// and since list growth backward. D becomes the head and C.xor points to the next node.
// the final list would look like:
//
//      D-->[c.xor(null)]-->C-->[b.xor(d)]-->B-->[a.xor(c)]-->A-->[b.xor(null)]
//
struct __node{
    __node* pxor;
    int data;
};

__node* __xor(__node* f, __node* s){
    return (__node*) ((unsigned long)f ^ (unsigned long)s);
}

void insert_node(__node** root, int data){
    __node* node = (__node*) malloc(sizeof(__node));
    node->data = data;

    // let point to the next node(aka. the actual root node)
    node->pxor = __xor(*root, nullptr);
    
    if(*root){
        (*root)->pxor = __xor((*root)->pxor, node); // create a xor for prev^next
    }
    *root = node;
}

__node* list_tail(__node* root){
    __node* ptr  = root;
    __node* prev = nullptr;
    do{
        __node* tmp  = ptr;
        ptr  = __xor(ptr->pxor, prev);
        prev = tmp;
    }while(ptr);
    
    return prev;
}


void traverse_forward(__node* root){
    __node* ptr  = root;
    __node* prev = nullptr;
    
    do{
        cout << ptr->data <<endl;
        
        __node* tmp  = ptr;
        ptr  = __xor(ptr->pxor, prev);
        prev = tmp;
    }while(ptr);
}


void traverse_backward(__node* root){
    __node* tail = list_tail(root);
    traverse_forward(tail);
}


int main(int argc, const char * argv[]) {
    
    __node* root = nullptr;
    insert_node(&root, 4);
    insert_node(&root, 6);
    insert_node(&root, 3);
    
    traverse_backward(root);
    
    return 0;
}