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

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

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

总结

以上是内存溢出为你收集整理的c – 仅使用单个指针字段存储双向链表全部内容，希望文章能够帮你解决c – 仅使用单个指针字段存储双向链表所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。