XOR双向链表

• 云风的 BLOG: XOR 链表
• Wikipedia
• 自己的实现代码 这里

这个东西的好处有：

• 节省指针空间。如果我们不是直接使用指针(uint64)，而是使用id(uint32)代替内存指针的话，普通的双向链表空间也一样。
• 操作代码是对称的。比如push/pop/walk从两个方向操作其实代码完全一样，只是起始点以及终止点有点不同。

这个东西的限制有：

• 操作上必须涉及指针，所以像Python/Java这样的语言就没有办法用了。
• 在某个位置插入和删除的话，时间复杂度是O(n)，传统双向链表时间复杂度是O(1).