30

以下链接对此进行了说明。
据说该实现通过存储前一个地址和下一个地址（例如 nxp）的 XOR 来工作，而不是分别存储（前一个和下一个地址）。但是，据说进一步的实现是通过对前一个地址进行异或运算来工作的和nxp，为了得到下一个地址。


但这实际上不是使用 与拥有前一个和下一个指针相同的空间吗？

4

5 回答 5

49

在双向链表中，每个节点存储两个指针：prev 和 next。在 XOR 链表中，每个节点存储一个“指针”，即 prev 和 next 的 XOR（或者如果其中一个不存在，则只是另一个（与 0 的 XORing 相同））。您仍然可以双向遍历 XOR 链表的原因取决于 XOR 的属性和双链表中固有的信息冗余。

假设您的 XOR 链表中有三个节点。

A 是头部，并且有一个未混淆的指向 B 的指针（B XOR 0，仅下一个）

B 是中间元素，具有指向 A 和指向 C 的指针的异或。

C 是尾部，并且是指向 B 的未混淆指针（0 XOR B，仅 prev）

当我遍历这个列表时，我从 A 开始。当我前往 B 时，我记下 A 在内存中的位置。当我希望前往 C 时，我将 B 的指针与 A 异或，授予我指向 C 的指针。然后我记下B在记忆中的位置并前往C。

这是因为 XOR 具有在应用两次时自行撤消的属性：C XOR A XOR A == C。另一种思考方式是，双向链表不存储单链表不存储的额外信息（因为它只是存储所有先前的指针都作为内存中其他地方的下一个指针的副本），因此通过利用这种冗余，我们可以拥有双链表属性，其中只有所需的链接数。但是，这仅在我们从头或尾开始 XOR 链表遍历时才有效——就好像我们只是跳到中间的一个随机节点，我们没有开始遍历所需的信息。

虽然 XOR 链表具有内存使用量较小的优点，但它也有缺点——它将混淆编译器、调试和静态分析工具，因为除了代码之外的任何指针都无法正确识别两个指针的 XOR。它还减慢了指针访问速度，必须首先执行 XOR 操作才能恢复真正的指针。它也不能在托管代码中使用——异或混淆指针不会被垃圾收集器识别。

于 2013-04-22T03:35:45.887 回答
8

让我们考虑以下 XOR 列表

A->B->C->D

假设您在下面以这种格式创建了节点

关键字|链接|

A|0^addr(B)| ->  B|addr(A)^addr(C)|  ->  C|addr(B)^addr(D)| -> D|addr(C)^0|

CASE #1:[Forward Traversal]现在假设你在 B (current_node=>B) 想要访问 C ，所以你需要 C 的地址。你将如何获得？

Addressof(Next_node) = addressof(Prev_node) ^ Current_node(Link)

addr(A)^ ( addr(A)^ addr(C) )
=>(addr(A) ^ addr(A)) ^ addr(C) 
=> 0 ^ addr(C)
=>addr(C)

CASE #2: [Backward traversal]现在假设你在 C (current_node=> C) 想要访问 B ，所以你需要 B 的地址。你将如何获得？

Addressof(Prev_node) = addressof(Next_node) ^ Current_node(Link)

addr(D) ^ ((addr(B) ^ addr(D)) 
=> (addr(D)^ addr(D)) ^ addr(B)
=> 0^addr(B)
=> addr(B)

遍历： 要遍历整个列表，您将需要 3 个指针 prevPtr 、 currPtr 、 nextPtr来存储从头开始的相对当前、上一个和下一个节点的地址。然后在每次迭代中，这些指针需要移动到前面的一个位置。 

struct Node *currPtr = head;
struct Node *prevPtr = NULL;
struct Node *nextPtr;

printf ("Following are the nodes of Linked List: \n");

while (currPtr != NULL)
{
    // print current node
    printf ("%d ", currPtr->key);

    // Save the address of next node
    nextPtr = XOR (prevPtr, currPtr->link);

    //move prevPtr and currPtr one position for next iteration

    prevPtr = currPtr;
    currPtr = nextPtr;
}
于 2018-07-17T14:12:13.093 回答
5

但这实际上不是使用与拥有前一个和下一个指针相同的空间吗？

不——它使用了大约一半的空间，因为“prev”和“next”的异或结果的大小等于两者中较大者的大小。

于 2013-04-22T03:39:13.023 回答
5

XOR 有一个非常特殊的性质，即在给定a XOR b = c的情况下，计算第三个变量只需要两个（任意两个）变量，但有一些限制。请参阅XOR 交换算法以了解其工作原理。

在这种情况下，前一个（或下一个）指针仍然必须被携带，但只能通过遍历计算而不是作为单独的成员。

于 2013-04-22T03:40:31.610 回答
4

双链表需要为 N 个节点存储 2*N 个指针，加上至少一个额外的指针（头，或者可能是头和尾）。

XOR 链表需要为 N 个节点存储 N 个指针，加上至少两个额外的指针（头和最后访问的节点，或者可能是头和尾和最后访问的节点）。遍历时，您存储一个节点（最后访问的节点），但是当您转到下一个节点时，您使用现在的前一个节点的地址重写它。

于 2013-04-22T03:37:47.047 回答