XOR linked list--- 异或链表

异或链表的结构

这是一个数据结构。利用计算机的的位异或操作(⊕)，来降低双向链表的存储需求。

...  A       B         C         D         E  ...

          –>  next –>  next  –>  next  –>

          <–  prev <–  prev  <–  prev  <–

双向链表如上面所示，每个节点有两个指针，分别指向该节点的前驱和后继。

而XOR链表如下面所示：

 ...  A        B         C         D         E  ...

         <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->

多余的一个指针中存放的地址的异或。 比如B中就存放了A⊕C的值。

这样从头开始便利时，我们需要知道开始的两个节点（而不像普通链表只需要一个）。

这样比如知道了节点A和节点B 我们就可以用节点A的地址和B中的A⊕C 结合运算，得到A⊕A⊕C 得到C。 这是正向遍历

反向遍历时类似，比如知道了节点E和D，就可以利用E的地址和D中的C⊕E 运算，得到C⊕E⊕E 得到C

但是，该结构用以做研究学习使用，实际中我们并不推荐使用，主要由于以下原因：

随着资源越来越便宜，内存越来越大，除了在一些嵌入式系统中，内存将不再是一个非常重要的因素。

加法链表：放地址的和

 ...  A        B         C         D         E  ...

         <–>  A+C  <->  B+D  <->  C+E  <->

减法链表：放地址的差

...  A        B         C         D         E  ...

         <–>  C-A  <->  D-B  <->  E-C  <->

不同是正向和反向需要做不同的运算。