From: Ben K. <bkim@coe.tamu.edu>
To: Guy Fraser <guy@incentre.net>
Cc: pgsql-sql@postgresql.org
Subject: Re: LinkedList
Date: Sat, 29 Apr 2006 01:50:49 -0500 (CDT)
Message-ID: <Pine.GSO.4.64.0604290027010.12166@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>
On Fri, 28 Apr 2006, Guy Fraser wrote:
>> -- HEAD
>> insert into linkedlist values(null,1,0);
>> insert into linkedlist values(1,2,10);
>> insert into linkedlist values(2,3,20);
>> insert into linkedlist values(3,4,30);
>> insert into linkedlist values(4,5,40);
>> -- TAIL
>> insert into linkedlist values(5,null,50);
> Bad example of a double linked list, you also need an id for
> the current node and the values of prevnode and nextnode do not
> need to be ordered or contiguous as the example shows.
Wow. Interesting... I am willing to be corrected, but to me the "node"
field seems redundant, since it does not add any information. (Since each
item in the list is already uniquely identifiable without the "node".)
Certainly so, for traversing, which was the OP's intention.
It may save some steps in case of other operations but at the expense of
one more field. Please see below.
> create table linkedlist(node int,prevnode int, nextnode int, val int);
> insert into linkedlist values(1,null,2,0);
> insert into linkedlist values(2,1,3,10);
> insert into linkedlist values(3,2,4,30);
> insert into linkedlist values(4,3,5,20);
> insert into linkedlist values(5,4,6,40);
> insert into linkedlist values(6,5,null,50);
> If we now wanted to reorder an item in the set you need
> make some updates in a block, which I have not done before
> but should be something like this:
>
> Move node 4 between 2 and 3 so that the values from head
> to tail are ordered.
>
> update linkedlist set prevnode = '2',nextnode = '3' where node = '4';
> update linkedlist set nextnode = '4' where node = '2';
> update linkedlist set prevnode = '4' where node = '3';
If the intention is to change it from 0-10-30-20-40-50 to
0-10-20-30-40-50, it would have been (in my design) exchanging node 3 and
node 4 below.
null,1,0
1,2,10 <-- node 2
2,3,30 <-- node 3
3,4,20 <-- node 4
4,5,40
5,null,50
Now, it can be done by:
begin;
update linkedlist set prevnode=2 where prevnode=3; -- node 4 = (2,4,20)
update linkedlist set prevnode=3 where nextnode=3; -- node 3 = (3,3,30)
update linkedlist set nextnode=3 where prevnode=2; -- node 4 = (2,3,20)
update linkedlist set nextnode=4 where nextnode=3; -- node 3 = (3,4,30)
commit;
achieving the same.
...
2,3,20 <-- node 4, originally
3,4,30 <-- node 3, originally
...
"node" will be more cost efficient if we insert an item at the beginning
of a long list, for example insert
(2,3,100)
before node 3 (2,3,20), but at least the sql is simple;
update linkedlist set prevnode = prevnode + 1 where prevnode > 1;
update linkedlist set nextnode = nextnode + 1 where nextnode > 2;
and then do insert (2,3,xxx)
This method can also be used for reordering.
The usefulness of the "node" will depend on the economics of these update
operations over keeping one more field.
But I think this is more of an exercise, and functions would be the proper
way for complex operations.
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.0604290027010.12166@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