今天看到云风的一篇blog,提到了XOR链表,第一次见到,算法非常有意思,记录下。

大概思想:正常实现双向链表,对于每个node都会保存两个指针pre和next, 但是对于XOR linked list来说,可以只保存一个指针就可以实现,

保存的就是pre^next的异或值。

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

对于每个链表对象,我们只需要保存链表的head和tail, 就可实现从头和从尾遍历链表。

这里是Wikipedia对XOR linked list的介绍:http://en.wikipedia.org/wiki/XOR_linked_list

另外还有一篇论文对lock-free FIFO 的介绍:http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf

来自yaronspace.cn  本文链接:http://yaronspace.cn/blog/archives/1577