Thread: LinkedList

LinkedList

From
"Ray Madigan"
Date:
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:

1, 0
3, 1
7, 3
9, 7
...

Any suggestions would be helpful, or I will have to implement the table
differently.

Thanks
Ray Madigan



Re: LinkedList

From
Scott Marlowe
Date:
On Wed, 2006-04-26 at 11:09, Ray Madigan 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:
> 
> 1, 0
> 3, 1
> 7, 3
> 9, 7
> ...
> 
> Any suggestions would be helpful, or I will have to implement the table
> differently.

You should be able to do this with a fairly simple self-join...

select a.id, b.aid, a.field1, b.field1 
from mytable a
join mytable b
on (a.id=b.aid)

Or something like that.


Re: LinkedList

From
"Ray Madigan"
Date:
Scott,

Thanks for your reply,  I tried what you said, worked around a few things
but I am still stuck.  The main reason is I didn't do an adequate job of
explaining the situation.  The table implements many linked lists and I want
to traverse one of them given the end of the list.

Say the table contains

h | v | j
1   0   100
3   1   300
5   3   500
7   5   700

2   0   200
4   2   400
6   4   600
8   6   800

If I specify t.h = 8 I want to traverse the even part of the table
If I specify t.h = 7 I want to traverse the odd part of the table

If you can send me to a book to read I am willing

Thanks

-----Original Message-----
From: pgsql-sql-owner@postgresql.org
[mailto:pgsql-sql-owner@postgresql.org]On Behalf Of Scott Marlowe
Sent: Wednesday, April 26, 2006 8:59 AM
To: Ray Madigan
Cc: pgsql-sql@postgresql.org
Subject: Re: [SQL] LinkedList


On Wed, 2006-04-26 at 11:09, Ray Madigan 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:
>
> 1, 0
> 3, 1
> 7, 3
> 9, 7
> ...
>
> Any suggestions would be helpful, or I will have to implement the table
> differently.

You should be able to do this with a fairly simple self-join...

select a.id, b.aid, a.field1, b.field1
from mytable a
join mytable b
on (a.id=b.aid)

Or something like that.

---------------------------(end of broadcast)---------------------------
TIP 2: Don't 'kill -9' the postmaster



Re: LinkedList

From
"Jim C. Nasby"
Date:
decibel=# select * from t;a | b 
---+---1 | 03 | 15 | 37 | 52 | 04 | 26 | 48 | 6
(8 rows)

decibel=# select * from t x join t y on(x.a=y.b) where y.a=7;a | b | a | b 
---+---+---+---5 | 3 | 7 | 5
(1 row)

decibel=# select * from t x join t y on(x.a=y.b) where y.a=8;a | b | a | b 
---+---+---+---6 | 4 | 8 | 6
(1 row)

decibel=#

As you can see, it selects the right data, but you'll need to step
through it somehow. You might be able to do it with a generate_series(),
or you can use a function. If we get WITH support/recursion in 8.2 you'd
use that.

I think that "SQL For Smarties" by Joe Celko might have an example of
how to do this without using a function. Even if it doesn't it's a book
any serious database developer should own.

On Wed, Apr 26, 2006 at 10:35:15AM -0700, Ray Madigan wrote:
> Scott,
> 
> Thanks for your reply,  I tried what you said, worked around a few things
> but I am still stuck.  The main reason is I didn't do an adequate job of
> explaining the situation.  The table implements many linked lists and I want
> to traverse one of them given the end of the list.
> 
> Say the table contains
> 
> h | v | j
> 1   0   100
> 3   1   300
> 5   3   500
> 7   5   700
> 
> 2   0   200
> 4   2   400
> 6   4   600
> 8   6   800
> 
> If I specify t.h = 8 I want to traverse the even part of the table
> If I specify t.h = 7 I want to traverse the odd part of the table
> 
> If you can send me to a book to read I am willing
> 
> Thanks
> 
> -----Original Message-----
> From: pgsql-sql-owner@postgresql.org
> [mailto:pgsql-sql-owner@postgresql.org]On Behalf Of Scott Marlowe
> Sent: Wednesday, April 26, 2006 8:59 AM
> To: Ray Madigan
> Cc: pgsql-sql@postgresql.org
> Subject: Re: [SQL] LinkedList
> 
> 
> On Wed, 2006-04-26 at 11:09, Ray Madigan 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:
> >
> > 1, 0
> > 3, 1
> > 7, 3
> > 9, 7
> > ...
> >
> > Any suggestions would be helpful, or I will have to implement the table
> > differently.
> 
> You should be able to do this with a fairly simple self-join...
> 
> select a.id, b.aid, a.field1, b.field1
> from mytable a
> join mytable b
> on (a.id=b.aid)
> 
> Or something like that.
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 2: Don't 'kill -9' the postmaster
> 
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 6: explain analyze is your friend
> 

-- 
Jim C. Nasby, Sr. Engineering Consultant      jnasby@pervasive.com
Pervasive Software      http://pervasive.com    work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf       cell: 512-569-9461


Re: LinkedList

From
"Neil Saunders"
Date:
Ray,

There's a good introductory article on Sitepoint for doing this kind of thing:

http://www.sitepoint.com/article/hierarchical-data-database

The "Modified Preorder Tree Traversal" is quite a nice method that I
would expect  to be a magnitude faster than recursive joins, although
does have some drawbacks.

Kind Regards,

Neil.


On 4/27/06, Jim C. Nasby <jnasby@pervasive.com> wrote:
> decibel=# select * from t;
>  a | b
> ---+---
>  1 | 0
>  3 | 1
>  5 | 3
>  7 | 5
>  2 | 0
>  4 | 2
>  6 | 4
>  8 | 6
> (8 rows)
>
> decibel=# select * from t x join t y on(x.a=y.b) where y.a=7;
>  a | b | a | b
> ---+---+---+---
>  5 | 3 | 7 | 5
> (1 row)
>
> decibel=# select * from t x join t y on(x.a=y.b) where y.a=8;
>  a | b | a | b
> ---+---+---+---
>  6 | 4 | 8 | 6
> (1 row)
>
> decibel=#
>
> As you can see, it selects the right data, but you'll need to step
> through it somehow. You might be able to do it with a generate_series(),
> or you can use a function. If we get WITH support/recursion in 8.2 you'd
> use that.
>
> I think that "SQL For Smarties" by Joe Celko might have an example of
> how to do this without using a function. Even if it doesn't it's a book
> any serious database developer should own.
>
> On Wed, Apr 26, 2006 at 10:35:15AM -0700, Ray Madigan wrote:
> > Scott,
> >
> > Thanks for your reply,  I tried what you said, worked around a few things
> > but I am still stuck.  The main reason is I didn't do an adequate job of
> > explaining the situation.  The table implements many linked lists and I want
> > to traverse one of them given the end of the list.
> >
> > Say the table contains
> >
> > h | v | j
> > 1   0   100
> > 3   1   300
> > 5   3   500
> > 7   5   700
> >
> > 2   0   200
> > 4   2   400
> > 6   4   600
> > 8   6   800
> >
> > If I specify t.h = 8 I want to traverse the even part of the table
> > If I specify t.h = 7 I want to traverse the odd part of the table
> >
> > If you can send me to a book to read I am willing
> >
> > Thanks
> >
> > -----Original Message-----
> > From: pgsql-sql-owner@postgresql.org
> > [mailto:pgsql-sql-owner@postgresql.org]On Behalf Of Scott Marlowe
> > Sent: Wednesday, April 26, 2006 8:59 AM
> > To: Ray Madigan
> > Cc: pgsql-sql@postgresql.org
> > Subject: Re: [SQL] LinkedList
> >
> >
> > On Wed, 2006-04-26 at 11:09, Ray Madigan 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:
> > >
> > > 1, 0
> > > 3, 1
> > > 7, 3
> > > 9, 7
> > > ...
> > >
> > > Any suggestions would be helpful, or I will have to implement the table
> > > differently.
> >
> > You should be able to do this with a fairly simple self-join...
> >
> > select a.id, b.aid, a.field1, b.field1
> > from mytable a
> > join mytable b
> > on (a.id=b.aid)
> >
> > Or something like that.
> >
> > ---------------------------(end of broadcast)---------------------------
> > TIP 2: Don't 'kill -9' the postmaster
> >
> >
> > ---------------------------(end of broadcast)---------------------------
> > TIP 6: explain analyze is your friend
> >
>
> --
> Jim C. Nasby, Sr. Engineering Consultant      jnasby@pervasive.com
> Pervasive Software      http://pervasive.com    work: 512-231-6117
> vcard: http://jim.nasby.net/pervasive.vcf       cell: 512-569-9461
>
> ---------------------------(end of broadcast)---------------------------
> TIP 2: Don't 'kill -9' the postmaster
>


Re: LinkedList

From
"Ben K."
Date:
> 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


Re: LinkedList

From
Guy Fraser
Date:
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




Re: LinkedList

From
"Ben K."
Date:
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 +
1where 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


Re: LinkedList

From
Guy Fraser
Date:
On Sat, 2006-29-04 at 01:50 -0500, Ben K. wrote:
> 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.
> 

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.

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.

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.

> 
> 
> > 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.
> 

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.





Re: LinkedList

From
"Ben K."
Date:
> 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