我知道这是我的第二个答案, 但我认为我在这里提供的解释可能会更好一些，比上一个答案更好。但请注意，即使那个答案也是正确的。
内存高效链表经常被称为XOR链表，因为它完全依赖于XOR逻辑门及其属性。
是的，它不同。虽然它基本上执行了与双向链表几乎相同的工作，但它确实是不同的。
双向链表存储两个指针，分别指向前一个节点和后一个节点。基本上，如果要返回到上一个节点，可以通过back指针指向的地址进行；如果要向前移动，则可以通过next指针指向的地址进行。如下图所示：
内存高效链表，或者说是 XOR 链表，只有一个指针而不是两个。它存储先前地址（addr(prev)) XOR 下一个地址 (addr(next))。当您想要移动到下一个节点时，需要进行某些计算，以找到下一个节点的地址。这对于移动到上一个节点也是一样的。如下图所示：
从名称中可以看出，XOR链表高度依赖于逻辑门XOR (^) 及其属性。
其属性为：
|-------------|------------|------------|
| Name | Formula | Result |
|-------------|------------|------------|
| Commutative | A ^ B | B ^ A |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1) | A ^ 0 | A |
|-------------|------------|------------|
| None (2) | A ^ A | 0 |
|-------------|------------|------------|
| None (3) | (A ^ B) ^ A| B |
|-------------|------------|------------|
现在，让我们搁置这个问题，看看每个节点存储了什么：
第一个节点，或者说头节点，存储0^addr(next)，因为没有前一个节点或地址。它看起来像这样：
然后第二个节点存储addr(prev)^addr(next)。它看起来像这样:
上面的图片显示了B节点，也就是第二个节点。A和C是第三个和第一个节点的地址。除了头和尾节点以外的所有节点都是类似于上面的节点。
列表的尾巴没有任何下一个节点，因此它存储addr(prev)^0。它看起来像这样：
在了解如何移动之前，让我们再次看一下异或链接列表的表示：
当您看到
它很清楚地表示有一个链接字段，可以用它向前或向后移动。
还要注意，在使用异或链接列表时，您需要一个临时变量（不在节点中），它存储之前所在节点的地址。当您移动到下一个节点时，丢弃旧值，并存储之前所在节点的地址。
从头移动到下一个节点
假设现在您位于第一个节点A。现在您想要移动到节点B。这是这样做的公式：
Address of Next Node = Address of Previous Node ^ pointer in the current Node
那么这将是：
addr (next) = addr (prev) ^ (0 ^ addr (next))
由于这是头部，所以先前的地址将简单地为0，因此：
addr (next) = 0 ^ (0 ^ addr (next))
addr (next) = 0 ^ 0 addr (next)
使用 none (2) 属性，我们可以说 0 ^ 0 将始终为 0：
addr (next) = 0 ^ addr (next)
使用none (1)属性，我们可以将其简化为：
addr (next) = addr (next)
你已经获得了下一个节点的地址！
从一个节点移动到下一个节点
现在假设我们在一个中间节点，该节点有前一个和后一个节点。
让我们应用公式：
Address of Next Node = Address of Previous Node ^ pointer in the current Node
现在替换数值：
addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))
去除括号：
addr (next) = addr (prev) ^ addr (prev) ^ addr (next)
使用none (2)属性，我们可以简化：
addr (next) = 0 ^ addr (next)
使用none (1)属性，我们可以简化：
addr (next) = addr (next)
你已经得到它了！
从一个节点移动到之前所在的节点
如果你不理解标题，它基本上意味着如果你曾经在节点X，现在移动到节点Y，你想回到之前访问过的节点，或者基本上是节点X。
这并不是一项繁琐的任务。记住，我在上面提到过，你将你所在的地址存储在一个临时变量中。因此，你要访问的节点的地址就在一个变量中：
addr (prev) = temp_addr
从一个节点移动到前一个节点
这不同于上面提到的。我的意思是说，你在节点Z，现在你在节点Y，想要去节点X。
这与从一个节点移动到下一个节点几乎相同。只是相反的。当你编写程序时，你将使用我在从一个节点移动到下一个节点中提到的相同步骤，只是你要找到列表中比要找到下一个元素更早的元素。
我认为我不需要解释这个。
它使用的内存比双向链表少。大约少33%。
它只使用一个指针。这简化了节点的结构。
正如doynax所说，XOR的子部分可以在常数时间内翻转。
它有一点棘手。有更高的失败几率，并且难以进行调试。
所有转换（在int的情况下）必须发生在/从uintptr_t中。
您不能仅获取节点的地址，并从那里开始遍历（或其他操作）。您必须始终从头或尾部开始。
你不能跳跃或跳过节点。你必须一个一个地走。
移动需要更多的操作。
使用XOR链表调试程序很困难。使用双向链表要容易得多。
这是一种旧的编程技巧，可以帮助你节省内存。我认为这种方法已经不再被广泛使用了，因为内存不再像早期那样紧缺。
其基本思想是：在传统的双向链表中，你有两个指向相邻列表元素的指针，“next”指针指向下一个元素，“prev”指针指向前一个元素。因此，你可以通过使用适当的指针正向或反向遍历列表。
在减少内存的实现中，你用一个单一的值替换“next”和“prev”，这个值是“next”和“prev”的按位异或(bitwise-XOR)。因此，你减少了相邻元素指针的存储一半。
使用这种技术，仍然可以在任一方向上遍历列表，但是需要知道前一个（或下一个）元素的地址才能这样做。例如，如果你向前遍历列表，并且你有“prev”的地址，则可以通过将当前组合指针值“prev XOR next”与“prev”进行按位异或来获取“next”。结果是“prev XOR prev XOR next”，即“next”。反向遍历也可以这样做。
缺点是，如果你拥有该元素的指针，则无法像通常情况下那样删除元素，需要知道“prev”或“next”元素的地址，因为你没有上下文来解码组合指针值。
另一个缺点是，这种指针技巧规避了编译器可能期望的正常数据类型检查机制。
这是一种聪明的技巧，但老实说，我认为在现代的编程中很少有使用它的理由。
我建议查看我的第二个答案，因为它更清晰易懂。但我并不是说这个答案是错误的。这也是正确的。
一种内存高效的链表也被称为XOR链表。
XOR(^)链表是一种链表，它不是存储next和back指针，而是只使用一个指针来完成next和back指针的工作。让我们首先看看XOR逻辑门的特性：
|-------------|------------|------------|
| Name | Formula | Result |
|-------------|------------|------------|
| Commutative | A ^ B | B ^ A |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1) | A ^ 0 | A |
|-------------|------------|------------|
| None (2) | A ^ A | 0 |
|-------------|------------|------------|
| None (3) | (A ^ B) ^ A| B |
|-------------|------------|------------|
现在让我们举一个例子。我们有一个包含四个节点的双向链表：A, B, C, D。下面是它的样子：
如果您看一下，每个节点都有两个指针和一个用于存储数据的变量。因此，我们使用了三个变量。
现在，如果您有一个具有许多节点的双向链表，它将使用太多的内存。为了使其更有效率，我们使用内存高效的双向链表。
内存高效的双向链表是一种链表，在其中我们仅使用一个指针来通过XOR和它的属性前后移动。
这里是一个图示：
如何前后移动？
您有一个临时变量（只有一个，不在节点中）。假设您从左到右遍历节点。所以你从节点A开始。在节点A的指针中，您存储节点B的地址。然后移动到节点B。在移动到节点B时，在临时变量中，您存储节点A的地址。
节点B的链接（指针）变量具有A ^ C的地址。您会将前一个节点的地址（即A）与当前链接字段进行XOR运算，从而获得C的地址。逻辑上看起来像：
A ^ (A ^ C)
现在让我们简化方程。由于关联律的存在，我们可以移除括号并进行重写：
A ^ A ^ C
0 ^ C
由于第二个属性（如表中所述的“None (2)”），因此发生了这种情况。
由于第一个属性（如表中所述的“None (1)”），因此基本上是这样的。
C
如果您无法理解所有内容，只需查看表格中列出的第三个属性（“None（3）”）。
现在，您已经获得了节点C的地址。回到起点的过程是一样的。
假设你从节点C到节点B。你会将节点C的地址存储在临时变量中，然后再次执行上面给出的过程。
注意：像A、B、C这样的所有东西都是地址。感谢Bathsheba告诉我要明确这一点。
XOR链表的缺点
正如Lundin所提到的，所有转换都必须从/to uintptr_t进行。
正如Sami Kuhmonen所提到的，你必须从一个明确定义的起点开始，而不仅仅是一个随机的节点。
你不能跳过一个节点。你必须按顺序前进。
还要注意，在大多数情况下，XOR链表并不比双向链表更好。
参考资料
好的，你可能已经看过了异或链表，它可以为每个项节省一个指针... 但是这是一种丑陋、难看的数据结构，并且远非最佳选择。
如果你担心内存问题，那么通常最好使用双向链表，每个节点包含多个元素，比如数组链表。
例如，虽然异或链表每个项需要1个指针和一个值，但是一个每个节点包含16个项的双向链表只需要每16个项3个指针，即每个项只需要3/16个指针。（额外的指针是记录节点中项数的整数的成本）。这比1还要小。
除了节省内存外，由于一个节点中所有16个项在内存中相邻，所以你还可以获得局部性优势。遍历列表的算法将更快。
请注意，异或链表还要求你在添加或删除节点时每次分配或释放内存，这是一项昂贵的操作。通过允许节点不完全满，你可以做得比这更好。例如，如果你允许5个空项插槽，那么你最多只需要每3次插入或删除一次分配或释放内存。
有许多可能的策略来确定何时和如何分配或释放节点。