"内存高效的双向链表"如何运作？

Question

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

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

在ptrdiff,将完成上一个和下一个节点的xoring.例如,前一个节点的地址为100,下一个节点的地址为500.

所以,在ptrdiff地址将是400.现在,如何通过了解其地址的xoring,如何移动到下一个或上一个节点(就像我们在双向链接列表中那样)？

我错过了这里的任何一步吗？

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