理解XOR链表时出现问题

Question

我正在阅读 XOR链表(来自维基百科).但我在理解它时遇到了一些问题.

我没有得到以下段落.

要从某个点开始遍历任一方向的列表,您需要两个连续项的地址,而不仅仅是一个.如果两个连续项目的地址相反,您将最终以相反的方向遍历列表.

我对此几乎没有疑问:

1. 它是如何(XOR链表本身)实际工作的？

   (如果你通过给出一些例子证明你的答案是合理的.通过取一些地址然后做相应的计算.)

2. 我该如何实现它？关于实施的简要概念.

3. 实际上它在哪里或可以使用？看起来真的有用吗？

Answer 1

1. 上述过程的工作原理是将下一个和前一个元素的地址存储在一个字段中(我们称之为A).因此,要获取列表中下一个元素的值,您需要获取另一个元素的地址(这就是为什么需要两个元素...称之为B).要查找下一个元素的地址,只需要A XOR B即可获得C(下一个元素的位置).

2. 取决于您使用的语言.研究你正在使用的任何语言的按位运算,你应该能够很快找到它.

3. 它可以在任何使用双链表的地方使用(XOR链表将节省内存).需要注意的是,您必须使用列表中的两个连续元素来遍历元素.

Answer 2

这种链表现在不太实用.它的主要好处是节省内存,这通常是便宜和丰富的.您链接的维基百科文章非常清楚地说明了缺点:

这种形式的链表可能是不可取的:

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

计算机系统具有越来越便宜和丰富的存储器,并且存储开销通常不是专用嵌入式系统之外的最重要问题.在仍希望减少链表开销的情况下,展开提供了更实用的方法(以及其他优点,例如提高缓存性能和加速随机访问).