问题标签 [xor-linkedlist]

I am reading XOR linked list (from Wikipedia).But I am having some problems in understanding it.

I am not getting following paragraph.

To start traversing the list in either direction from some point, you need the address of two consecutive items, not just one. If the addresses of the two consecutive items are reversed, you will end up traversing the list in the opposite direction.

I have few questions about it :

1. How does it (the XOR linked list itself) actually work ?

   (It would be great if you justify your answer by giving some example.i.e by taking some addresses and then doing some calculations accordingly.)

2. How can I implement it? A brief idea about implementation.

3. Practically where it is or can be used? Is it really helpful as it seems?

我想为xor-linked list编写 java 代码。有人可以建议我如何在引用之间执行异或操作吗？

我最近遇到了下面的链接，我发现它很有趣。

http://en.wikipedia.org/wiki/XOR_linked_list

• 通用调试工具不能遵循异或链，调试难度较大；[1]
• 内存使用量减少的代价是代码复杂度的增加，使得维护成本更高；
• 大多数垃圾收集方案不适用于不包含文字指针的数据结构；
• 在某些上下文（例如，C 语言）中没有定义指针的异或，尽管许多语言提供了指针和整数之间的某种类型转换；
• 如果不遍历列表，则指针将不可读——例如，如果指向列表项的指针包含在另一个数据结构中；
• 在遍历列表时，您需要记住先前访问的节点的地址，以便计算下一个节点的地址。

现在我想知道这是否是低级语言独有的，还是在 C# 中也可以？

是否有任何类似的选项可以使用 C# 产生相同的结果？

这是我的异或链表实现代码

但是当我编译它时，它给了我这样的错误

为什么它是模棱两可的符号结束？这个错误是什么意思？

我正在阅读有关 XOR 链接列表的内容，我想到了一个问题，在我Is it possible to have a circular XOR linked list?看来，即使我们以某种方式构建这样一个列表，给定列表的头节点也不可能遍历它。例如 - 让链表包含 3 个节点：A、B 和 C。

由于我们得到head了列表，即A在这种情况下，我们将无法向前或向后移动，因为我们必须至少知道BorC之一才能移动。由于我们无法遍历它，因此我们也无法构建它。

我的想法正确吗？还是我错过了什么？

假设这是我的 XOR 链表结构......

如果异或链表的大小是 1 或 2应该xor包含什么？

在 Cormen 的作者之一的书中，异或链表存在一个有趣的问题。

我举了一个将项目添加到异或链表的例子。

我不明白这段代码

在我看来应该有类似的东西

谢谢你的好答案。抱歉我的愚蠢问题，为什么在第一行使用pNext-> ptrdiff（pNext->ptrdiff = pNext->ptrdiff XOR pCurrent XOR pNew 在此）。乍一看，似乎当pCurrent <====> pNew <====> pNext <====> (NextNode to pNext)pCurrent 与pNext-> ptrdiff.

我为异或链表编写代码。我有一个函数，我得到一个指针，使用属性 C.link = A XOR B。这里是这个函数的代码

但最后得到一个分段错误。用 GDB 调试表明，这是因为return (Node<T>*)((int)prev ^ (int)curr->np); 变量中的行这样的值

在异或的最后

在我看来，没有有效的指针，因此它遵循分段错误。我该如何解决？谢谢

Тhe 问题解决了。问题出在赋值运算符中

我删除了这两行，问题就消失了。

主程序称为赋值运算符，将旧对象的头部和尾部值分配给新对象。

In Data Structures and Algorithms Made Easy, struct of memory efficient memory list given as follows,

In ptrdiff, there will be xoring of previous and next node is done. For example, previous node have address 100 and next node address is 500.

So, in ptrdiff address will be 400. Now how it is possible to move to next or previous node (as we do in doubly link list), just by knowing xoring of their addresses?

Am I missing any step here?

所以我正在制作一个异或链表，每当我试图为新节点分配内存时，程序就会崩溃。这是我的插入功能代码：

这是 XORList 的定义：

这是 XORListNode 的定义：

我也很感激有关代码的任何其他评论，因为我还没有使用指针的经验。

感谢您的帮助。