Pranit Kothari Pranit Kothari - 2 months ago 12
C Question

How 'memory efficient doubly linked list' works?

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

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;
    }
}
Comments