XOR List - A Memory Efficient Doubly Linked List

普通的双向链表需要两个指针分别保存 next 和 prev 。利用 XOR 的特性，可以用一个指针实现双向链表。

考虑 XOR 特性：

\begin{equation} A \oplus B = B \oplus A \end{equation}

\(If\)

\begin{equation} C = A \oplus B \end{equation}

\(Then\)

\begin{equation} B = C \oplus A\\ A = C \oplus B \end{equation}

假设链表节点 struct node { struct node *link; } 和链表头 =struct head {}; ，初始时有:

插入节点 x1 ：

\begin{equation} next = prev \oplus cur->link;\\ prev = next \oplus cur->link; \end{equation}