Implementing XOR linked list. Size 1 or 2

Question

Suppose this is my XOR linked list struct...

struct xList {
    int data;
    xList* xor;
}

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

Answer 1

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

It should contain prev ^ next where prev is a pointer to the previous element, next is a pointer to the next element, and ^ is the XOR operator. The first element in the list obviously has nil for the previous item, and the last item has nil for the last item, so you'd get nil ^ next and prev ^ nil for those elements, respectively. In a list of size 1, there's no previous or next element, so you can probably figure out what you'd store in the xor field.

The idea with an xor linked list is that you have to know the address of either the previous or next element in the list already in order to determine the next or previous element. That's no problem if you're iterating through the list, though, and since that's what you do with linked lists, it can be a useful optimization. If you're iterating from head to tail, for example, you start with a pointer to the first element in the list. The previous element is nil, so to get the next element you compute: next = prev ^ xor. You also have to remember the pointer to the current element before moving to the next element, so that you can use it to get to the following element.

Answer 2

You store (previous ^ next) in the xorlink pointer.

Consider

struct xList 
{
    int data;
    xList* xorlink;
}

A -> B -> C -> D

You start from the head. You know head doesn't have a previous - so xorlink will point to the B node. You save the current pointer(A) and move to next (B). You do (A ^ B->xorlink) to get the pointer to C. (B ^ C->xorlink) will give you the pointer to D. And so on

Reverse traversal is also similar.

Anyway, the answer to your question

1. If the size is 1, then the first node's xorlink should contain NULL.
2. If the size is 2, then the first node's xorlink should contain a pointer to 2nd node. The 2nd node's xorlink should contain a pointer to the 1st node.