今天看到云风的一篇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

最多留言日志