XOR 链表
前两天阿楠同学想用链表实现一个消息队列，虽说是链表，但是没有从中间删除节点或添加节点的需求。只需要先压入的消息先处理。为了完成这个需求，最后实现了一个双向链表。
当然这个东西是用 Lua 写的，做一个双向链表也不算复杂。采用单向链表也可以做到，只需要多记录一个尾节点。不过今天想说的是，如果这个玩意在 C 里实现的话，其实只需要用一个指针的空间就可以搞定一个双向队列，可以从任意一头进出数据，可以以两个方向遍历，而实现需要的代码量却和单向链表类似。因为算法非常有趣，在 C 语言之外很少见到，知道并使用过的人也就不太多了。这就是所谓的 XOR Linked List 。
我们不需要在链表节点上保存前序和后继两个指针，而改而保存这两个指针的 XOR 值。把两个指针强制转换为 uintptr_t ，做位运算 ^ 即可。
这个数据结构可以工作起来，依赖位运算的一个特性： A^(A^B) == B ，我们知道前序地址或后继地址中的任意一个，都可以用这个值推算出另一个来。这样的链表，从前向后与从后向前遍历的算法是一样的，区别只在于初始参数。
每个链表对象，我们保存链表的首节点和尾节点的指针。由于首节点没有前序节点，它的链接信息只需要记录后续节点（ XOR NULL 不会改变它）即可。当链表内只有一个节点时，链接信息记录的就是它自己的地址了。
对于队列，我们只需要在新节点加入时，替换掉首节点，链接信息设为原来的头节点，并把原头节点的链接数据域 xor 上新加入的节点地址即可。
而出队列的时候，只需要用尾节点的链接域替换掉它并用 xor 更新新的尾节点链接域的数据即可。
XOR 链表的实现很巧妙有趣，但并不意味着实现很复杂。它比传统的双向链表实现起来要简单的多（甚至更容易实现为无锁的数据结构，传统的单向链表很容易实现为无锁数据结构，而双向链表就麻烦的多 ）。当然，局限性也很明显。
它很难在 C/C++ 之外的其它语言中实现，而且链接信息很隐讳，会导致调试起来更困难一些。
我们几乎只能在遍历链表的过程中去插入和删除单个节点（当然很多情况下，我们也只需要在这个场合做这些事情），插入一个节点需要同时知道两个节点，我们才能把新节点插入其间，删除节点也必须有它前或后的节点信息才行。
但这个数据结构在某些场景毕竟是有用的，比起用 xor 交换两个变量来说，XOR 交换算法 才真的像道智力题。
Comments
Posted by: zhang | (18) February 18, 2024 01:19 PM
Posted by: 董世学 | (17) June 11, 2013 03:27 PM
Posted by: 董世学 | (16) June 11, 2013 03:27 PM
Posted by: chm | (15) May 27, 2013 10:35 AM
Posted by: 邓安良 | (14) May 20, 2013 05:20 PM
Posted by: Jacky007 | (13) May 17, 2013 07:30 PM
Posted by: swz | (12) May 13, 2013 08:50 AM
Posted by: shen | (11) May 11, 2013 12:18 AM
Posted by: 域名优惠 | (10) May 10, 2013 09:54 PM
Posted by: Anonymous | (9) May 9, 2013 04:06 PM
Posted by: shuax | (8) May 7, 2013 12:47 PM
Posted by: joysword | (7) May 6, 2013 12:25 PM
Posted by: joysword | (6) May 6, 2013 12:09 PM
Posted by: n00b | (5) May 5, 2013 09:40 PM
Posted by: Cloud | (4) May 5, 2013 08:41 PM
Posted by: irachex | (3) May 5, 2013 08:40 PM
Posted by: wheat | (2) May 5, 2013 08:26 PM
Posted by: 浅浅水 | (1) May 5, 2013 08:25 PM