理解XOR链表时出现问题

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

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

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

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

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

通用调试工具不能遵循XOR链,使调试更加困难;

内存使用量减少的代价是代码复杂性的增加,使维护成本更高;

大多数垃圾收集方案不适用于不包含文字指针的数据结构;

指针的异或未在某些上下文中定义(例如,C语言),尽管许多语言在指针和整数之间提供某种类型的转换;

如果没有遍历列表,则指针将是不可读的 - 例如,如果指向列表项的指针包含在另一个数据结构中;

在遍历列表时,您需要记住先前访问的节点的地址,以便计算下一个节点的地址.

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