什么是C中的内存有效的双链表？
在阅读关于C数据结构的书时，我遇到了“Memory-Efficient Doubly Linked List”这个术语。 它只有一行说，一个内存有效的双向链表比正常的双向链表使用更less的内存，但是做同样的工作。 没有更多的解释，也没有例子。 只是有人认为，这是从一本杂志，“支架”中的“辛哈”。
在Google上search之后，我最接近的就是这个 。 但是，我什么都不懂。
有人可以解释我什么是在C内存有效双向链接列表？ 它和正常的双链表有什么不同？
编辑：好吧，我犯了一个严重的错误。 看到我上面贴出的链接，是文章的第二页。 我没有看到有第一页，并认为给出的链接是第一页。 文章的第一页实际上给出了解释，但我不认为它是完美的。 它只讨论了内存有效链接列表或异或链接列表的基本概念。
我知道这是我的第二个答案，但我认为我在这里提供的解释可能会比上一个答案更好。 但请注意，即使这个答案是正确的。
内存有效链接列表通常被称为异或链接列表，因为这完全依赖于异或逻辑门及其属性。
它与双链表不同吗？
是的 ，是的。 它实际上做着和双链表完全一样的工作，但是它是不同的。
双链表是存储两个指向下一个和前一个节点的指针。 基本上，如果你想回去，你去到back指针指向的地址。 如果你想前进，你可以到next指针指向的地址。 就像是：
内存有效的链接列表 ，或异或链接列表只有一个指针，而不是两个。 这存储了以前的地址（addr（prev）） XOR （^）下一个地址（addr（next））。 当你想移动到下一个节点时，你需要做一些计算，并find下一个节点的地址。 对于前一个节点，这是一样的。就像：
它是如何工作的？
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 。 看起来像：
在看到我们如何移动之前，让我们再次看到XOR链接列表的表示：
当你看到
这显然意味着有一个链接领域，用你前后移动。
此外，要注意的是，在使用XOR链接列表时，您需要有一个临时variables（不在节点中），它存储您之前所在节点的地址。 当您移动到下一个节点时，您会丢弃旧值，并存储您之前所在节点的地址。
从头部移动到下一个节点
假设您现在处于第一个节点或节点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
现在replace值：
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.
这不是一个麻烦的任务。 请记住，我上面已经提到过，您将您所在的地址存储在一个临时variables中。 所以你想访问的节点的地址是在一个variables：
addr (prev) = temp_addr
从一个节点移动到前一个节点
这和上面提到的不一样。 我的意思是说，你在节点Z，现在你在节点Y，并且想要去节点X.
这与从节点移动到下一个节点几乎相同。 只是这是反之亦然。 当你编写一个程序的时候，你将使用和我刚刚提到的从一个节点移动到下一个节点相同的步骤，只是在列表中find前一个元素而不是find下一个元素。
我不认为我需要解释这一点。
异或链接列表的优势
-
这比双倍链接列表使用更less的内存。 减less了大约33％。
-
它只使用一个指针。 这简化了节点的结构。
-
正如doynax所说的那样，XOR的一个子部分可以在一段时间内反转。
异或链接列表的缺点
-
这实施起来有点棘手。 它有较高的失败几率，debugging相当困难。
-
所有的转换（如果是int）必须在
uintptr_t -
你不能只获取一个节点的地址，并从那里开始遍历（或其他）。 你必须始终从头部或尾部开始。
-
你不能跳，或跳过节点。你必须一个一个去。 -
移动需要更多的操作。
-
debugging正在使用XOR链接列表的程序是很困难的。 debugging双链表更容易。
参考
这是一个古老的编程技巧，可以让你节省内存。 我不认为它已经被使用了很多，因为记忆不再像以前那样紧密。
基本思路是：在传统的双向链表中，有两个指向相邻链表元素的指针，一个指向下一个元素的“next”指针和一个指向前一个元素的“prev”指针。 因此，您可以通过使用适当的指针向前或向后遍历列表。
在内存减less的实现中，用“下一个”和“前一个”的逐位异或（“逐位异或”）replace“下一个”和“前一个”。 因此，您将相邻元素指针的存储减less了一半。
使用这种技术，仍然可以在任一方向遍历列表，但是您需要知道前一个（或下一个）元素的地址。 例如，如果你正在向前移动列表，并且你的地址是“prev”，那么你可以通过把“prev”与当前组合指针值进行按位异或来得到“next”，这就是“prev”XOR“下一个”。 结果是“prev”XOR“prev”XOR“next”，这只是“下一个”。 在相反的方向也可以做同样的事情。
缺点是你不能做像删除一个元素，给定一个指向该元素的指针，而不知道“prev”或“next”元素的地址，因为你没有上下文来解码组合的指针值。
另一个缺点是这种指针技巧绕过了编译器可能期望的正常数据types检查机制。
这是一个聪明的伎俩，但是诚实地说，这几天我没有理由使用它。
我build议看到我对这个问题的第二个答案 ，因为它更清楚。 但我不是说这个答案是错的。 这也是正确的。
内存有效链接列表也被称为异或链接列表 。
它是如何工作的
XOR （^）链接列表是一个链接列表，其中不是存储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 | |-------------|------------|------------|
现在让我们举一个例子。 我们有一个双链表，有四个节点： A，B，C，D 。 以下是它的外观：
如果你看到，每个节点有两个指针，1个variables用于存储数据。 所以我们使用三个variables。
现在如果你有一个节点很多的双链表，它将使用的内存太多了。 为了使效率更高，我们使用了一个Memory-Efficient双链表 。
内存有效的双链表是一个链表，我们只用一个指针来来回移动使用异或它的属性。
这是一个graphics表示：
你如何来回移动？
你有一个临时variables（只有一个，不在节点中）。 假设您正在从左到右遍历节点。 所以你从节点A开始。在节点A的指针中，存储节点B的地址。 然后移动到节点B.在移动到节点B时，在临时variables中存储节点A的地址。
节点B的链接（指针）variables的地址为A ^ C 你可以把前一个节点的地址（它是A）和XOR与当前链接字段进行比较，给出C的地址。逻辑上，这看起来像：
A ^ (A ^ C)
现在我们来简化公式。 我们可以删除括号并重写它，因为关联属性如下所示：
A ^ A ^ C
我们可以进一步简化这个
0 ^ C
因为第二个（表中没有“无（2）”）财产。
由于第一项（表中“无（1）”）财产，这基本上是
C
如果你不能理解这一切，只要看看表中的第三个属性（“None（3）”）。
现在，你得到了节点C的地址。这将是返回的相同过程。
假设您正在从节点C到节点B.您可以将节点C的地址存储在临时variables中，再次执行上面给出的过程。
注意： A ， B ， C都是地址。 感谢Bathsheba告诉我要说清楚。
异或链接列表的缺点
-
正如Lundin所说的，所有的转换都必须从
uintptr_t。 -
正如Sami Kuhmonen提到的，你必须从一个明确的起点开始，而不仅仅是一个随机节点。
-
你不能只跳一个节点。 你必须按顺序
另外请注意，在大多数情况下，异或链接列表并不比双向链表更好。
参考
好的，所以你已经看到了异或链表，它为你节省了一个指针，但是这是一个丑陋的，丑陋的数据结构，远远不能做到最好。
如果你担心内存，使用每个节点超过1个元素的双向链表（比如数组的链表）就更好了。
例如，异或链接列表每个项目花费1个指针加上项目本身，每个节点16个项目的双向链接列表花费每个16个项目3个指针或每个项目3/16个指针。 （额外的指针是logging节点中有多less项目的整数的成本）小于1。
除了节省内存之外，您还可以在本地获得优势，因为节点中的所有16个项目在内存中彼此相邻。 遍历列表的algorithm会更快。
请注意，XOR链接列表还要求您在每次添加或删除节点时分配或释放内存，这是一项昂贵的操作。 通过数组链表，你可以做得比这更好，通过允许节点less于完全满。 例如，如果允许5个空的项目插槽，则每隔3分钟只能分配或释放内存，或者在最差的情况下删除内存。
确定如何以及何时分配或释放节点有许多可能的策略。
你已经有了XOR链表的详细解释，我将分享一些关于内存优化的更多的想法。
-
指针通常在64位机器上占用8个字节。 需要使用32位指针寻址超过4GB的RAM地址。
-
内存pipe理器通常处理固定大小的块，而不是字节。 例如C malloc通常在16字节的粒度内分配。
这两件事意味着如果你的数据是1个字节，相应的双向链表元素将占用32个字节（8 + 8 + 1，四舍五入到最接近的16倍）。 XOR技巧，你可以把它降到16。
但是，为了进一步优化，可以考虑使用自己的内存pipe理器：（a）处理较低粒度的块，例如1字节，甚至可能进入比特，（b）对整体大小有更严格的限制。 例如，如果您知道您的列表将始终适合100 MB的连续块，则只需要27位即可处理该块中的任何字节。 不是32或64位。
如果你没有开发一个通用的列表类，但你知道你的应用程序的具体使用模式，在许多情况下实现这样的内存pipe理器可能是一件容易的工作。 例如，如果您知道永远不会分配超过1000个元素，并且每个元素需要5个字节，则可以将内存pipe理器实现为具有保存第一个空闲字节索引的variables的5000字节数组，并且在分配额外元素时，你只需要索引，并通过分配的大小向前移动它。 在这种情况下，你的指针不会是真正的指针（如int *），而只是5000字节数组中的索引。
