究竟如何一个XOR链表的工作？ [英] How exactly does a XOR Linked list work?

问题描述

下面的链接解释它。
的实施被认为由单独存储的previous和下一个地址（比如NXP）异或，而不是存储两个（previous和下一个地址）的工作。然而，随着进一步的实施被认为由异或的previous地址和恩智浦合作，以获得的下一个地址的。

The following link explains it.
The implementation is said to work by storing the XOR of the previous and next address(say nxp), instead of storing both(previous and next address) separately.However, further along the implementation is said to work by xor-ing the previous address and nxp, in order to get the next address.

但实际使用的同样的空间这个心不是作为有previous和明年的指针？

But isnt this practically using the same space as having previous and next pointers?

推荐答案

在一个双向链表，你存储每个节点两个指针：$ P $光伏和明年。在一个XOR链表，则存储每个节点有一个'指针'，这是$ P $光伏和下一个异或（或者如果其中之一是不存在，只是另一个（相同异或0））。之所以仍然可以遍历在两个方向上的XOR链表依赖异或的固有的双链表的属性和信息的冗余度。

In a doubly linked list, you store two pointers per node: prev and next. In an XOR linked list, you store one 'pointer' per node, which is the XOR of prev and next (or if one of them is absent, just the other (the same as XORing with 0)). The reason why you can still traverse an XOR linked list in both directions relies on the properties of XOR and the redundancy of information inherent in a double linked list.

想象一下，你在你的XOR链表三个节点。

Imagine you have three nodes in your XOR linked list.

一个是头，并有一个是非模糊的指针为B（b XOR 0，仅次于）

A is the head, and has an unobfuscated pointer to B (B XOR 0, next only)

B是中间元件，具有指针的异或以A和至C

B is the middle element, and has the XOR of pointers to A and to C.

C是尾巴，一个是非模糊的指向B（0 XOR B，$ P $光伏专用）

C is the tail, and an unobfuscated pointer to B (0 XOR B, prev only)

当我遍历这个名单，我开始在答：我注意到一个在内存中的位置，因为我旅行到B.当我要出差到C，我XOR B的指针与A，给予我的指针C.然后我注意到B的位置，在内存中，前往℃。

When I am iterating over this list, I start at A. I note A's position in memory as I travel to B. When I wish to travel to C, I XOR B's pointer with A, granting me the pointer to C. I then note B's position in memory and travel to C.

这工作，因为XOR有撤消自己的财产，如果应用两次：C XOR A XOR A == C.另一种方式去思考它，双向链表存储单链表没有任何额外的信息（因为它只是存储所有的previous指针作为下一个指针其他在内存的某个地方）的副本，所以通过利用这种冗余，我们可以有双向链表性能，只有尽可能多环节的需要。 但是，如果这只是工作，我们开始我们的XOR链表遍历从开始或结束 - 好像我们刚刚跳进中间一个随机的节点上，我们并没有开始遍历所需的信息。

This works because XOR has the property of undoing itself if applied twice: C XOR A XOR A == C. Another way to think about it is, the doubly linked list stores no extra information a singly linked list does not (since it's just storing all the previous pointers as copies of next pointers somewhere else in memory), so by exploiting this redundancy we can have doubly linked list properties with only as many links as are needed. However, This only works if we start our XOR linked list traversal from the start or end — as if we just jump into a random node in the middle, we do not have the information necessary to start traversing.

而异或链接列表中有更小的内存使用情况的优势，它的缺点 - 它会混淆编译器，调试和静态分析工具，你的两个指针异或不会被指向正确认识到任何东西，除了你的$ C $℃。它也减慢指针访问都要做XOR运算将首先恢复真正的指针。它也不能用于管理code - XOR模糊处理的指针将不会被垃圾收集器识别

While an XOR linked list has the advantage of smaller memory usage, it has disadvantages — it will confuse the compiler, debugging and static analysis tools as your XOR of two pointers will not be correctly recognized by a pointer by anything except your code. It also slows down pointer access to have to do the XOR operation to recover the true pointer first. It also can't be used in managed code — XOR obfuscated pointers won't be recognized by the garbage collector.

这篇关于究竟如何一个XOR链表的工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！