Gaetano Mendola wrote:
> If I'm not wrong Neil Conway is working on
> reimplement a double linked list.
> Looking around I found this post of
> "Herb Sutter" on comp.lang.c++:
>
> ========================================================================
> In particular, a motivation behind two-way pointers is that you
> can have a more space-efficient doubly linked list if you store only one
> (not two) pointer's worth of storage in each node. But how can the list
> still be traversable in both directions? The idea is that each node
> stores, not a pointer to one other node, but a pointer to the previous
> node XOR'd with a pointer to the next node. To traverse the list in either
> direction, at each node you get a pointer to the next node by simply
> XORing the current node's two-way pointer value with the address of the
> last node you visited, which yields the address of the next node you want
> to visit. For more details, see:
>
> "Running Circles Round You, Logically"
> by Steve Dewhurst
> C/C++ Users Journal (20, 6), June 2002
>
> I don't think the article is available online, alas, but you can find some
> related source code demonstrating the technique at:
>
> http://www.semantics.org/tyr/tyr0_5/list.h
That certainly is an amazing idea. You know the pointer you are coming
from so you can XOR to find the next pointer.
I agree with a Tom that we don't have much use for double-link lists,
but is a nice idea.
-- Bruce Momjian | http://candle.pha.pa.us pgman@candle.pha.pa.us | (610)
359-1001+ If your life is a hard drive, | 13 Roberts Road + Christ can be your backup. | Newtown Square,
Pennsylvania19073