XOR 链表
前两天阿楠同学想用链表实现一个消息队列，虽说是链表，但是没有从中间删除节点或添加节点的需求。只需要先压入的消息先处理。为了完成这个需求，最后实现了一个双向链表。
当然这个东西是用 Lua 写的，做一个双向链表也不算复杂。采用单向链表也可以做到，只需要多记录一个尾节点。不过今天想说的是，如果这个玩意在 C 里实现的话，其实只需要用一个指针的空间就可以搞定一个双向队列，可以从任意一头进出数据，可以以两个方向遍历，而实现需要的代码量却和单向链表类似。因为算法非常有趣，在 C 语言之外很少见到，知道并使用过的人也就不太多了。这就是所谓的 XOR Linked List 。
我们不需要在链表节点上保存前序和后继两个指针，而改而保存这两个指针的 XOR 值。把两个指针强制转换为 uintptr_t ，做位运算 ^ 即可。
这个数据结构可以工作起来，依赖位运算的一个特性： A^(A^B) == B ，我们知道前序地址或后继地址中的任意一个，都可以用这个值推算出另一个来。这样的链表，从前向后与从后向前遍历的算法是一样的，区别只在于初始参数。
每个链表对象，我们保存链表的首节点和尾节点的指针。由于首节点没有前序节点，它的链接信息只需要记录后续节点（ XOR NULL 不会改变它）即可。当链表内只有一个节点时，链接信息记录的就是它自己的地址了。
对于队列，我们只需要在新节点加入时，替换掉首节点，链接信息设为原来的头节点，并把原头节点的链接数据域 xor 上新加入的节点地址即可。
而出队列的时候，只需要用尾节点的链接域替换掉它并用 xor 更新新的尾节点链接域的数据即可。
XOR 链表的实现很巧妙有趣，但并不意味着实现很复杂。它比传统的双向链表实现起来要简单的多（甚至更容易实现为无锁的数据结构，传统的单向链表很容易实现为无锁数据结构，而双向链表就麻烦的多 ）。当然，局限性也很明显。
它很难在 C/C++ 之外的其它语言中实现，而且链接信息很隐讳，会导致调试起来更困难一些。
我们几乎只能在遍历链表的过程中去插入和删除单个节点（当然很多情况下，我们也只需要在这个场合做这些事情），插入一个节点需要同时知道两个节点，我们才能把新节点插入其间，删除节点也必须有它前或后的节点信息才行。
但这个数据结构在某些场景毕竟是有用的，比起用 xor 交换两个变量来说，XOR 交换算法 才真的像道智力题。
Comments
10年了
Posted by: zhang | (18) February 18, 2024 01:19 PM
对于你的文件我有不同的看法：1你来自北京《可是为什么要到南京发展呢？还有你的文件版本实在是不堪路眼，太多的崽子要你的圣体。也许我不认识你你也不认识我的名字，但是我对于你的论文实在太精辟了
Posted by: 董世学 | (17) June 11, 2013 03:27 PM
对于你的文件我有不同的看法：1你来自北京《可是为什么要到南京发展呢？还有你的文件版本实在是不堪路眼，太多的崽子要你的圣体。也许我不认识你你也不认识我的名字，但是我对于你的论文实在太精辟了
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
x86下还好吧，MemoryBarrier()是个编译器屏障，指令别优化错了就行，指令是对的，cpu执行的时候访存就不会乱序。
Posted by: Jacky007 | (13) May 17, 2013 07:30 PM
@浅浅水
在目前CPU都普遍乱序优化的情况下，我倒是很想知道你不用lock如何保证正确性？不是看理论就好的好么？早期的论文都是基于顺序执行和纯正常思考情况下设计的。现在绝大部分CPU都有乱序执行功能。你不用lock如何保证互斥性？C语言还要一个关键字volatile来保证变量访问不被优化-就这也无法能在多核而且都具有乱序执行下保证安全。纯学术派在一定程度上总是以为自己很权威，但是在现实面前往往非常悲剧。我只能说他们真的只适合做理论研究。关于这个乱序执行的问题文章中几乎没什么针对性的说明。
Posted by: swz | (12) May 13, 2013 08:50 AM
@浅浅水
你的skynet cpp版打算开源吗？支持window平台吗？
Posted by: shen | (11) May 11, 2013 12:18 AM
这个设计想法是不错。
Posted by: 域名优惠 | (10) May 10, 2013 09:54 PM
linux 内核的struct list_head？
Posted by: Anonymous | (9) May 9, 2013 04:06 PM
但并意味着实现很复杂。
C/C++ 只外
Posted by: shuax | (8) May 7, 2013 12:47 PM
@irachex i==j时应该不会出现仍是原值不会变成0
Posted by: joysword | (7) May 6, 2013 12:25 PM
10分钟前刚在wikipedia看到这个说法，这里就有文章可以看了，赞命运
Posted by: joysword | (6) May 6, 2013 12:09 PM
满足群性质的集合和二元运算都可以像xor那样交换http://chris-taylor.github.io/blog/2013/02/25/xor-trick/
Posted by: n00b | (5) May 5, 2013 09:40 PM
@浅浅水
谢谢你给的论文， 我错了，我把链接给到正文里去了。
Posted by: Cloud | (4) May 5, 2013 08:41 PM
XOR swap有个坑：当应用于一个数组时(比如qsort)，swap a[i]和a[j]，当i == j时就会都变成0了
Posted by: irachex | (3) May 5, 2013 08:40 PM
这跟保存列表的倒数第二个指针有啥区别。。。
Posted by: wheat | (2) May 5, 2013 08:26 PM
好精巧的设计，回头我去实现个无锁的版本看看（估计是很久之后），因为最近忙着复刻你的skynet cpp版（设计已经有了巨大的变动。不过是受skynet的启发）。。~
bty：双向链表也是可以做到无锁，采用环形链表，居论文讲性能还要略高，http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf
Posted by: 浅浅水 | (1) May 5, 2013 08:25 PM