c - “高效内存的双向链表”如何工作？

在存储器有效存储器列表的Data Structures and Algorithms Made Easy，struct中，如下所示，

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

在ptrdiff中，将执行前一个节点和下一个节点的异或例如，上一个节点的地址为100，下一个节点的地址为500。
所以，在ptrdiff地址是400现在怎么可能移动到下一个或上一个节点（就像我们在双链接列表中所做的那样），只需知道它们的地址的异或？
我是不是漏了一步？

最佳答案

第一个节点没有上一个节点，最后一个节点没有下一个节点因此，将第一个节点之前的节点地址和最后一个节点之后的节点地址想象为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;
    }
}

关于c - “高效内存的双向链表”如何工作？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25820051/