How do I sort a linked list in sql?

Question

I have implemented a linked list as a self-referencing database table:

CREATE TABLE LinkedList(
    Id bigint NOT NULL,
    ParentId bigint NULL,
    SomeData nvarchar(50) NOT NULL)

where Id is the primary key, and ParentId is the Id of the previous node on the list. The first node has ParentId = NULL.

I now want to SELECT from the table, sorting the rows in the same order they should appear, as nodes on the list.

Eg.: if the table contains the rows

Id      ParentId  SomeData
24971   NULL      0
38324   24971     1
60088   60089     3
60089   38324     2
61039   61497     5
61497   60088     4
109397  109831    7
109831  61039     6

Then sorting it, using the criteria, should result in:

Id      ParentId  SomeData
24971   NULL      0
38324   24971     1
60089   38324     2
60088   60089     3
61497   60088     4
61039   61497     5
109831  61039     6
109397  109831    7

You're supposed to use the SomeData colum as a control, so please don't cheat doing ORDER by SomeData :-)

Answer 1

In Oracle:

SELECT Id, ParentId, SomeData
FROM (
  SELECT ll.*, level AS lvl
  FROM LinkedList ll
  START WITH
    ParentID IS NULL
  CONNECT BY
    ParentId = PRIOR Id
)
ORDER BY
  lvl

P. S. It's a bad practice to use NULL as ParentID, as it is not searchable by indices. Insert a surrogate root with id of 0 or -1 instead, and use START WITH ParentID = 0.

Answer 2

I found a solution for SQLServer, but looks big and much less elegant than Quassnoi's

WITH SortedList (Id, ParentId, SomeData, Level)
AS
(
  SELECT Id, ParentId, SomeData, 0 as Level
    FROM LinkedList
   WHERE ParentId IS NULL
  UNION ALL
  SELECT ll.Id, ll.ParentId, ll.SomeData, Level+1 as Level
    FROM LinkedList ll
   INNER JOIN SortedList as s
      ON ll.ParentId = s.Id
)

SELECT Id, ParentId, SomeData
  FROM SortedList
 ORDER BY Level

Answer 3

(edit: d'oh! While I was debugging you found it too!)

In SQL Server:

;WITH cte (Id, ParentId, SomeData, [Level]) AS (
    SELECT Id, ParentId, SomeData, 0
    FROM LinkedList
    WHERE ParentId IS NULL
    UNION ALL
    SELECT ll.Id, ll.ParentId, ll.SomeData, cte.[Level] + 1
    FROM LinkedList ll
    INNER JOIN cte ON ll.ParentID = cte.ID
)
SELECT * FROM cte
ORDER BY [Level]

Answer 4

what about

Msg 530, Level 16, State 1, Line 1 The statement terminated. The maximum recursion 100 has been exhausted before statement completion.

?