使用单指针字段存储双向链表

Question

使用单指针字段存储双向链表

9

最近我读了一篇文章，向我展示了如何使用单个指针字段实现双向链表，即像单向链表那样。它涉及将XOR prev和next地址存储在单个字段中。我不明白这如何帮助我们遍历前面和后面？有人能解释一下吗？我在这里阅读了该文章。有人能更详细地解释一下吗？XOR与这些地址有什么关系。

- Izy-

2

下面有几个解释得很好的答案，所以我跳过那些并简单评论一件事情。存在某些平台不支持这种操作（事实上，有些平台会将if (ptr)评估为false，如果指针值是不确定的或者并非来自“适当”的分配函数或&-运算符）。通常在汇编语言级别上是通过这种方式来节省宝贵的字节。如今很少需要这样做了（通常用于嵌入式系统），而且使代码难以阅读和维护。好技巧，好传说，现在就忘了它吧 =P。 - WhozCraig

啊，我明白这是一种旧的、未使用的方法。问题是，我在某个地方读到过这个作为面试题。我很好奇它是如何工作的。当然，今天我们没有必要在这么小的空间上进行压缩。尽管如此，这个想法是创新的，而且纯粹是为了我的理解。 - Izy-

5个回答

1

是这样的：

你正在某个节点。你需要前往下一个节点。但你只有一个变量，需要存储两个指针的值。这可能吗？

我们利用了这样一个事实：当我们遍历列表时，我们知道先前访问的节点的地址。但是如何做到呢？

所以，问题归结为：

我们需要在单个变量中存储两个值。在任何时候，我们都知道其中任意一个。我们需要找到另一个。这可能吗？

答案是肯定的。

v = a^b;
then v^b = a and v^a = b

现在，将这个概念应用到DLL中。

在当前节点中存储前一个和后一个节点地址的异或值。

当您希望遍历到下一个节点时，使用当前节点中存储的值与前一个节点的地址进行异或。您可以遍历到下一个节点。同样，也可以向后遍历。

- nitish712

1

XOR 有一个有趣的特性：如果你知道 A 和 C = A^B，你可以计算出 A^C = A^(A^B) = (A^A)^B = B。

在链表中，如果你已知正向指针或反向指针和两个指针的异或结果，你可以通过一次异或来找到另一个指针。当你遍历链表时，你已经拥有其中一个指针，所以你只需要知道异或结果就可以找到另一个指针了；因此不需要存储两个指针。

- Joni

嗯，我明白了。但是您能否给我们举一个实际例子（使用虚拟地址值），以便我们更清楚地理解这个概念？ - Izy-

好的。假设您有一个带有后向指针1和前向指针3的节点。该节点存储1^3 = 2。现在，如果您向前迭代列表，则从地址为1的节点到达此节点。1^2 = 3，因此下一个节点是3。同样，如果您向后迭代，则从地址为3的节点到达此节点。现在3^2 = 1，因此下一个节点具有地址1。 - Joni

有趣。但是它似乎有点奇怪。让我澄清一些事情。你说“假设你有一个带有向后指针和向前指针的节点”。那不是使它本身成为双向链表吗？而且，拥有向后指针1和向前指针3，这难道不是使当前节点成为地址2的节点吗？ - Izy-

你正在实现一个双向链表，因此节点将具有两个指针，或者至少有一种方法可以获取它们。通过这种技巧，指针并不是直接存储的，但仍然有一种方法可以计算它们。当前节点可能具有任何地址，这并不重要，重要的是它存储了2，这是两个指针的异或值。 - Joni

0

Nitish的解释很好。这种解释使得理解这个概念变得非常容易。

如果我能让它更简单，那就更有用了。假设你有3个节点，分别是A、B和C。存储在A中的地址为1（即二进制01），在B中为2（即二进制10），在C中为3（即二进制11）。这种方式更加清晰易懂。

A    B    C
01   10   11  --->>this 01,10,11 are addresses.

现在，异或属性表明当位相同时我们得到0，否则为1。因此，当您的当前节点是B（即在地址10处）并且您想向前移动时。也就是说，您需要做的是A XOR B或01 XOR 10，即

     01
xor  10
    =11 i.e by doing xor of 01 and 10 it will make you reach at 11 address that is C.

类似地，当你执行10异或11时，答案是01，即A。

- Chandresh Dwivedi

0

据我所知，这取决于异或运算符的属性，例如：

A XOR A = 0

当使用双向链表时，您必须在结构中保存“下一个”和“上一个”地址。作者说为了节省空间，您可以只存储：

next XOR prev

并通过执行以下操作来浏览列表：

next = current XOR prev

next = (next XOR prev) XOR prev

next = next XOR (prev XOR prev)

但我真的不明白这一点，因为在这个例子中，您仍然需要知道“prev”才能进行计算...

- n0p

这个想法是，如果你正在向前遍历列表，你知道 prev 并且想要 next。如果你正在向后遍历，你知道 next 并且想要 prev。无论哪种方式，你都知道 XOR 输入中的一个，并需要知道另一个。 - Patricia Shanahan

好的，但是如果你只提供一个元素的指针，那么你就会陷入困境。因此，这是一种具有有限兴趣的优化（即它只在非常特定的情况下有用）。 - n0p

在我作为专业程序员的30多年中，我从未遇到过一种情况，其中使用它所获得的内存增益足以证明灵活性和代码清晰度上的成本。我认为这是一种理论上的好奇心，而不是一种有用的模式。 - Patricia Shanahan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pandrei · Accepted Answer

作为这篇文章所指出的，这种技术只有在你拥有链表头或尾的指针时才有用；如果你只有链表中间的指针，则无处可去。

关于这种技术：考虑以下链接列表：

|0|A|0x01|<->|0x01|B|0x02|<->|0x02|C|0|

这个列表包含3个节点，值为A，B，C，并且prev/next指针包含列表中前一个/后一个元素的十六进制值（地址）。值0表示空。
我们可以只使用一个指针来替代存储2个指针，正如文章所解释的那样：

|A|0x01|<->|B|0x03|<->|C|0x03|

我们将新字段称为link = prev XOR next。因此，考虑到这一点：

    A.link = 0^0x01 = 0x01
    B.link = 0x01^0x02 = 0x03
    C.link = 0x03^0x0 = 0x03.

假设您有指向列表头的指针（您知道其prev指针设置为null），以下是如何遍历列表的方法：

 p=head; 
 prev = 0;
 while(p.link!=prev)
 {
   next = p.link^prev
   prev=p
   p=next 
 }

你可以使用相同的逻辑向列表后面移动。