xor linked list

[phoenixlsk]

hi i need some help.
i have to do a linked list using XOR and i don't know how to do it.
thanks

[twomers]

Please elaborate. A linked list I can understand. Exclusive or I can understanc. Doing a linked list using XOR ... I'm not certain what you mean.

[phoenixlsk]

"XOR linked lists are a curious use of the bitwise exclusive disjunction (XOR) operation, here denoted by ⊕, to decrease storage requirements for doubly-linked lists. An ordinary doubly-linked list stores addresses of the previous and next list items in each list node, requiring two address fields:
... A B C D E ...
<– prev <– prev <– prev <–
–> next –> next –> next –>

An XOR linked list compresses the same information into one address field by storing the bitwise XOR of the address for previous and the address for next in one field:

... A B C D E ...
<–> A⊕C <-> B⊕D <-> C⊕E <->

"

[phoenixlsk]

i found something but it has an error :"xor1001.cpp invalid conversion from `void*' to `link*' ".
and i don't really understand the program

#include <stdio.h>
        #include <stdlib.h>
        #include <assert.h>

        /* pray that a long is the size of a pointer */
        typedef unsigned long pointer;

        typedef struct
        {
          pointer next_prev;
          int payload;
        } link;

        link* add_data(int payload, link* list)
        {
          link *new_link = malloc(sizeof(link));
          assert(new_link);
          new_link->next_prev = (pointer)list;
          new_link->payload = payload;
          if (list != NULL)
            list->next_prev ^= (pointer)new_link;
          return new_link;
        }

        void walk_list(link *list)
        {
          pointer prev = 0;
          while (list != NULL)
          {
            pointer next = prev ^ list->next_prev;
            printf("%d ", list->payload);
            prev = (pointer)list;
            list = (link*)next;
          }
          printf("\n");
        }

        int main(void)
        {
          /* create a list */
          link *l2 = add_data(2, NULL);
          /* add something to the front ... */
          link *l1 = add_data(1, l2);
          /* add something to the back ... */
          link *l3 = add_data(3, l2);

          /* walk from front to back */
          walk_list(l1);
          /* walk from back to front */
          walk_list(l3);

          return 0;
        }

[Ptolemy]

>Doing a linked list using XOR ... I'm not certain what you mean.
It's a hack to avoid wasting extra space on links. It takes advantage of the butterfly effect using XOR. If you take the XOR of two values and XOR it with either value, you get the other value:

123 XOR 456 = 435 (butterfly radix)

435 XOR 123 = 456
435 XOR 456 = 123

They're obscure, the logic is complex, and the result is far less flexible than a traditional linked list. If you're so pressed for space that you're willing to add this kind of complexity to the implementation, you should find a more suitable data structure.

[twomers]

First things first. Do you know how to write a regular linked list?

[Ptolemy]

>i found something but it has an error :"xor1001.cpp
>invalid conversion from `void*' to `link*' ".
You're compiling C as C++. C++ doesn't support implicit pointer conversions to and from void*. You have to add casts.

>and i don't really understand the program
If you understood it, you could have written it yourself. :) Try to run through the logic and figure it out. The program is tiny and bare bones. You're not going to find a simpler implementation.

[twomers]

Thanks for the explanation, Ptolemy. I hadn't heard of them before. Sounds like fun to implement. I can only assume that one uses the 'boundrary conditions' (ie start and end nodes where previous and next respectively will be NULL), to extract the next and previous addresses of all the other elements. Would be a bit more painful if it was a completely cyclic list though.

I glossed over your explanation, sorry. I assumed you were explaining XOR to me :) Makes sense.

[phoenixlsk]

>i found something but it has an error :"xor1001.cpp
>invalid conversion from `void*' to `link*' ".
You're compiling C as C++. C++ doesn't support implicit pointer conversions to and from void*. You have to add casts.

but don't know how to use cast. can you help me?

[twomers]

Put (int*) before the error area.
Or look up some C++ casts.

[Ptolemy]

>but don't know how to use cast. can you help me?
That's something that any C++ book or reference will tell you how to use. It would be "cast" or "type cast" in the index.

[phoenixlsk]

thank you
:-)

[WaltP]

Try reading some of the sticky posts that are labels Read Me: to learn good posting techniques...

[manojthesingham]

class xll
{
public:
int data;
unsigned long link;
};

class xlist
{
xll *head,*tail;
xlist(){head = NULL;tail = NULL}
void insert(int);
};
void xlist :: insert (int ele)
{
xll *node = (xll*) malloc (sizeof(xll));
node->data = ele;
xll *temp = head,*prev = NULL;
while(temp != NULL)
{
next = (xll *) (temp->link ^ (unsigned long) prev);
prev = temp;
temp = next;
}
if(prev == NULL)
head = node;
else
{
node->link ^= (unsigned long) prev ^ (unsigned long) temp;
prev->link ^= (unsigned long) temp ^ (unsigned long) node;
temp->link ^= (unsigned long) prev ^ (unsigned long) node;
}
}