Fwd: Double linked list with one pointer [mendola@bigfoot.com]

I could see how this would work if you always had a reference to one of the nodes.

The problem with the approach I can see is that you *have* to always know the value of at least one pointer, and maintaining that will ultimately require more coding than just having two pointers.
Assume CurrentNode is a pointer to on element in the list:

CurrentNode = <some node in the list> // This node knows what one of the pointers is.
List *TempNode = CurrentNode // This node does not know what one of the pointers is because it was never told.

So, TempNode can't traverse the list. Like I say, passing the known pointer value around would take more coding than maintaining two pointers in the list.

Richard Schilling

----- Begin Forwarded Message -----
Date: 2003.12.06 08:03
Subject: [HACKERS] Double linked list with one pointer
From: Gaetano Mendola <mendola(at)bigfoot(dot)com>
To: "pgsql-hackers(at)postgresql(dot)org" <pgsql-hackers(at)postgresql(dot)org>
Message-ID: <3FD1FDE4(dot)9070503(at)bigfoot(dot)com>

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
----- End Forwarded Message -----