How 'memory efficient doubly linked list' works?

Question

In Data Structures and Algorithms Made Easy, struct of memory efficient memory list given as follows,

struct LinkNode
{
 int data;
 struct LinkNode* ptrdiff;
}

In ptrdiff, there will be xoring of previous and next node is done. For example, previous node have address 100 and next node address is 500.

So, in ptrdiff address will be 400. Now how it is possible to move to next or previous node (as we do in doubly link list), just by knowing xoring of their addresses?

Am I missing any step here?

Answer 1

The first node has no previous node, and the last node has no next node ... so think of the address of the node before the first and of the node after the last as 0. That's enough to start a traversal, and as you traverse you always have the address of the preceding node in hand so you can determine the address of the succeeding node. Here's an example of traversing such a list and printing the data ... pass the address of either the first or last node to printxorlist and it will print it either forwards or backwards:

void printxorlist(struct LinkNode* node)
{
    struct LinkNode* prev = NULL;
    while (node)
    {
        printf("%d\n", node->data);
        struct LinkNode* next = (struct LinkNode*)((intptr_t)node->ptrdiff ^ (intptr_t)prev);
        prev = node;
        node = next;
    }
}

Note that we have to cast node->ptrdiff because it doesn't really have the right type. Better would be to declare it correctly:

struct LinkNode
{
    int data;
    intptr_t ptrdiff;
}

then

void printxorlist(struct LinkNode* node)
{
    struct LinkNode* prev = NULL;
    while (node)
    {
        printf("%d\n", node->data);
        struct LinkNode* next = (struct LinkNode*)(node->ptrdiff ^ (intptr_t)prev);
        prev = node;
        node = next;
    }
}

Answer 2

In this type of linked list, you can not traverse from the address of any arbitrary node. Because you need some extra information either about predecessor address or successor address. But traversing from the first node(predecessor address =0 , since not any predecessor) or last node(successor address=0, since not any successor) is possible.