data-structures - 理解异或链表的问题

Question

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

我没有得到以下段落。

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.

我有几个问题:

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?

Answer 1

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

2. 取决于您使用的语言。用你使用的任何语言研究按位运算，你应该能够很快弄清楚。

3. 它可以在任何使用双链表的地方使用(异或链表会节省内存)。需要注意的是，您必须有两个连续的列表元素才能遍历这些元素。