xor linked list
 

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

Re: xor linked list
 

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.

Re: xor linked list
 

"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 <->

"

Re: xor linked list
 

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;

        }

Re: xor linked list
 

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

Re: xor linked list
 

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

Re: xor linked list
 

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

Re: xor linked list
 

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.

Re: xor linked list
 

[QUOTE=Ptolemy;457374]>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?

Re: xor linked list
 

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