In a book by one of the authors of which is the Cormen, there is an interesting problem of the xor linked list.
I took this one example of adding items to a xor linked list.
void insertAfter(plistNode pNew, T theElm)
{
plistNode pPrev, pCurrent, pNext;
pPrev = NULL;
pCurrent = pStart;
while (pCurrent) {
pNext = NextNode(pCurrent, pPrev);
if (pCurrent->elm == theElm) {
/* traversal is done */
if (pNext) {
/* fix the existing next node */
pNext->ptrdiff =
(plistNode) ((int) pNext->ptrdiff
^ (int) pCurrent
^ (int) pNew);
/* fix the current node */
pCurrent->ptrdiff =
(plistNode) ((int) pNew ^ (int) pNext
^ (int) pCurrent->ptrdiff);
/* fix the new node */
pNew->ptrdiff =
(plistNode) ((int) pCurrent
^ (int) pNext);
break;
}
pPrev = pCurrent;
pCurrent = pNext;
}
}
I do not understand this code
pNext-> ptrdiff = (plistNode) ((int) pNext-> ptrdiff
^ (Int) pCurrent
^ (Int) pNew);
In my opinion there should be something like
pNext-> ptrdiff = New Xor pNext[next]
Thanks for the good answer. Sorry for my silly question, why in the first line is used pNext-> ptrdiff
(pNext->ptrdiff = pNext->ptrdiff XOR pCurrent XOR pNew
in this). At first glance, it seems that when pCurrent <====> pNew <====> pNext <====> (NextNode to pNext)
pCurrent not related to pNext-> ptrdiff
.
XOR linked list logic for A<===>B<====>C
B should contain A XOR C
Now ,
1>earlier : pCurrent<====>pNext<====>(NextNode to pNext)
So , pNext->ptrdiff = pCurrent XOR (NextNode to pNext)
2>After inserting pNew after pCurrent, you should have :
pCurrent<====>pNew<====>pNext<====>(NextNode to pNext)
So,pNext->ptrdiff should be
pNext->ptrdiff = pNew XOR (NextNode to pNext)
So the code is achieving that with
pNext->ptrdiff = pNext->ptrdiff XOR pCurrent XOR pNew
= pCurrent XOR (NextNode to pNext) XOR pCurrent XOR pNew [ replaced pNext->ptrdiff from 1 ]
= pCurrent XOR pCurrent XOR (NextNode to pNext) XOR pNew [ XOR is commutative ]
= 0 XOR (NextNode to pNext) XOR pNew [ A XOR A = NULL ]
= (NextNode to pNext) XOR pNew [ 0 XOR A = A ]
This is what was expected [ from 2]