以下链接解释了它.
据说该实现通过存储前一个和下一个地址(比如nxp)的XOR而不是分别存储两个(前一个和下一个地址)来工作.但是,进一步沿着实现被称为通过xor-ing先前的地址工作和nxp,以获得下一个地址.
但这实际上是否使用 与前一个和下一个指针相同的空间？
Pat*_*shu 37
在双向链表中,每个节点存储两个指针:prev和next.在XOR链表中,每个节点存储一个"指针",即prev和Xor的XOR(或者如果其中一个不存在,则只存在另一个(与0相同的XOR)).您仍然可以在两个方向上遍历XOR链接列表的原因依赖于XOR的属性和双链表中固有的信息冗余.
想象一下,你的XOR链表中有三个节点.
A是头部,并且有一个未经混淆的指向B的指针(B XOR 0,仅下一个)
B是中间元素,并且具有指向A和C的指针的XOR.
C是尾部,是B的未混淆指针(0 XOR B,仅限prev)
当我在这个列表上进行迭代时,我从A开始.当我前往B时,我注意到A在记忆中的位置.当我想要前往C时,我将A指向B的指针,给我指向C的指针.然后我注意到B在记忆中的位置并前往C.
这是有效的,因为如果应用两次,XOR具有撤消自身的属性:C XOR A XOR A == C.考虑它的另一种方式是,双向链表不存储单链表所没有的额外信息(因为它只是存储所有以前的指针都是内存中其他位置的下一个指针的副本),因此通过利用这种冗余,我们可以拥有双向链表属性,只需要所需数量的链接.但是,这只有在我们从开始或结束开始我们的XOR链表遍历时才有效 - 就像我们只是跳到中间的随机节点一样,我们没有开始遍历所需的信息.
虽然XOR链表具有内存使用量较小的优点,但它有一些缺点 - 它会混淆编译器,调试和静态分析工具,因为除了代码之外,指针无法正确识别两个指针的XOR.它还会减慢指针访问速度,必须先执行XOR操作才能恢复真正的指针.它也不能在托管代码中使用 - 垃圾收集器不会识别XOR混淆的指针.
让我们考虑以下 XOR 列表
A->B->C->D
假设您在下面以这种格式创建了节点
钥匙|链接|
A|0^addr(B)| -> B|addr(A)^addr(C)| -> C|addr(B)^addr(D)| -> D|addr(C)^0|
案例#1：[前向遍历]现在假设你在 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)
案例#2：[向后遍历]现在假设你在 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来存储从 head 开始的相对当前、上一个和下一个节点的地址。然后在每次迭代中，这些指针需要移动到前面的一个位置。
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;
}
双链表需要为N个节点存储2*N个指针,加上至少一个附加指针(头部,或者可能是头部和尾部).
XOR链表需要为N个节点存储的N个指针,以及至少两个附加指针(头部和最后访问的节点,或者可能是头部和尾部以及最后访问的节点).遍历时,您存储一个节点(最后访问的节点),但是当您转到下一个节点时,您使用现在的上一个节点的地址重写该节点.