Circular XOR linked list?

Question

I was reading about XOR linked list and one question came to my mind that Is it possible to have a circular XOR linked list? It seems to me that even if we somehow build such a list, it would be impossible to traverse it given head node of the list. For e.g - Let the linked list contain 3 nodes: A, B and C.

|
v
A ---> B ---> C

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

Since we are given head of the list i.e A in this case, we will not be able to either move forward or backward, as we have to know at-least one of the B or C in order to move. Since we cannot traverse it, we can't build it too.

Am I correct in what I am thinking? Or am I missing something?

Answer 1

Indeed you are right, it is impossible to traverse this list since we cannot retrieve any pointer value from the xor link.

The minimal requirement for this list to become traversable is two pieces of information … for instance the pointer to the current node, and a pointer to the next (or previous) node. Then you can retrieve all the information from the xor link.

In fact, this is what the Wikipedia article says anyway:

To start traversing the list in either direction from some point, you need the address of two consecutive items, not just one

This is still cheaper than storing two pointers for each node since we only need one link per node, plus two pointers for the current and next (or previous) node.

Answer 2

This was fun! I wrote a little circular XOR linked list program as a proof of concept that it is possible. The edge cases of 1 and 2 nodes are a little weird but everything else checks out as long as you keep track of the head and tail pointers somewhere. (Also I know this is a 7 year old thread, but I had the same question and found this as pretty much the only mention of a circular XOR linked list)

#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

It is impossible to traverse the list with one value, but it is possible to find all traversals that would work, in this case we find all b's and c's that can traverse the tree:

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

To traverse an XOR list you need a pointer to a node and to its "parent" (preceding node) or "child" (succeeding node). The pointer to the parent of the first node of a non-circular XOR list can be arbitrary (NULL) and the pointer to the child of the last node can also be set to NULL, so you can traverse a non-circular XOR list knowing just the pointer to the first or the last node, but the first node of a circular XOR list has the last node as parent and is the child of the last node, therefore you need pointers to 2 (parent and child) nodes in order to traverse a circular XOR list. Think of the linked-list as a degenerate tree.