Doubly link list

Question

I am trying to make a memory efficient doubly linked list. The list stores the XOR of the next and the previous addresses, but I am facing an error in the function XOR. The error is:

[Error] cast from 'node*' to 'unsigned int' loses precision [-fpermissive] 

My code is:

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node *next;
}*start,*temp;
node* XOR(node *a,node *b)
{
    return (node *)((unsigned int)(a)^(unsigned int)(b));   
}
void push(int data)
{
    node *a=new node;
    a->data=data;
    a->next=XOR(start,NULL);
    if(start!=NULL)
    start->next=XOR(start->next,a);
    start=a;
}
void disp()
{
    temp=start;
    node *prev,*cur;
    while(temp)
    {
        cout<<temp->data<<" ";
        if(temp==start)
        {
            prev=temp;
            temp=temp->next;
        }
        else
        {
            cur=temp;
            temp=XOR(temp->next,prev);
            prev=cur;
        }
    }
}
main()
{
    start=NULL;
    push(1);
    push(2);
    push(3);
    push(4);
    push(5);
    push(6);
    push(7);
    push(8);
}

Answer 1

An unsigned int is not guaranteed to be as large as a a pointer, in many cases a pointer is 64 bits and an unsigned int 32 bits. Therefore in this case the upper 32 bits are discarded, invalidating the pointer. You need a uintptr_t instead of an unsigned int.

The corrected code must first:

#include <cstdint>

Somewhere at the top in order to add a declaration for uintptr_t as well as a variety of other useful types and second change the line:

return (node *)((unsigned int)(a)^(unsigned int)(b));

To:

return (node *)((uintptr_t)(a)^(uintptr_t)(b));

Please take a look here for a much better explanation of how uintptr_t and other similar types work http://www.cplusplus.com/reference/cstdint/

Finally I shall mention that in most modern machines a xored linked list will actually be slower, not faster than a normal doubly linked list as the technique makes it much harder for the CPU and compiler to predict what you are doing and optimise well and this effect is greater than the speed boost from small space saving.