异或链表

示例练习>>>

异或链表（XOR linked list）可以在降低空间复杂度的情况下达到和双向链表一样的目的，使得在任何一个节点都能方便地访问它的前驱节点和后继节点。双向链表一般有三个变量，一个是指向前一个节点，一定是指向后一个节点，一个是存放数据。而异或链表只需要两个变量即可，一个存放前一个节点地址与后一个节点地址的异或值，一个存放数据，如下图所示。

如果现在处于节点 B ，想求节点 C 的地址，只需要用 A 的地址 addr(A) 与 B 中存储的值 addr(A)^addr(C) 进行异或运算即可，在位运算介绍中我们讲过异或运算具有交换律，所以得到下面的公式：

addr(A) ^ link(B)
= addr(A) ^ (addr(A) ^ addr(C))
= 0 ^ addr(C)
= addr(C)

如果现在处于节点 B ，想求节点 A 的地址，只需要用 C 的地址 addr(C) 与 B 中存储的值 addr(A)^addr(C) 进行异或运算即可。

addr(C) ^ link(B)
= addr(C) ^ (addr(A) ^ addr(C))
= addr(A) ^ addr(C) ^ addr(C)
= addr(A)

异或链表有很大的局限性，因为是地址异或，在 C 以及 C++ 中可以直接访问变量的地址，所以很容易实现。但在 Java 和其他的一些语言中，由于不能直接访问变量的地址，所以一般情况下都使用不到，对异或链表只需要理解即可。

参考：XOR Linked List

相关链接