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?
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.