如何在 Python 中实现 XOR 链表？

Question

鉴于python对象只是对实际内存对象的引用，并且无法检索对象的内存地址。

是否可以在 Python 中实现 XOR 链表？如果是怎么办？

Answer 1

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

无论如何，您都不想实现它——这是一个肮脏的技巧，它使您的代码难以理解，而且收益甚微。

如果您担心内存，那么使用每个节点超过 1 个元素的双向链表几乎总是更好，例如数组的链表。

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

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

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