3

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?
4

2 回答 2

5

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

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

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

于 2009-10-26T14:49:51.770 回答
5

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

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

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

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

于 2009-10-26T17:05:08.940 回答