From: Ben K. <bkim@coe.tamu.edu>
To: Guy Fraser <guy@incentre.net>
Cc: pgsql-sql@postgresql.org
Subject: Re: LinkedList
Date: Wed, 3 May 2006 00:14:04 -0500 (CDT)
Message-ID: <Pine.GSO.4.64.0605022332320.18622@coe.tamu.edu> (raw)
In-Reply-To: <1146239551.12641.210.camel@sigurd.incentre.net>
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>
> 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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: bkim@coe.tamu.edu, guy@incentre.net
Subject: Re: LinkedList
In-Reply-To: <Pine.GSO.4.64.0605022332320.18622@coe.tamu.edu>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox