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
---------------------------(end of broadcast)--------------------------- TIP 7: don't forget to increase your free space map settings
