异或链接列表

跳转至导航跳转至搜索异或链接列表是计算机编程中使用的一种数据结构。它利用按位XOR运算来减少双向链表的存储要求。

普通的双向链接列表在每个列表节点中存储上一个和下一个列表项的地址，需要两个地址字段：

... A B C D E ... –＆gt;下一个–＆gt;下一个–＆gt;下一个–＆gt; ＆lt; –上一个＆lt; –上一个＆lt; –上一个＆lt; –

一个XOR链表通过在一个字段中存储前一个地址和下一个地址的按位XOR（此处用denoted表示）将相同的信息压缩到一个地址字段中：

... A B C D E ...-- A⊕C- B⊕D- C⊕E-

当从左向右遍历列表时：假设光标在C处，则前一项B可以与链接字段（B⊕D）中的值进行XOR运算。然后将获得D的地址，并且可以继续遍历列表。相同的方向适用于另一个方向。

即addr（D）=链接（C）⊕addr（B）其中，link（C）= addr（B）⊕addr（D），所以addr（D）= addr（B）⊕addr（D）⊕addr（B）由于X = X = 0 =>，所以addr（D）= addr（B）→addr（B）→addr（D）。由于X = 0 = x =>，所以addr（D）= 0 0 addr（D）。 addr（D）= addr（D）XOR操作取消等式中出现两次的addr（B），剩下的就是addr（D）。

要从某个点开始沿任一方向遍历列表，需要两个连续项的地址。如果两个连续项的地址相反，则列表遍历将以相反的方向进行。 [1]

R2寄存器始终包含当前项C的地址与先前项P：C⊕P的地址的异或。记录中的链接字段包含左右后继地址的XOR，例如L⊕R。 R2（C⊕P）与当前链接字段（L⊕R）的XOR得出C⊕P⊕L⊕R。

如果前任是L，则P（= L）和L抵消，剩下C⊕R。

如果前任是R，则P（= R）和R抵消，剩下C⊕L。

在每种情况下，结果都是当前地址与下一个地址的XOR。将其与R1中的当前地址进行XOR运算将保留下一个地址。 R2保留了（现在）当前地址和先前地址的必要XOR对。

两个XOR操作足以完成从一项到下一项的遍历，在两种情况下，相同的指令就足够了。考虑一个列表，其中包含项{…BCD…}，并且R1和R2是分别包含当前（例如C）列表项的地址的寄存器和包含当前地址与先前地址（例如C）的XOR的工作寄存器。 ⊕D）。投射为System / 360指令：

X R2，链接R2 ＜-C⊕D⊕B⊕D（即B⊕C，＆＃34；链接＆＃34；是当前记录中的链接字段，包含B⊕D）。 -C⊕B⊕C（即B，下一个记录）

通过想象一个位于{0 A B C…}中与端点相邻的地址零处的列表项来表示列表的末尾。 A处的链接字段为0⊕B。在两次异或运算之后，需要按上述顺序添加一条指令来检测零结果，从而开发出当前项目的地址，

通过使链接指针为零，可以使列表端点具有反射性。零指针是一面镜子。 （左右邻居地址的XOR相同，为零。）

减少内存使用量的代价是代码复杂度的增加，从而使维护更加昂贵；

大多数垃圾回收方案不适用于不包含文字指针的数据结构。

并非所有的语言都支持指针和整数之间的类型转换，在某些上下文中未定义对指针的XOR。

在遍历列表时，需要使用先前访问的节点的地址来计算下一个节点的地址，并且如果不遍历该列表（例如，如果指向列表项的指针），则指针将不可读包含在另一个数据结构中；

XOR链表没有提供双链表的一些重要优点，例如仅知道地址就可以从列表中删除节点的能力，或者仅知道地址就可以在现有节点之前或之后插入新节点的能力。现有节点的

计算机系统具有越来越便宜和充足的内存，因此存储开销通常不是专用嵌入式系统之外的首要问题。如果仍然需要减少链接列表的开销，则展开将提供一种更实用的方法（以及其他优势，例如提高缓存性能和加快随机访问的速度）。

XOR链表的基本原理可以应用于任何可逆的二进制操作。通过加法或减法替换XOR得出的公式略有不同，但基本相同：

... A B C D E ...-- A + C- B + D- C + E-

除了零链接字段不是＆＃34; mirror＆＃34;之外，这种列表具有与XOR链接列表完全相同的属性。通过从当前节点的链接字段中减去前一个节点的地址，可以得出列表中下一个节点的地址。

... A B C D E ...-- C-A- D-B- E-C-

这种列表与标准＆＃34;传统＆＃34;不同。 XOR链表的不同之处在于向前遍历该列表所需的指令序列与反向遍历该列表所需的序列不同。通过将链接字段添加到上一个节点的地址，可以得出下一个节点的地址（向前）。通过从下一个节点的地址中减去链接字段，可以得出前一个节点的地址。

减法链接列表的特殊之处还在于，可以在不对指针值进行任何修补的情况下将整个列表重定位到内存中，因为向列表中的每个地址添加恒定偏移量将不需要对链接字段中存储的值进行任何更改。 （另请参见序列化。）与XOR链表和传统链表相比，这是一个优势。

^＆＃34; XOR链接列表-内存有效的双重链接列表| 设置1-GeeksforGeeks＆＃34;。 极客。 2011-05-23。