How to traverse postgresql in the form of linked list?-CodePudding

I have a table in the form of linked list.

| unique_id |    next |
| --------  | ------- |
| 1         | 3       |
| 2         | null    |
| 3         | 2       |

Here the unique_id is the id of the row. Next is the id of the row it is pointing to. There is another table which keeps track of the head. Let's say row with uId=1 is the head. So, I want to query my table such that it extracts head from the headTable and gives the data in the same order as this linked-list. 1->3->2 in the form of an array of rows.

Expected Result : [{unique_id:1, next:3},{unique_id:3, next:2}{unique_id:2, next:null}] Sorry, I'm unable to render the above table properly that's why It's in the form of code.

CodePudding user response：

Try a recursive query - and add a "path" column to the query:

CREATE TABLE 
-- your input ....
indata(unique_id,next) AS (
          SELECT 1,3
UNION ALL SELECT 2,null
UNION ALL SELECT 3,2
)
;
\pset null NULL
WITH RECURSIVE recursion AS (
  SELECT
    unique_id
  , next
  , (unique_id::VARCHAR(8)||'>'||next::VARCHAR(8))::VARCHAR(16) AS path
  FROM indata
  WHERE unique_id=1 -- need a starting filter
  UNION ALL
  SELECT
    c.unique_id
  , c.next
  , p.path||'>'||NVL(c.next::VARCHAR(8),'NULL')
  FROM recursion p
  JOIN indata    c ON p.next = c.unique_id
)
SELECT * FROM recursion;
-- out  unique_id | next |    path    
-- out ----------- ------ ------------
-- out          1 |    3 | 1>3
-- out          3 |    2 | 1>3>2
-- out          2 | NULL | 1>3>2>NULL

CodePudding user response：

A bit late with the answer, but here is my version, without adding columns.

with recursive headtablelist as (
  select unique_id, next
    from headtable
  where unique_id = 1
union
  select e.unique_id, e.next
    from headtable e
  inner join headtablelist s on s.next = e.unique_id
)  

select * from headtablelist;

Demo in dbfiddle

More information about recursive queries can be found here.