循环异或链表

Question

我正在阅读有关XOR链表的文章，我想到了一个问题，Is it possible to have a circular XOR linked list? 在我看来，即使我们以某种方式构建了这样一个列表，也不可能遍历它，给定列表的头节点。例如 - 让链表包含 3 个节点：A、B 和 C。

|
v
A ---> B ---> C
A->xor = B ^ C
B->xor = A ^ C
C->xor = A ^ B

由于我们获得了列表的head，即在这种情况下A，我们将无法向前或向后移动，因为我们必须至少知道B或C中的一个才能移动。由于我们无法遍历它，因此我们也无法构建它。

我的想法正确吗？还是我错过了什么？

Answer 1

事实上你是对的，不可能遍历这个列表，因为我们无法从xor链接中检索任何指针值。

此列表可遍历的最低要求是两条信息......例如，指向当前节点的指针，以及指向下一个（或上一个）节点的指针。然后，您可以从xor链接中检索所有信息。

事实上，无论如何，维基百科文章都是这么说的：

要从某个点开始向任一方向遍历列表，您需要两个连续项目的地址，而不仅仅是一个

这仍然比为每个节点存储两个指针便宜，因为我们只需要每个节点一个链接，加上当前和下一个（或上一个）节点的两个指针。

Answer 2

这

很有趣！我写了一个小的循环XOR链表程序作为概念证明它是可能的。1 和 2 节点的边缘情况有点奇怪，但只要您跟踪某处的头尾指针，其他一切都会检查出来。（我也知道这是一个 7 年前的线程，但我有同样的问题，发现这几乎是唯一提到循环 XOR 链表）

#include <stdlib.h> // for malloc
#include <stdio.h>  // for printf
#include <stdint.h> // for uintptr_t
typedef struct  s_list  t_list;
struct s_list
{
    char        *data;  // Contains a string.
    struct s_list   *npx;   // npx = previous XOR next
};
t_list  *create_elem(char *data, t_list *npx)
{
    t_list  *ret;
    ret = malloc(sizeof(*ret));
    ret->data = data;
    ret->npx = npx;
    return (ret);
}
t_list  *xor(t_list *a, t_list *b)
{
    return (t_list*)((uintptr_t)a ^ (uintptr_t)b);
}
void    insert(t_list **h, t_list **t, char *data)
{
    t_list  *last = *t;
    t_list  *first = *h;
    t_list  *new, npx;
    if (!last && !first)  // No nodes, populate first node
    {
        new = create_elem(data, NULL);  // self XOR self == NULL
        *h = ((*t = new));
    }
    else if (last == first)  // Only one node, set tail properly
        *t = create_elem(data, NULL);   // self XOR self == NULL
    else  // Multiple nodes, do a real add
    {
        // Create an element with npx = first XOR last
        // (it will be inserted at the end of the list)
        new = create_elem(data, xor(first, last));
        // If head or tail's npx == 0, we know its a list of size 2,
        // so each prev and next pointer is the same.
        // So, if it is a list with size 2
        //  last->npx = new XOR first
        //  first->npx = new XOR last
        // else
        //  last->npx = new XOR (last->npx XOR first)
        //  first->npx = new XOR (first->npx XOR last)
        last->npx = xor(new, ((!last->npx || !first->npx) ?
                first : xor(last->npx, first)));
        first->npx = xor(new, ((!last->npx || !first->npx) ?
                last : xor(first->npx, last)));
        // Set the new pointers for passed addresses.
        *h = first;
        *t = new;
    }
}
int traverse(t_list *h, t_list *t)
{
    t_list  *cur = h;
    t_list  *last = t;
    t_list  *tmp;
    while (cur)
    {
        printf("[%s]n", cur->data);
        tmp = xor(cur->npx, last);
        last = cur;
        cur = tmp;
        if (cur == h)
            return (1);
    }
    return (1);
}
int main(void)
{
    char    s1[] = "Testing!";
    char    s2[] = "My!";
    char    s3[] = "Function!";
    char    s4[] = "For!";
    char    s5[] = "GeeksforGeeks!";
    // We need to keep track of head and tail pointers for
    // everything to work nicely.
    // Traversal will always require access to
    // two consecutive pointers.
    t_list  *head;
    t_list  *tail;
    head = NULL;
    tail = NULL;
    insert(&head, &tail, s1);
    insert(&head, &tail, s2);
    insert(&head, &tail, s3);
    insert(&head, &tail, s4);
    insert(&head, &tail, s5);
    traverse(head, tail);
}

Answer 3

不可能

用一个值遍历列表，但可以找到所有遍历将起作用，在这种情况下，我们找到所有可以遍历树的 B 和 C：

a=5
for b in range(0, 16): 
    print(a, b, a ^ b)
5 0 5
5 1 4
5 2 7
5 3 6
5 4 1
5 5 0
5 6 3
5 7 2
5 8 13
5 9 12
5 10 15
5 11 14
5 12 9
5 13 8
5 14 11
5 15 10

Answer 4

在非循环 XOR 列表中，first节点指针用于将节点附加到列表，last节点指针用于将节点追加到列表。我们可以遍历一个只有一个指针的非循环异或列表。但不是循环异或列表，其中first必须链接到last。因此，要从first或last节点遍历循环 XOR 列表并将节点添加到列表中，我们需要指向两者的指针。