c - 实现异或链表。尺寸 1 或 2

Question

假设这是我的异或链表结构...

struct xList {    int data;    xList* xor;}

如果异或链接列表的大小为 1 或 2，xor 应该包含什么？

Answer 1

What should xor contain if the size of the xor linked list is 1 or 2?

它应该包含 prev ^ next 其中 prev 是指向上一个元素的指针，next 是指向下一个元素的指针，并且^ 是异或运算符。列表中的第一个元素显然具有 nil 表示前一项，最后一项具有 nil 表示最后一项，因此您将得到 nil ^ next 和 prev ^ nil 分别表示这些元素。在大小为 1 的列表中，没有上一个或下一个元素，因此您可能可以弄清楚要在 xor 字段中存储的内容。

异或链接列表的想法是，您必须知道列表中前一个或下一个元素的地址才能确定下一个或前一个元素。不过，如果您要迭代列表，那没有问题，并且由于这就是您对链接列表所做的操作，因此它可能是一种有用的优化。例如，如果您从头到尾进行迭代，则从指向列表中第一个元素的指针开始。前一个元素是nil，因此要获取下一个元素，您需要计算:next = prev ^ xor。在移动到下一个元素之前，您还必须记住指向当前元素的指针，以便您可以使用它来访问下一个元素。