Pranit Kothari - 2 months ago 12
C Question

# How 'memory efficient doubly linked list' works?

`struct`
of memory efficient memory list given as follows,

``````struct LinkNode
{
int data;
}
``````

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?

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)
{
while (node)
{
printf("%d\n", node->data);
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)
{