最近，我读了一篇文章，向我展示了如何实现一个只有一个指针字段的双向链表，即，像一个单链表。与将 XOR prev 和 next 地址存储在单个字段中有关。我不明白这如何帮助我们前后遍历？谁可以给我解释一下这个？我已经阅读了这篇文章 here .谁能给我解释一下？更详细一点？以及异或与这些地址有什么关系。
最佳答案
正如文章所指出的，只有在列表的头部或尾部有一个指针时，这种技术才有用；如果列表中间只有一个指针，则无处可去。
关于该技术:考虑以下链表:
|0|A|0x01|<->|0x01|B|0x02|<->|0x02|C|0|
该列表包含 3 个节点，其值为 A、B、C 和包含列表中上一个/下一个元素的十六进制值(地址)的上一个/下一个指针。值 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 指针设置为空)，下面是您如何遍历列表:
p=head;
prev = 0;
while(p.link!=prev)
{
next = p.link^prev
prev=p
p=next
}
您使用相同的逻辑在列表中向后移动
关于c - 仅使用单个指针字段存储双向链表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21528422/