algorithmxorxor-linkedlist

How to add an item to xor linked list?


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.


Solution

  • 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]