List representation in Postgresql

zashto 0
Viewed 33

I would like to implement a linked list in Postgresql and I imagine it is the same as implementing a list using array indexing. In DB, table and primary key will do the job I suppose. For a -> b -> c -> d -> e and 1 -> 2 -> 3 -> 4 representation will be:

[0] -> {"a", 1}
[1] -> {"b", 2}
[2] -> {"c", 4}
[3] -> {"1", 5}
[4] -> {"d", 7}
[5] -> {"2", 6}
[6] -> {"3", 8}
[7] -> {"e", nil}
[8] -> {"4", nil}

Because I have not enough SQL knowledge so I still struggle with Postgresql implementation. Could you elaborate on this? INSERT should add at the end and SELECT result should start from the end. Nor UPDATE and DELETE are required if this is helpful for the optimization.

linked-list sql postgresql
1 Answers

I'm not sure that this is the best way to represent your data, but you can make a list like that.

 create table list_table (
    id int primary key generated by default as identity
   ,data text
   ,next int unique references list_table(id)
 );
 -- insert you example data
 insert into list_table values (0,'a',1),
 (1,'b', 2),(2,'c',4),(3,'1',5),(4,'d',7),
 (5,'2',6),(6,'3',8),(7,'e',NULL),(8,'4',NULL);
 -- advance the sequence used by the id column to safe position
 select setval('list_table_id_seq',max(id)) from list_table;

To see the ends of both (all) lists:

select * from list_table where next is null;

To append to the list that ends with id 7

with n as ( insert into list_table(data) values ('f') returning id ) 
update list_table as l set next=n.id from n where l.id=7;
Jasen0
Related