Skip certain types of nodes in DLL

I'm on Postgres 15.1 and have a node table as follows:

CREATE TABLE node (
    id TEXT PRIMARY KEY,
    is_skippable BOOL,
    prev TEXT REFERENCES node(id),
    "next" TEXT REFERENCES node(id)
);

This table represents a series of doubly linked lists, but on certain occasions for certain queries, I want to remove is_skippable nodes from the list and link around them.

For example, if I had the following data seeded in the DB, where there's one linked list of A1 <-> A2 <-> A3 (with A2 skippable) and one of B1 <-> B2:

INSERT INTO node VALUES 
  ('A1', FALSE, NULL, 'A2'), 
  ('A2', TRUE, 'A1', 'A3'), 
  ('A3', FALSE, 'A2', NULL),
  ('B1', FALSE, NULL, 'B2'), 
  ('B2', FALSE, 'B1', NULL);

For certain queries I want to link around is_skippable nodes. So if I queried this full table, the result set I'm looking for is:

id	prev	next
A1	NULL	A3
A3	A1	NULL
B1	NULL	B2
B2	B1	NULL

Note that A2 isn't in the result set and A2's pointers have been rewritten to the node before and after it.

Is there a well-supported way to do this in Postgres? I've seen answers for simple linked lists elsewhere on StackOverflow (like Linked list concept in postgresql), but they don't entail having to rewrite pointers. Thanks!

Sample Fiddle here: https://dbfiddle.uk/4lB4TAtF.

Solution

You could probably collapse it to run in a lateral query in both directions at once, but the fact that this only tries to skip to the nearest non-skippable element might actually be an advantage, making the recursive part more lightweight. Demo at db<>fiddle:

select id,(with recursive cte as( 
            select n2.id,n2.prev,n2.is_skippable
            from node n2
            where n2.id=n1.prev
            union
            select n2.id,n2.prev,n2.is_skippable
            from node n2 join cte 
              on n2.id=cte.prev
              and cte.is_skippable) CYCLE prev SET is_cycle USING path
          select id from cte where not is_skippable limit 1) as prev
        ,(with recursive cte as( 
            select n2.id,n2.next,n2.is_skippable
            from node n2
            where n2.id=n1.next
            union
            select n2.id,n2.next,n2.is_skippable
            from node n2 join cte 
              on n2.id=cte.next
              and cte.is_skippable) CYCLE next SET is_cycle USING path
          select id from cte where not is_skippable limit 1) as next
from node n1
where not is_skippable;

id	prev	next
A1	null	A3
A3	A1	null
B1	null	B2
B2	B1	null

It doesn't mind if the lists branch out. You can tighten the recursive cte join conditions to check for bi-directionality of the link to make it strictly follow the bi-directional path:
```
from node n2 join cte 
       on n2.id = cte.next
      and n2.prev=cte.id --add this for strict
```
branches start with a uni-directional link, so this will filter them out.
It doesn't mind cycles/rings/loops, if you happen to have any, thanks to built-in cycle detection.

A covering index speeds things up:

create index on node (id)
   include(is_skippable,prev,"next")
   with(fillfactor=100);

You might be interested in pgrouting and Apache AGE.