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
=========================================================================
In this way we are going to save a pointer for each node,
what do you think ?
Regards
Gaetano Mendola