如何在Python中实现XOR链表？

Question

由于python对象只是对实际内存对象的引用，因此无法检索对象的内存地址。

可以在Python中实现XOR链表吗？如果是，是如何实现的？

Answer 1

你不能在Python中构建XOR链表，因为Python不允许你乱用指针中的位。

您无论如何都不想实现它--这是一个肮脏的把戏，它使您的代码难以理解，但却没有什么好处。

如果您担心内存问题，那么使用双链表(每个节点有超过1个元素)几乎总是更好的，就像数组的链表一样。

例如，XOR链表的成本为每个项目1个指针，加上项目本身，而每个节点16个项目的双向链表的成本为每16个项目3个指针，或每个项目3/16个指针。(额外的指针是记录节点中有多少项的整数的成本)小于1。在Python中有额外的开销，但它仍然工作得更好。

除了节省内存之外，您还可以在局部性方面获得优势，因为节点中的所有16个项目在内存中都是相邻的。遍历列表的算法会更快。

请注意，XOR链表还要求您在每次添加或删除节点时分配或释放内存，这是一个开销很大的操作。使用数组链表，您可以通过允许节点少于完全满来做得更好。例如，如果您允许5个空项插槽，那么在最坏的情况下，您只能在每次第三次插入或删除时分配或释放内存。