最近,我读过一篇文章,向我展示了如何使用单个指针字段实现双向链表,即像单个链表一样.与在单个字段中存储XOR prev和下一个地址有关.我不知道这有助于我们前后横穿？谁可以给我解释一下这个？我已经阅读了
here以上的文章.任何人都可以向我解释这个吗？更详细一点？ XOR如何与这些地址有关.
解决方法
正如文章所指出的,只有当你在列表的头部或尾部有一个指针时,这种技术才有用.如果你只有一个指针在列表中间,那么无处可去.
关于技术：考虑以下链表：
|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
}
您使用相同的逻辑在列表中向后移动
