Re: LinkedList - Mailing list pgsql-sql

On Thu, 2006-27-04 at 22:58 -0500, Ben K. wrote:
> > I have a table that I created that implements a linked list.  I am not an
> > expert SQL developer and was wondering if there are known ways to traverse
> > the linked lists.  Any information that can point me in the direction to
> > figure this out would be appreciated.  The table contains many linked lists
> > based upon the head of the list and I need to extract all of the nodes that
> > make up a list.  The lists are simple with a item and a link to the history
> > item so it goes kind of like:
> 
> It may not be exactly suitable, but this one does only traversal (assuming 
> the list is not clsoed)
> 
> create table linkedlist(prevnode int, nextnode int, val int);
> -- 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);
> 
> -- TRAVERSE
> begin;
> declare mc cursor for select * from linkedlist order by nextnode;
> fetch 1 from mc;
> fetch 1 from mc;
> ...
> close mc;
> commit;
> 
> which is nothing more than,
> select * from linkedlist order by nextnode;
> 
> 
> Regards,
> 
> Ben K.
> Developer
> http://benix.tamu.edu

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.

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.

BEGIN
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';
COMMIT

I have never done linked lists in SQL but have done a lot of
work with bidirectional multi-dimensional linked lists in the 
past in C and other programming languages. The concept is the 
same.

A single linked list would be easier, but can only be traversed 
in one direction :

create table linkedlist(node int,nextnode int, val int);

insert into linkedlist values(1,2,0);
insert into linkedlist values(2,3,10);
insert into linkedlist values(3,4,30);
insert into linkedlist values(4,5,20);
insert into linkedlist values(5,6,40);
insert into linkedlist values(6,null,50);

Again to order the val from head to tail:

BEGIN
update linkedlist set nextnode = '3' where node = '4';
update linkedlist set nextnode = '4' where node = '2';
COMMIT