Date: Wed, 3 May 2006 00:14:04 -0500 (CDT)
From: "Ben K." <bkim@coe.tamu.edu>
To: Guy Fraser <guy@incentre.net>
cc: pgsql-sql@postgresql.org
Subject: Re: LinkedList
In-Reply-To: <1146239551.12641.210.camel@sigurd.incentre.net>
Message-ID: <Pine.GSO.4.64.0605022332320.18622@coe.tamu.edu>
References: <IEELLOAPJFACBDBGELGHIEKMEDAA.ray@madigans.org>
	<1146067158.23538.264.camel@state.g2switchworks.com>
	<Pine.GSO.4.64.0604272249570.3093@coe.tamu.edu>
	<1146239551.12641.210.camel@sigurd.incentre.net>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
Received-SPF: pass (smtp-relay.tamu.edu: 165.91.232.6 is authenticated by a
	trusted mechanism)

> The problem is that your way, there is no indicated way to determine
> which node is which. For instance is you update any of your nodes
> then the node list would be out of order and your list would not
> work.

I think the thinking is different here. The OP's list is ordered and has 
prev-next only, and there can be lists that are read only and/or ordered 
(like clickstream or a data stream out of multi-stream packets) and do not 
require insert. That's why I mentioned it's for traverse-only in my 
original post.

(But I disagree with you about not being able to determine a node - since 
in sql it's possible to identify a row as long as it has unique values in 
fields, however they are named)

> After I posted the message I realized there is another way to
> do this without adding an extra field, and it would be a closer
> example to how it is done in C. If you assigned the OID of the
> previous and next nodes rather than arbitrary integer, you could
> access each node independent of the order they are listed.
> 
> I have not messed around much with OIDs. I am not sure if
> OIDs change if an entry is updated.

I understand oid doesn't change with update. But tables may or may not 
have oids. (can be created "without oids") I also came to appreciate the 
difference with C.

In sql, there is a way to identify a row like I did, but in C it'd not be 
possible without the address (of course it's not like "impossible" but 
...), so the linked list as in strict C-like sense would be perfect but 
may carry a different value here. (Since we already have the added layer 
of sql engines.) I agree your method would be better if we want to scale 
when insert or delete is needed.

It'd be interesting to compare how the normal O() applies to sql - would 
updating n rows with one sql statement be equivalent to O(n) in C? Maybe a 
silly question but it came to my mind...

> In C you would use a pointer to storage location of previous
> and next "node" which is similar to using the OID. In some
> cases it can be necessary to use pointers to pointers when
> accessing variable length relocatable data, but that goes way
> past what this thread is about.
> The example I provided, is still feasible and alleviates all
> unknowns at the expense of 4 bytes of storage for one integer
> used as a fixed address for each node.

> As long as it works in real world use. Without some way of addressing
> each node, the idea of a linked list seems wrong, since a linked is
> supposed to hold the address of the previous and or next item in the
> list, assuming the data is always going to be correctly sorted so that
> you can locate the next item by tupple number seems overly assumptive.
> If it works for you great, your example may then be useful as a short
> cut, but I don't believe in leaving things to chance when programming.


Regards,

Ben K.
Developer
http://benix.tamu.edu