XOR双向链表

时间：2024-06-09 19:04:56

这是一个数据结构。利用计算机的的位异或操作(⊕)，来降低双向链表的存储需求。

...  A       B         C         D         E  ...

          –>  next –>  next  –>  next  –>

          <–  prev <–  prev  <–  prev  <–
双向链表如上面所示，每个节点有两个指针，分别指向该节点的前驱和后继。
而XOR链表如下面所示：An XOR linked list compresses the same information into one address field by storing the bitwise XOR of the address for previous and the address for next in one field:
 ...  A        B         C         D         E  ...

         <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->
 link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), ..
要求addr(D)，使用:addr(D) = link(C) ⊕ addr(B)
地址指针中存放的地址的异或。 比如B中就存放了A⊕C的值。
这样从头开始便利时，我们需要知道开始的两个节点（而不像普通链表只需要一个）。
这样比如知道了节点A和节点B 我们就可以用节点A的地址和B中的A⊕C 结合运算，得到A⊕A⊕C 得到C。 这是正向遍历
反向遍历时类似，比如知道了节点E和D，就可以利用E的地址和D中的C⊕E 运算，得到C⊕E⊕E 得到C.

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.

This form of linked list may be inadvisable: 异或链表不推荐使用：

  • General-purpose debugging tools cannot follow the XOR chain, making debugging more difficult; [1]
  • The price for the decrease in memory usage is an increase in code complexity, making maintenance more expensive; 虽然内存使用减少了，但代码复杂量增加了，使维护更加昂贵。
  • Most garbage collection schemes do not work with data structures that do not contain literal pointers;通常的垃圾回收机制对于这种表示无法正常工作
  • XOR of pointers is not defined in some contexts (e.g., the C language), although many languages provide some kind of type conversion between pointers and integers;
  • The pointers will be unreadable if one isn't traversing the list — for example, if the pointer to a list item was contained in another data structure;不是在遍历链表时，指针是无意义的。例如另外的数据结构也包含了链表中的指针。
  • While traversing the list you need to remember the address of the previously accessed node in order to calculate the next node's address.
  • XOR linked lists do not provide some of the important advantages of doubly-linked lists, such as the ability to delete a node from the list knowing only its address or the ability to insert a new node before or after an existing node when knowing only the address of the existing node.XOR链表也无法提供双向链表提供的一些功能。比如仅知道一个节点是将该节点从链表移除或者在仅知道一个节点时再该节点后面插入一个节点。

Computer systems have increasingly cheap and plentiful memory, and storage overhead is not generally an overriding issue outside specialized embedded systems. Where it is still desirable to reduce the overhead of a linked list, unrolling provides a more practical approach (as well as other advantages, such as increasing cache performance and speeding random access).

实现代码：http://blog.wsensors.com/2011/04/the-xor-linked-list-in-c/

类似的变形

加法链表：放地址的和

 ...  A        B         C         D         E  ...

         <–>  A+C  <->  B+D  <->  C+E  <->
减法链表：放地址的差
...  A        B         C         D         E  ...

         <–>  C-A  <->  D-B  <->  E-C  <->
不同是正向和反向需要做不同的运算。

参考：http://en.wikipedia.org/wiki/XOR_linked_list

相关文章