Thread: Linked List
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. 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
> 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. 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 > ... I missed "The table contains many linked lists", so wanted to do another try. I guess there should be a better way, but what if you do this? 1) Assuming your table has two columns (n int, p int), do create table tmplist (n int, p int); 2) drop function traverse(integer); create or replace function traverse (integer) returns integer as $$ declare x int; begin x := $1; while x is not null loop select n into x from linkedlist where p = x; insert into tmplist (select * from links where p=x); -- or do any processing end loop; return 1 ; end; $$ language plpgsql; 3) select traverse(0); select * from tmplist; 0 - 1 - 4 - 8 - 12 ... delete from tmplist; select traverse(2); select * from tmplist; 2 - 3 - 5 - 6 - ... (where 0 or 2 is the heads of the linked lists in the table, which you want to traverse) I'd appreciate any insight if there's a better way but somehow it was not possible to return setof int from within while loop whereas it was possible from within a for loop. I didn't find a way to deliver the templist table name as argument. (Somehow there seemed to be a bug(?) there) Regards, Ben K. Developer http://benix.tamu.edu
Ben, The pgsql function is compiled and wouldn't know how to handle a table name as a variable. If you rewrite the SQL to use the 'EXECUTE' statement I think you could do this, something along the lines of (untested): EXECUTE ''INSERT INTO '' || quote_ident(tmplist) || '' (SELECT * FROM links WHERE p=x)''; HTH, Greg Williamson DBA GlobeXplorer LLC -----Original Message----- From: pgsql-sql-owner@postgresql.org on behalf of Ben K. Sent: Sun 4/30/2006 6:29 PM To: Ray Madigan Cc: Pgsql-Sql-Owner; Marc G. Fournier; pgsql-sql@postgresql.org Subject: Re: [SQL]Linked List > 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. 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 > ... I missed "The table contains many linked lists", so wanted to do another try. I guess there should be a better way, but what if you do this? 1) Assuming your table has two columns (n int, p int), do create table tmplist (n int, p int); 2) drop function traverse(integer); create or replace function traverse (integer) returns integer as $$ declare x int; begin x := $1; while x is not null loop select n into x from linkedlist where p = x; insert into tmplist (select * from links where p=x); -- or do any processing end loop; return 1 ; end; $$ language plpgsql; 3) select traverse(0); select * from tmplist; 0 - 1 - 4 - 8 - 12 ... delete from tmplist; select traverse(2); select * from tmplist; 2 - 3 - 5 - 6 - ... (where 0 or 2 is the heads of the linked lists in the table, which you want to traverse) I'd appreciate any insight if there's a better way but somehow it was not possible to return setof int from within while loop whereas it was possible from within a for loop. I didn't find a way to deliver the templist table name as argument. (Somehow there seemed to be a bug(?) there) Regards, Ben K. Developer http://benix.tamu.edu ---------------------------(end of broadcast)--------------------------- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq !DSPAM:445564c2225761179214242!
> The pgsql function is compiled and wouldn't know how to handle a table >name as a variable. > If you rewrite the SQL to use the 'EXECUTE' statement I think you could >do this, something along the lines of (untested): > EXECUTE ''INSERT INTO '' || quote_ident(tmplist) || '' (SELECT * FROM >links WHERE p=x)''; Thanks. Yet, if I give the table name as the argument, I get the same error. drop function traverse(integer, text); create or replace function traverse (integer, text) returns integer as $$ declare x int; tname alias for $2; begin x := $1; while x is not null loop select n into x from linkswhere p = x; insert into tmplink (select * from links where p=x); EXECUTE ''INSERT INTO '' || quote_ident(tname)|| '' (SELECT * FROM links WHERE p=x)''; end loop; return 1 ; end; $$ language plpgsql; The above gives the following error. Please note that the first and second args are mixed up now. I tested it only on 8.0 (FC 4) and didn't on 8.1 and wonder whether it's a bug or I may be doing something wrong. Using tname or $2 doesn't change the result. ======================================================================== # select traverse(0, 'links2'); ERROR: syntax error at or near "INSERT" at character 11 QUERY: SELECT ''INSERT INTO '' || quote_ident( $1 ) || '' (SELECT * FROM links WHERE p= $2 )'' CONTEXT: PL/pgSQL function "traverse" line 10 at execute statement LINE 1: SELECT ''INSERT INTO '' || quote_ident( $1 ) || '' (SELECT ... ======================================================================== Regards, Ben K. Developer http://benix.tamu.edu