我在阅读一本关于 C 数据结构的书时遇到了“内存高效的双向链表”一词。它只有一行说内存高效的双向链表比普通的双向链表使用更少的内存，但做同样的工作。没有更多的解释，也没有给出例子。只是给出了这是从一本期刊中摘录的，括号中是“Sinha”。
在谷歌上搜索后，我最接近的是这个。但是，我什么都听不懂。
有人可以解释一下什么是 C 中的内存高效双向链表吗？它与普通的双向链表有何不同？
编辑：好的，我犯了一个严重的错误。请参阅我上面发布的链接，是文章的第二页。我没有看到有第一页，并认为给出的链接是第一页。文章的第一页实际上给出了解释，但我认为它并不完美。它只讨论内存高效链表或 XOR 链表的基本概念。
我知道这是我的第二个答案，但我认为我在这里提供的解释可能比上一个答案更好。但请注意，即使那个答案也是正确的。
内存高效链表更常称为XOR 链表，因为这完全取决于XOR逻辑门及其属性。
是的，是的。它实际上做的工作几乎与双向链表相同，但有所不同。
双向链表存储两个指针，分别指向下一个节点和前一个节点。基本上，如果你想回去，你就去back指针指向的地址。如果你想往前走，你就去next指针指向的地址。就像是：
内存效率高的链表，即XOR 链表只有一个指针，而不是两个。这存储上一个地址 (addr (prev)) XOR (^) 下一个地址 (addr (next))。当你想移动到下一个节点时，你做一些计算，找到下一个节点的地址。转到上一个节点也是如此。就像：
XOR Linked List ，从它的名字可以看出，高度依赖于逻辑门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 |
|-------------|------------|------------|
现在让我们把它放在一边，看看每个节点存储了什么：
第一个节点或head存储0 ^ addr (next)，因为没有先前的节点或地址。看起来像：
然后第二个节点存储addr (prev) ^ addr (next)。看起来像：
上图显示了节点 B，即第二个节点。A 和 C 是第三个和第一个节点的地址。除了头部和尾部之外的所有节点都和上面的一样。
列表的尾部，没有任何下一个节点，所以它存储addr (prev) ^ 0. 看起来像：
在看我们如何移动之前，让我们再次看一下 XOR Linked List 的表示：
当你看到
这显然意味着有一个链接字段，您可以使用它前后移动。
另外，要注意，当使用异或链表时，你需要有一个临时变量（不在节点中），它存储你之前所在节点的地址。当您移动到下一个节点时，您会丢弃旧值，并存储您之前所在节点的地址。
从头移动到下一个节点
假设您现在在第一个节点或节点 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”的按位异或（按位异或）。因此，您将相邻元素指针的存储空间减少了一半。
使用这种技术，仍然可以在任一方向遍历列表，但您需要知道上一个（或下一个）元素的地址才能这样做。例如，如果您正在向前遍历列表，并且您有“prev”的地址，那么您可以通过将“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。这是它的外观：
如果您看到，每个节点都有两个指针和 1 个用于存储数据的变量。所以我们使用三个变量。
现在，如果您有一个包含很多节点的双向链表，那么它将使用的内存太多了。为了提高效率，我们使用了内存高效的双向链表。
内存高效的双向链表是一个链表，我们只使用一个指针来使用 XOR 和它的属性来回移动。
这是一个图形表示：
你如何来回移动？
您有一个临时变量（只有一个，不在节点中）。假设您正在从左到右遍历节点。因此，您从节点 A 开始。在节点 A 的指针中，您存储节点 B 的地址。然后移动到节点 B。移动到节点 B 时，在临时变量中存储节点 A 的地址。
节点 B 的链接（指针）变量的地址为A ^ C。您将获取前一个节点的地址（即 A）并将其与当前链接字段进行异或，从而为您提供 C 的地址。从逻辑上讲，这看起来像：
A ^ (A ^ C)
现在让我们简化方程。由于 Associative 属性，我们可以删除括号并重写它，例如：
A ^ A ^ C
我们可以进一步简化为
0 ^ C
由于第二个（表中所述的“无 (2)”）属性。
由于第一个（表中所述的“None (1)”）属性，这基本上是
C
如果您无法理解这一切，只需查看第三个属性（表中所述的“None (3)”）。
现在，您获得了节点 C 的地址。这将是返回的相同过程。
假设您从节点 C 到节点 B。您将节点 C 的地址存储在临时变量中，再次执行上面给出的过程。
注意：所有像A, B,C都是地址。感谢 Bathsheba 让我说清楚。
XOR链表的缺点
正如 Lundin 提到的，所有的转换都必须从/到完成uintptr_t。
正如 Sami Kuhmonen 所提到的，您必须从一个明确定义的起点开始，而不仅仅是一个随机节点。
你不能只跳一个节点。你必须按顺序去。
另请注意，在大多数情况下，异或链表并不比双向链表好。
参考
OK, so you've seen the XOR linked list, which saves you one pointer per item... but that is an ugly, ugly data structure, and far from the best you can do.
If you're worried about memory, it's almost always better to use a doubly-linked list with more than 1 element per node, like a linked list of arrays.
For example, while an XOR linked list costs 1 pointer per item, plus the item itself, A doubly-linked list with 16 items per node costs 3 pointers for each 16 items, or 3/16 pointers per item. (the extra pointer is the cost of the integer that records how many items are in the node) That is less than 1.
In addition to the memory savings, you get advantages in locality because all 16 items in the node are next to each other in memory. Algorithms that iterate through the list will be faster.
Note that an XOR-linked list also requires you to allocate or free memory each time you add or delete a node, and that is an expensive operation. With the array-linked list, you can do better than this by allowing nodes to be less than completely full. If you allow 5 empty item slots, for example, then you only have allocate or free memory on every 3rd insert or delete at worst.
There are many possible strategies for determining how and when to allocate or free nodes.
你已经对异或链表有了相当详尽的解释，我将分享一些关于内存优化的更多想法。
在 64 位机器上，指针通常占用 8 个字节。有必要使用 32 位指针寻址超过 4GB 的 RAM 中的任何点。
内存管理器通常处理固定大小的块，而不是字节。例如，C malloc 通常在 16 字节粒度内分配。
这两件事意味着如果你的数据是 1 字节，则对应的双向链表元素将占用 32 字节（8+8+1，四舍五入到最接近的 16 倍数）。使用 XOR 技巧，您可以将其降至 16。
但是，为了进一步优化，您可以考虑使用自己的内存管理器，即：(a) 处理较低粒度的块，例如 1 字节甚至可能进入位，(b) 对整体大小有更严格的限制。例如，如果您知道您的列表将始终适合 100 MB 的连续块，那么您只需要 27 位来寻址该块中的任何字节。不是 32 位或 64 位。
如果您没有开发通用列表类，但您知道应用程序的特定使用模式，那么在许多情况下实现这样的内存管理器可能是一件容易的事。例如，如果你知道你永远不会分配超过 1000 个元素并且每个元素占用 5 个字节，你可以将内存管理器实现为 5000 字节数组，其中包含一个保存第一个空闲字节索引的变量，并且当你分配额外的元素时，您只需获取该索引并将其向前移动分配的大小。在这种情况下，您的指针将不是真正的指针（如 int*），而只是该 5000 字节数组中的索引。