Very interesting.

It seems that you'd have to have a pointer to the current address, and
the address of either the next item in the list or the previous item in
the list.  The current item will contain the xor of the previous and
next pointers, and since you know one of them you can get the other.

What you are doing, in essence, is trading space (eliminating another
pointer sized word in each data structure) for a smaller space (keeping
another pointer size word in code) and code (since you now have to
execute another instruction to get the other pointer.

This has other interesting uses as well.  If you don't want to keep
track of where you're at in the linked list, you can loop it, and zoom
around in whatever direction you're pointed in.

Inserting another item between two established items requires the same
amount if work as well.  Very interesting.

It would drive someone else crazy, trying to read the code and figure
out what the heck the previous programmer was smoking...  ;-)

-Adam

Bob Ammerman wrote:

>One of the neatest XOR tricks I ever saw was a way to build a doubly-linked
>list using only one pointer-sized word in each data structure.
>
>Anyone care to guess how it worked?
>
>
>Bob Ammerman
>RAm Systems
>
>--
>http://www.piclist.com hint: PICList Posts must start with ONE topic:
>[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads
>
>
>
>
>

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads