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 [EMAIL PROTECTED] | (610) 359-1001 + If your life is a hard drive, | 13 Roberts Road + Christ can be your backup. | Newtown Square, Pennsylvania 19073 ---------------------------(end of broadcast)--------------------------- TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]