仅使用单个指针字段存储双向链表

Question

最近,我读过一篇文章,向我展示了如何使用单个指针字段实现双向链表,即像单个链表一样.与将XOR prev和下一个地址存储在单个字段中有关.我不知道这有助于我们前后横穿？谁可以给我解释一下这个？我在这里读过这篇文章.任何人都可以向我解释这个吗？更详细一点？XOR如何与这些地址有关.

Answer 1

正如文章所指出的,只有当你在列表的头部或尾部有一个指针时,这种技术才有用.如果你只有一个指针在列表中间,那么无处可去.

关于技术:考虑以下链表:

|0|A|0x01|<->|0x01|B|0x02|<->|0x02|C|0|

该列表包含3个节点,其值为A,B,C和prev/next指针,其中包含列表中prev/next元素的十六进制值(地址).值0为空

如果存储2个指针,我们只能使用一个,如文章中所述:

|A|0x01|<->|B|0x03|<->|C|0x03| 

我们接下来将调用新字段link = prev XOR.所以考虑到这一点:

    A.link = 0^0x01 = 0x01
    B.link = 0x01^0x02 = 0x03
    C.link = 0x03^0x0 = 0x03. 

假设你有一个指向列表头部的指针(你知道将prev指针设置为null),这里是你如何遍历列表:

 p=head; 
 prev = 0;
 while(p.link!=prev)
 {
   next = p.link^prev
   prev=p
   p=next 
 }

您使用相同的逻辑在列表中向后移动