c - 'memory efficient doubly linked list' 是如何工作的？

Question

在Data Structures and Algorithms Made Easy , struct 内存高效内存列表给出如下,

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

在ptrdiff中，将完成上一个节点和下一个节点的异或运算。例如，前一个节点的地址为100，下一个节点的地址为500。

因此，在 ptrdiff 中地址将为 400。现在如何移动到下一个或上一个节点(就像我们在双向链表中所做的那样)，仅仅通过知道它们的地址的异或？

我是否遗漏了任何步骤？

Answer 1

第一个节点没有前一个节点，最后一个节点没有下一个节点...所以将第一个节点之前的节点和最后一个节点之后的节点的地址视为0。这足以开始遍历，当你遍历时，你手头总是有前一个节点的地址，这样你就可以确定后一个节点的地址。下面是遍历这样一个列表并打印数据的示例……将第一个或最后一个节点的地址传递给 printxorlist，它将向前或向后打印它:

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

请注意，我们必须强制转换 node->ptrdiff，因为它实际上没有正确的类型。最好是正确地声明它:

struct LinkNode
{
    int data;
    intptr_t ptrdiff;
}

然后

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