什么是C中的内存高效双链表？

Question

在阅读有关C数据结构的书时,我遇到了"内存高效的双重链接列表"这个术语.它只有一行说一个内存有效的双向链表使用比普通双链表更少的内存,但做同样的工作.没有更多的解释,也没有给出任何例子.只是有人认为这是从一本期刊中获取的,而在"Brackets"中则是"Sinha".

在Google上搜索后,我最接近的就是这个.但是,我什么都听不懂.

有人能解释一下C中的内存高效双链表是什么？它与正常的双向链接列表有什么不同？

编辑:好的,我犯了一个严重的错误.看到我上面发布的链接,是文章的第二页.我没有看到有第一页,并认为给出的链接是第一页.文章的第一页实际上给出了解释,但我不认为它是完美的.它只讨论了Memory-Efficient Linked List或XOR Linked List的基本概念.

Answer 1

我知道这是我的第二个答案,但我认为我在这里提供的解释可能比最后一个答案更好.但请注意,即使这个答案也是正确的.

甲内存效率链表更通常被称为异或链表,因为这是完全依赖于XOR逻辑门和其属性.

它与双重链接列表不同吗？

是的,确实如此.它实际上与双重链接列表几乎完成相同的工作,但它是不同的.

甲双链表正存储两个指针,其在下一和前一节点指向.基本上,如果你想回去,你会转到back指针指向的地址.如果你想前进,你会转到next指针指向的地址.就像是:

甲内存效率链表,或即异或链表是仅具有一个指针,而不是两个.这将先前的地址(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.看起来像:

在看到我们如何移动之前,让我们再次看到XOR链接列表的表示:

当你看到

它显然意味着有一个链接字段,使用它前后移动.

另外,要注意当使用XOR链接列表时,您需要一个临时变量(不在节点中),它存储您之前所在节点的地址.当您移动到下一个节点时,您将丢弃旧值,并存储您之前所在节点的地址.

从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.

这与从节点移动到下一个节点几乎相同.只是这是反之亦然.编写程序时,您将使用我在从一个节点移动到下一个节点时提到的相同步骤,只是您在列表中找到了比查找下一个元素更早的元素.

我认为我不需要解释这一点.

XOR链接列表的优点

• 这比双链表使用更少的内存.减少约33%.

• 它只使用一个指针.这简化了节点的结构.

• 正如doynax所说,XOR的一个子部分可以在恒定时间内反转.

XOR链接列表的缺点

• 实施起来有点棘手.它有更高的失败机会,调试非常困难.

• 所有转换(如果是int)都必须进行转换 uintptr_t

• 您不仅可以获取节点的地址,还可以从那里开始遍历(或其他).你必须始终从头部或尾部开始.

• 你不能跳跃或跳过节点.你必须一个接一个地去.

• 移动需要更多操作.

• 调试使用XOR链接列表的程序很困难.调试双向链表更容易.

参考

• http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/

• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/

Answer 2

这是一个旧的编程技巧,可以节省内存.我不认为它已经用得太多了,因为记忆不再像过去那样紧张.

基本思想是这样的:在传统的双向链表中,你有两个指向相邻列表元素的指针,一个指向下一个元素的"下一个"指针,以及一个指向前一个元素的"prev"指针.因此,您可以使用适当的指针向前或向后遍历列表.

在内存减少的实现中,将"next"和"prev"替换为单个值,即"next"和"prev"的按位异或(bitwise-XOR).因此,您将相邻元素指针的存储空间减少了一半.

使用这种技术,仍然可以在任一方向上遍历列表,但您需要知道前一个(或下一个)元素的地址.例如,如果您正在向前遍历列表,并且您具有"prev"的地址,那么您可以通过使用当前组合指针值的"prev"的按位-XOR来获得"下一个",这是"prev"XOR"下一步".结果是"prev"XOR"prev"XOR"next",这只是"下一步".同样可以在相反的方向上完成.

缺点是你不能做一些事情,如删除一个元素,给定一个指向该元素的指针,而不知道"prev"或"next"元素的地址,因为你没有用于解码组合指针的上下文值.

另一个缺点是这种指针技巧绕过了编译器可能期望的普通数据类型检查机制.

这是一个聪明的伎俩,但说实话,我觉得这些天使用它的理由很少.

Answer 3

我建议看到我对这个问题的第二个答案,因为它更清楚.但我不是说这个答案是错的.这也是正确的.

一个内存效率链表也被称为异或链表.

它是如何工作的

一个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)")属性.

由于第一个(表中所述的"无(1)")属性,这基本上是

C

如果您无法理解所有这些,只需查看第三个属性(表中所述的"None(3)").

现在,您获得了节点C的地址.这将是返回的相同过程.

假设您从节点C到节点B.您将节点C的地址存储在临时变量中,再次执行上面给出的过程.

注:一切都像A,B,C是地址.感谢Bathsheba告诉我说清楚.

XOR链接列表的缺点

• 正如Lundin所说,所有的转换都必须从/到uintptr_t.

• 正如Sami Kuhmonen所提到的,你必须从明确定义的起点开始,而不仅仅是一个随机节点.

• 你不能只跳一个节点.你必须按顺序排序.

还要注意,异或链表是不是比在大多数情况下,双向链表更好.

参考

• https://en.wikipedia.org/wiki/XOR_linked_list
• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/
• http://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/

Answer 4

好的,所以你已经看到了XOR链表,它为每个项目节省了一个指针...但这是一个丑陋,丑陋的数据结构,远远不是你能做的最好的.

如果您担心内存,那么使用每个节点超过1个元素的双向链表几乎总是更好,就像链接的数组列表一样.

例如,虽然XOR链接列表每个项目需要1个指针,加上项目本身,但每个节点有16个项目的双向链接列表每16个项目需要3个指针,或者每个项目需要3/16个指针.(额外指针是记录节点中有多少项的整数的成本)小于1.

除了节省内存之外,您还可以获得本地优势,因为节点中的所有16个项目在内存中彼此相邻.迭代列表的算法会更快.

请注意,每次添加或删除节点时,XOR链接列表还要求您分配或释放内存,这是一项昂贵的操作.使用阵列链接列表,您可以通过允许节点小于完全填充来做得更好.例如,如果允许5个空项目插槽,那么每次第3次插入时只分配或释放内存,或者最差时删除.

有许多可能的策略来确定如何以及何时分配或释放节点.