面试官：如何只使用一个指针域实现双向链表

这是来自某学习群的群友提供的，一道 便利蜂 的实习面试题，恰好被看到了（不是

问题是：只使用一个指针如何实现双向链表，乍一想好像不可能，我当时的大致思路是这样的：原来直接使用 ->right 或者 ->left 就能访问到左右节点，现在只有一个指针，就要修改指针的含义，不能直接存储下一个节点的地址了，大概率是要根据某些条件算出下一个地址。

事实呢？为了了解具体做法，我去翻了维基百科关于这部分的 详细解释 ，并本地实现了一遍完整代码，记录在这里。

实现原理

这种链表被称为 异或链表（XOR Linked List），能够达到只使用一个指针域实现双向链表的效果，从而降低空间复杂度。当然它也不是没有缺点，如果只有一个节点，无法向两个方向遍历，必须有连续的两个节点地址。

回到之前说的问题，问题的关键就是如何只使用一个指针实现双向访问的效果，再来看链表名，异或链表。

任何一个节点的指针域的值为 它的前一个节点和下一个节点的地址异或。

假如现在有 3 个节点分别为 A,B 和 C，地址分别为 0x1,0x2,0x3，那么，

A.next = null^0x2
B.next = 0x1^0x3
C.next = 0x2^null

                         XOR linked List



   +--- -----+ next=0x1    +---------+ next=0x1^0x3   +---------+
   | *A=0x1  +---------    | *B=0x2  +------------    | *C=0x3  |
   +---------+             +---------+                +------+--+
                                                             |
       |                                                     | next=0x2
       |                                                     |
       | next=0x1                                            |
       |
+------+--+                                               +---------+
|  null   |                                               |  null   |
+---------+                                               +---------+

这个图之所以没有画出箭头是因为这里并不是直接指向下一个节点的地址，而是需要和前一个节点异或计算才能得到下一个节点的地址。

由于遍历的时候需要知道前一个节点的地址，所以遍历方向也就确定了，所以需要用到当前节点的指针域参与异或运算。并不需要后一个节点的指针域。可能有一点绕，一直用前一个后一个的说法，不过结合一下上面这个图你就明白了。

具体实现

需要实现链表的基本操作，构造/访问/删除/插入，这里的插入操作是在第 N 个节点之前，例如上图，如果 N = 2，那么就是在 A 与 B 之间插入，使新节点成为第二个节点。删除操作也是找到第 N 个节点。

建表

遍历

插入

删除

总结