什么是 C 中的内存高效双向链表？
What is a Memory-Efficient Doubly Linked List in C?
我在阅读有关 C 数据结构的书时遇到了术语 "Memory-Efficient Doubly Linked List"。它只有一行说内存高效的双重 linked 列表比普通的双重 linked 列表使用更少的内存，但做同样的工作。没有更多的解释，也没有给出例子。只是假设这是从期刊中获取的，并且 "Sinha" 在括号中。
在 Google 上搜索后，我最接近的是 this。但是，我什么都听不懂。
谁能给我解释一下什么是 C 语言中的内存高效双向链表？它与普通的双向链表有何不同？
编辑： 好吧，我犯了一个严重的错误。看我上面发的link，是文章的第二页。没看到有首页，还以为给的link是首页。文章的第一页其实已经给出了解释，但我觉得还不够完美。它只讨论了内存高效链表或异或链表的基本概念。
我建议看我的这个问题，因为它更清楚。但我并不是说这个答案是错误的。这也是正确的。
A Memory-Efficient Linked List 也称为 XOR Linked LIST.
它是如何工作的
A XOR (^) Linked 列表是一个 Link 列表，而不是存储 next 和 back 指针，我们只使用 一个 指针来完成 next 和 back 指针的工作。让我们先看看异或逻辑门的属性：
|-------------|------------|------------|
| 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 |
|-------------|------------|------------|
现在让我们举个例子。我们有一个包含四个节点的双重 linked 列表：A、B、C、D。外观如下：
如你所见，每个节点都有两个指针，和1个存储数据的变量。所以我们使用三个变量。
现在，如果您有一个包含大量节点的双 Linked 列表，它将使用的内存将太多。为了提高效率，我们使用 内存高效双 Linked 列表。
A Memory-Efficient Doubly Linked List 是一个 Linked List，其中我们仅使用一个指针通过 XOR 来回移动及其属性。
这是图示：
怎么来回移动的？
您有一个临时变量（只有一个，不在节点中）。假设您要从左到右遍历节点。因此，您从节点 A 开始。在节点 A 的指针中，您存储了节点 B 的地址。然后移动到节点 B。移动到节点 B 时，在临时变量中存储节点 A 的地址。
节点B的link（指针）变量的地址为A ^ C。您将获取前一个节点的地址（即 A）并将其与当前的 link 字段进行异或，得到 C 的地址。从逻辑上讲，这看起来像：
A ^ (A ^ C)
现在让我们简化方程式。我们可以删除括号并重写它，因为 Associative 属性 like:
A ^ A ^ C
我们可以进一步简化为
0 ^ C
因为第二个（“None(2)”如table中所述）属性.
因为第一个(None(1)"如table)所述属性，这基本上是
C
如果你不能理解这一切，就简单地看第三个属性（“None (3)” as stated in the table).
现在，你得到了节点C的地址。这将是返回相同的过程。
假设您要从节点 C 到节点 B。您会将节点 C 的地址存储在临时变量中，然后再次执行上面给出的过程。
注意： A、B、C 等都是地址。感谢 Bathsheba 告诉我说清楚。
XOR 的缺点 Linked List
正如伦丁所说，所有的转换都必须完成 from/to uintptr_t.
正如 Sami Kuhmonen 提到的，你必须从一个明确定义的起点开始，而不仅仅是一个随机节点。
你不能只跳过一个节点。一定要按顺序走。
另请注意，在大多数情况下，异或 Linked 列表 并不 优于双重 linked 列表。
参考资料
我知道这是我的第二个答案，但我认为我在这里提供的解释可能比上一个答案更好。但请注意，即使那个答案也是正确的。
A Memory-Efficient Linked List 通常被称为 XOR Linked List 因为这完全依赖于 XOR逻辑门及其属性。
它和双向链表有区别吗？
是，是的。它实际上做的工作与双向链表几乎相同，但又有所不同。
A Doubly-Linked List 存储了两个指针，分别指向下一个节点和上一个节点。基本上，如果你想回去，你就去back指针指向的地址。如果要往前走，就到next指针指向的地址。就像：
一个Memory-Efficient链表，或者说异或链表只有一个指针而不是两个。这存储了前一个地址(addr(prev))XOR(^)下一个地址(addr(next))。当你想移动到下一个节点时，你做一些计算，找到下一个节点的地址。这和去之前一样 node.It 就像：
它是如何工作的？
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。看起来像：
在看我们如何移动之前，让我们再看看异或链表的表示：
当你看到
这显然意味着有一个 link 字段，您可以使用它来回移动。
另外需要注意的是，在使用XOR Linked List时，需要有一个临时变量（不在节点中），它存储的是你之前所在节点的地址。当你移动到下一个节点时，你丢弃旧值，并存储你之前所在的节点的地址。
从Head移动到下一个节点
假设你现在在第一个节点，或者在节点 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。
这与从一个节点移动到下一个节点几乎相同。只是这是 vice-versa。当您编写程序时，您将使用与我在从一个节点移动到下一个节点时提到的相同的步骤，只是您在列表中查找较早的元素而不是查找下一个元素。
我想我不需要解释这个。
异或链表的优点
这比 双向链表使用更少的内存。大约减少 33%。
它只使用一个指针。这样就简化了节点的结构。
正如doynax所说，异或的sub-section可以在常数时间内反转。
异或链表的缺点
这实现起来有点棘手。失败几率较高，调试难度较大。
所有转换（在 int 的情况下）必须发生到/从 uintptr_t
你不能只获取一个节点的地址，然后从那里开始遍历（或其他）。您必须始终从头或尾开始。
你不能跳，也不能跳过节点。你得一个一个去。
移动需要更多操作。
很难调试使用 XOR 链表的程序。调试双向链表要容易得多。
参考资料
好的，你已经看到了 XOR 链表，它为每个项目节省了一个指针......但这是一个非常丑陋的数据结构，远非你能做到的最好。
如果您担心内存问题，使用每个节点超过 1 个元素的双向链表几乎总是更好，例如数组链表。
例如，XOR 链表每个项目需要 1 个指针，加上项目本身，而每个节点有 16 个项目的双向链表每 16 个项目需要 3 个指针，或每个项目 3/16 个指针。 （额外的指针是记录节点中有多少项的整数的成本）小于1.
除了节省内存之外，您还可以获得局部优势，因为节点中的所有 16 个项目在内存中彼此相邻。遍历列表的算法会更快。
请注意，异或链表还需要您在每次添加或删除节点时分配或释放内存，这是一项昂贵的操作。使用数组链表，您可以通过允许节点少于完全填满来做得更好。例如，如果你允许 5 个空项目槽，那么最坏情况下你只能在每 3 次插入或删除时分配或释放内存。
有许多可能的策略来确定如何以及何时分配或释放节点。
这是一个古老的编程技巧，可以节省内存。我认为它不再被广泛使用，因为内存不再像过去那样紧张。
基本思想是这样的：在传统的双向链表中，有两个指向相邻列表元素的指针，一个指向下一个元素的 "next" 指针，以及一个 "prev" 指针指向前一个元素。因此，您可以使用适当的指针向前或向后遍历列表。
在减少内存的实现中，您将 "next" 和 "prev" 替换为单个值，该值是 "next" 和 [ 的按位异或 (bitwise-XOR) =25=]。因此，您将相邻元素指针的存储空间减少了一半。
使用这种技术，仍然可以在任一方向遍历列表，但您需要知道前一个（或下一个）元素的地址才能这样做。例如，如果你正向遍历列表，并且你有 "prev" 的地址，那么你可以通过对 "prev" 与当前地址进行按位异或来得到 "next"组合指针值，即"prev"异或"next"。结果是"prev"异或"prev"异或"next"，就是"next"。反之亦然。
缺点是你不能在不知道 "prev" 或 "next" 元素的地址的情况下执行删除元素之类的操作，给定指向该元素的指针，因为你有没有用于解码组合指针值的上下文。
另一个缺点是这种指针技巧绕过了编译器可能期望的正常数据类型检查机制。
这是一个聪明的技巧，但老实说，这些天我看不出有什么理由使用它。
你已经对异或链表有了相当详尽的解释，我将分享更多关于内存优化的想法。
指针在 64 位机器上通常占用 8 个字节。有必要使用 32 位指针寻址超过 4GB 的 RAM 中的任何点。
内存管理器通常处理固定大小的块，而不是字节。例如。 C malloc 通常在 16 字节粒度内分配。
这两件事意味着如果你的数据是1个字节，对应的双向链表元素将占用32个字节（8+8+1，四舍五入到最接近的16倍数）。使用 XOR 技巧，您可以将其降低到 16。
然而，为了进一步优化，您可以考虑使用您自己的内存管理器，即：
(a) 以较低的粒度处理块，例如 1 字节甚至可能进入位，
(b) 对总体规模有更严格的限制。例如，如果您知道您的列表总是适合一个 100 MB 的连续块，那么您只需要 27 位来寻址该块中的任何字节。不是 32 或 64 位。
如果您没有开发通用列表 class，但您知道应用程序的特定使用模式，那么在许多情况下实施此类内存管理器可能很容易。例如，如果您知道您永远不会分配超过 1000 个元素并且每个元素占用 5 个字节，您可以将内存管理器实现为 5000 字节的数组，并使用一个变量保存第一个空闲字节的索引，并且当您分配额外的元素时，您只需获取该索引并将其向前移动分配的大小。在这种情况下，您的指针将不是真正的指针（如 int*），而只是该 5000 字节数组中的索引。
我在阅读有关 C 数据结构的书时遇到了术语 "Memory-Efficient Doubly Linked List"。它只有一行说内存高效的双重 linked 列表比普通的双重 linked 列表使用更少的内存，但做同样的工作。没有更多的解释，也没有给出例子。只是假设这是从期刊中获取的，并且 "Sinha" 在括号中。
在 Google 上搜索后，我最接近的是 this。但是，我什么都听不懂。
谁能给我解释一下什么是 C 语言中的内存高效双向链表？它与普通的双向链表有何不同？
编辑： 好吧，我犯了一个严重的错误。看我上面发的link，是文章的第二页。没看到有首页，还以为给的link是首页。文章的第一页其实已经给出了解释，但我觉得还不够完美。它只讨论了内存高效链表或异或链表的基本概念。
我建议看我的
A Memory-Efficient Linked List 也称为 XOR Linked LIST.
它是如何工作的
A XOR (^) Linked 列表是一个 Link 列表，而不是存储 next 和 back 指针，我们只使用 一个 指针来完成 next 和 back 指针的工作。让我们先看看异或逻辑门的属性：
|-------------|------------|------------|
| 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 |
|-------------|------------|------------|
现在让我们举个例子。我们有一个包含四个节点的双重 linked 列表：A、B、C、D。外观如下：
如你所见，每个节点都有两个指针，和1个存储数据的变量。所以我们使用三个变量。
现在，如果您有一个包含大量节点的双 Linked 列表，它将使用的内存将太多。为了提高效率，我们使用 内存高效双 Linked 列表。
A Memory-Efficient Doubly Linked List 是一个 Linked List，其中我们仅使用一个指针通过 XOR 来回移动及其属性。
这是图示：
怎么来回移动的？
您有一个临时变量（只有一个，不在节点中）。假设您要从左到右遍历节点。因此，您从节点 A 开始。在节点 A 的指针中，您存储了节点 B 的地址。然后移动到节点 B。移动到节点 B 时，在临时变量中存储节点 A 的地址。
节点B的link（指针）变量的地址为A ^ C。您将获取前一个节点的地址（即 A）并将其与当前的 link 字段进行异或，得到 C 的地址。从逻辑上讲，这看起来像：
A ^ (A ^ C)
现在让我们简化方程式。我们可以删除括号并重写它，因为 Associative 属性 like:
A ^ A ^ C
我们可以进一步简化为
0 ^ C
因为第二个（“None(2)”如table中所述）属性.
因为第一个(None(1)"如table)所述属性，这基本上是
C
如果你不能理解这一切，就简单地看第三个属性（“None (3)” as stated in the table).
现在，你得到了节点C的地址。这将是返回相同的过程。
假设您要从节点 C 到节点 B。您会将节点 C 的地址存储在临时变量中，然后再次执行上面给出的过程。
注意： A、B、C 等都是地址。感谢 Bathsheba 告诉我说清楚。
XOR 的缺点 Linked List
正如伦丁所说，所有的转换都必须完成 from/to
uintptr_t.正如 Sami Kuhmonen 提到的，你必须从一个明确定义的起点开始，而不仅仅是一个随机节点。
你不能只跳过一个节点。一定要按顺序走。
另请注意，在大多数情况下，异或 Linked 列表 并不 优于双重 linked 列表。
参考资料
我知道这是我的第二个答案，但我认为我在这里提供的解释可能比上一个答案更好。但请注意，即使那个答案也是正确的。
A Memory-Efficient Linked List 通常被称为 XOR Linked List 因为这完全依赖于 XOR逻辑门及其属性。
它和双向链表有区别吗？
是，是的。它实际上做的工作与双向链表几乎相同，但又有所不同。
A Doubly-Linked List 存储了两个指针，分别指向下一个节点和上一个节点。基本上，如果你想回去，你就去back指针指向的地址。如果要往前走，就到next指针指向的地址。就像：
一个Memory-Efficient链表，或者说异或链表只有一个指针而不是两个。这存储了前一个地址(addr(prev))XOR(^)下一个地址(addr(next))。当你想移动到下一个节点时，你做一些计算，找到下一个节点的地址。这和去之前一样 node.It 就像：
它是如何工作的？
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。看起来像：
在看我们如何移动之前，让我们再看看异或链表的表示：
当你看到
这显然意味着有一个 link 字段，您可以使用它来回移动。
另外需要注意的是，在使用XOR Linked List时，需要有一个临时变量（不在节点中），它存储的是你之前所在节点的地址。当你移动到下一个节点时，你丢弃旧值，并存储你之前所在的节点的地址。
从Head移动到下一个节点
假设你现在在第一个节点，或者在节点 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。
这与从一个节点移动到下一个节点几乎相同。只是这是 vice-versa。当您编写程序时，您将使用与我在从一个节点移动到下一个节点时提到的相同的步骤，只是您在列表中查找较早的元素而不是查找下一个元素。
我想我不需要解释这个。
异或链表的优点
这比 双向链表使用更少的内存。大约减少 33%。
它只使用一个指针。这样就简化了节点的结构。
正如doynax所说，异或的sub-section可以在常数时间内反转。
异或链表的缺点
这实现起来有点棘手。失败几率较高，调试难度较大。
所有转换（在 int 的情况下）必须发生到/从
uintptr_t你不能只获取一个节点的地址，然后从那里开始遍历（或其他）。您必须始终从头或尾开始。
你不能跳，也不能跳过节点。你得一个一个去。移动需要更多操作。
很难调试使用 XOR 链表的程序。调试双向链表要容易得多。
参考资料
好的，你已经看到了 XOR 链表，它为每个项目节省了一个指针......但这是一个非常丑陋的数据结构，远非你能做到的最好。
如果您担心内存问题，使用每个节点超过 1 个元素的双向链表几乎总是更好，例如数组链表。
例如，XOR 链表每个项目需要 1 个指针，加上项目本身，而每个节点有 16 个项目的双向链表每 16 个项目需要 3 个指针，或每个项目 3/16 个指针。 （额外的指针是记录节点中有多少项的整数的成本）小于1.
除了节省内存之外，您还可以获得局部优势，因为节点中的所有 16 个项目在内存中彼此相邻。遍历列表的算法会更快。
请注意，异或链表还需要您在每次添加或删除节点时分配或释放内存，这是一项昂贵的操作。使用数组链表，您可以通过允许节点少于完全填满来做得更好。例如，如果你允许 5 个空项目槽，那么最坏情况下你只能在每 3 次插入或删除时分配或释放内存。
有许多可能的策略来确定如何以及何时分配或释放节点。
这是一个古老的编程技巧，可以节省内存。我认为它不再被广泛使用，因为内存不再像过去那样紧张。
基本思想是这样的：在传统的双向链表中，有两个指向相邻列表元素的指针，一个指向下一个元素的 "next" 指针，以及一个 "prev" 指针指向前一个元素。因此，您可以使用适当的指针向前或向后遍历列表。
在减少内存的实现中，您将 "next" 和 "prev" 替换为单个值，该值是 "next" 和 [ 的按位异或 (bitwise-XOR) =25=]。因此，您将相邻元素指针的存储空间减少了一半。
使用这种技术，仍然可以在任一方向遍历列表，但您需要知道前一个（或下一个）元素的地址才能这样做。例如，如果你正向遍历列表，并且你有 "prev" 的地址，那么你可以通过对 "prev" 与当前地址进行按位异或来得到 "next"组合指针值，即"prev"异或"next"。结果是"prev"异或"prev"异或"next"，就是"next"。反之亦然。
缺点是你不能在不知道 "prev" 或 "next" 元素的地址的情况下执行删除元素之类的操作，给定指向该元素的指针，因为你有没有用于解码组合指针值的上下文。
另一个缺点是这种指针技巧绕过了编译器可能期望的正常数据类型检查机制。
这是一个聪明的技巧，但老实说，这些天我看不出有什么理由使用它。
你已经对异或链表有了相当详尽的解释，我将分享更多关于内存优化的想法。
指针在 64 位机器上通常占用 8 个字节。有必要使用 32 位指针寻址超过 4GB 的 RAM 中的任何点。
内存管理器通常处理固定大小的块，而不是字节。例如。 C malloc 通常在 16 字节粒度内分配。
这两件事意味着如果你的数据是1个字节，对应的双向链表元素将占用32个字节（8+8+1，四舍五入到最接近的16倍数）。使用 XOR 技巧，您可以将其降低到 16。
然而，为了进一步优化，您可以考虑使用您自己的内存管理器，即： (a) 以较低的粒度处理块，例如 1 字节甚至可能进入位， (b) 对总体规模有更严格的限制。例如，如果您知道您的列表总是适合一个 100 MB 的连续块，那么您只需要 27 位来寻址该块中的任何字节。不是 32 或 64 位。
如果您没有开发通用列表 class，但您知道应用程序的特定使用模式，那么在许多情况下实施此类内存管理器可能很容易。例如，如果您知道您永远不会分配超过 1000 个元素并且每个元素占用 5 个字节，您可以将内存管理器实现为 5000 字节的数组，并使用一个变量保存第一个空闲字节的索引，并且当您分配额外的元素时，您只需获取该索引并将其向前移动分配的大小。在这种情况下，您的指针将不是真正的指针（如 int*），而只是该 5000 字节数组中的索引。