聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

XOR 链表

2013-05-06 22:01 浏览: 1439004 次 我要评论(0 条) 字号:

前两天阿楠同学想用链表实现一个消息队列,虽说是链表,但是没有从中间删除节点或添加节点的需求。只需要先压入的消息先处理。为了完成这个需求,最后实现了一个双向链表。

当然这个东西是用 Lua 写的,做一个双向链表也不算复杂。采用单向链表也可以做到,只需要多记录一个尾节点。不过今天想说的是,如果这个玩意在 C 里实现的话,其实只需要用一个指针的空间就可以搞定一个双向队列,可以从任意一头进出数据,可以以两个方向遍历,而实现需要的代码量却和单向链表类似。因为算法非常有趣,在 C 语言之外很少见到,知道并使用过的人也就不太多了。这就是所谓的 XOR Linked List

我们不需要在链表节点上保存前序和后继两个指针,而改而保存这两个指针的 XOR 值。把两个指针强制转换为 uintptr_t ,做位运算 ^ 即可。

这个数据结构可以工作起来,依赖位运算的一个特性: A^(A^B) == B ,我们知道前序地址或后继地址中的任意一个,都可以用这个值推算出另一个来。这样的链表,从前向后与从后向前遍历的算法是一样的,区别只在于出使参数。

每个链表对象,我们保存链表的首节点和尾节点的指针。由于首节点没有前序节点,它的链接信息只需要记录后续节点( XOR NULL 不会改变它)即可。当链表内只有一个节点时,链接信息记录的就是它自己的地址了。

对于队列,我们只需要在新节点加入时,替换掉首节点,链接信息设为原来的头节点,并把原头节点的链接数据域 xor 上新加入的节点地址即可。

而出队列的时候,只需要用尾节点的链接域替换掉它并用 xor 更新新的尾节点链接域的数据即可。


XOR 链表的实现很巧妙有趣,但并意味着实现很复杂。它比传统的双向链表实现起来要简单的多(甚至更容易实现为无锁的数据结构,传统的单向链表很容易实现为无锁数据结构,而双向链表就麻烦的多 )。当然,局限性也很明显。

它很难在 C/C++ 只外的其它语言中实现,而且链接信息很隐讳,会导致调试起来更困难一些。

我们几乎只能在遍历链表的过程中去插入和删除单个节点(当然很多情况下,我们也只需要在这个场合做这些事情),插入一个节点需要同时知道两个节点,我们才能把新节点插入其间,删除节点也必须有它前或后的节点信息才行。

但这个数据结构在某些场景毕竟是有用的,比起用 xor 交换两个变量来说,XOR 交换算法 才真的像道智力题。



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复