CODEWITHSUNDEEP
sqlpostgresqllinked-listsingly-linked-listrecursive-cte
Charles B
Charles B

Reputation: 190

Linked lists: query first and last element of chained lists stored in SQL table

I have an SQL table with "lines" representing elements of chained lists. I could for example have the following records:

(id, previous_id)
------------------
(1, NULL)
(2, NULL)
(3, 2)
(4, 3)
(5, NULL)
(6, 4)
(7, 5)

We have 3 lists in this table:

(1,)
(2,3,4,6)
(5,7)

I would like to find the last element of each list and the number of elements in the list. The query I am looking for would output:

last, len
1, 1
6, 4
7, 2

Is this possible in SQL?

Upvotes: 1

Views: 886

Answers (3)

Charles L
Charles L

Reputation: 1

Here is an implementation in Microsoft SQL Server 2016 db<>fiddle

WITH chain
 AS (SELECT l.id AS [first], 
            l.id AS [last], 
            1 AS [len]
     FROM lines AS l
     WHERE l.previous_id IS NULL
     UNION ALL
     SELECT c.[first], 
            l.id, 
            c.[len] + 1 AS [len]
     FROM chain AS c
          JOIN lines AS l ON l.previous_id = c.[last]),
 result
 AS (SELECT DISTINCT 
            c.[first], 
            c.[last], 
            c.[len], 
            ROW_NUMBER() OVER(PARTITION BY c.[first] ORDER BY c.[len] DESC) AS rn
     FROM chain as c)
 SELECT r.[first], 
        r.[last], 
        r.[len]
 FROM result AS r
 WHERE r.rn = 1
 ORDER BY r.[first];

Upvotes: 0

Gordon Linoff
Gordon Linoff

Reputation: 1270573

You can use a recursive CTE:

with recursive cte as (
      select l.previous_id as id, id as last
      from lines l
      where not exists (select 1 from lines l2 where l2.previous_id = l.id)
      union all
      select l.previous_id, cte.last
      from cte join
           lines l
           on cte.id = l.id
     )
select cte.last, count(*)
from cte
group by cte.last;

Here is a db<>fiddle.

Upvotes: 1

Erwin Brandstetter
Erwin Brandstetter

Reputation: 658092

WITH RECURSIVE cte AS (
   SELECT id AS first, id AS last, 1 as len
   FROM   lines
   WHERE  previous_id IS NULL

   UNION ALL
   SELECT c.first, l.id, len + 1
   FROM   cte   c
   JOIN   lines l ON l.previous_id = c.last
   )
SELECT DISTINCT ON (first)
       last, len  -- , first -- also?
FROM   cte
ORDER  BY first, len DESC;

db<>fiddle here

Produces your result exactly.

If yo also want the first element like your title states, that's readily available.

Upvotes: 0

Related Questions