异或链表的目的？

Question

我偶然发现了一篇关于Xor 链表的维基百科文章，这是一个有趣的琐事，但该文章似乎暗示它偶尔会在实际代码中使用。我很好奇它有什么用处，因为我不明白为什么它即使在内存/缓存严重受限的系统中也有意义：

• 常规双向链表的主要优点是能够从列表中间插入或删除元素，只需提供指向要删除/插入的节点的指针。这不能通过异或链表来完成。
• 如果需要在迭代时进行 O(1) 预置或 O(1) 插入/删除，那么单链表就足够了，并且可以避免大量代码复杂性以及垃圾收集、调试工具等方面的注意事项。
• 如果不需要 O(1) 预置/插入/删除，那么使用数组在空间和时间上可能更有效。即使在迭代时只需要高效的插入/删除，数组也可能非常好，因为可以在迭代时完成插入/删除。

考虑到上述情况，有什么意义呢？是否存在任何奇怪的极端情况，异或链接列表实际上是值得的？

Answer 1

除了节省内存之外，它还允许 O(1) 反转，同时仍然有效地支持所有其他破坏性更新操作，例如

• concat破坏性地计算两个列表的时间复杂度为 O(1)
• insertAfter/insertBefore在 O(1) 中，当您只有对节点及其后继/前驱的引用时（这与标准双向链表略有不同）
• remove在 O(1) 中，还引用后继者或前驱者。

我认为内存方面并不真正重要，因为对于大多数可能使用 XOR 列表的情况，您可以使用单链表代替。