XOR 链表 – 内存高效的双向链表(二)-原理讲解及C++/Python/JAVA等实现源码

在上一篇文章中，我们讨论了如何使用每个节点的地址字段仅使用一个空间来创建双向链接。在这篇文章中，我们将讨论内存高效的双向链表的实现。我们主要讨论以下两个简单的功能。

1. 在开头插入新节点的函数。
2. 向前遍历列表的函数。

在以下代码中，insert()函数在开头插入一个新节点。我们将每个节点的下一个和前一个节点的 XOR 存储起来，我们将其称为 npx，这是每个节点拥有的唯一地址成员。当我们在开头插入一个新节点时，新节点的npx将始终是NULL和当前头的异或。并且当前头的npx必须改为新节点与当前头的下一个节点的XOR。
printList()向前遍历列表。它打印每个节点的数据值。为了遍历列表，我们需要在每个点获取指向下一个节点的指针。我们可以通过跟踪当前节点和前一个节点来获取下一个节点的地址。如果我们对 curr->npx 和 prev 进行异或，我们就得到下一个节点的地址。