How do I order a doubly linked list?

I have a table, as follows:

id | val | next | prev
1   13   3       4
2   87   4       3
3   34   2       2
4   98   1       1

All columns are ints.
Prev and next link to the previous and next row ID's.

I am trying to do a SELECT that will order the rows properly, so that I get row 1,3,2, and 4; in that order.

Any ideas?
LVL 1
thekodAsked:
Who is Participating?
 
coffeeshopConnect With a Mentor Commented:
I found some interesting links to your question, but for different sql dialects. Take a look at:
 
http://www.webinade.com/web-development/creating-recursive-sql-calls-for-tables-with-parent-child-relationships

http://www.mssqltips.com/tip.asp?tip=938

The point is to do this without creating a "real" temporary table, just doing this in memory.
0
 
ralmadaCommented:
do you mean that you want to sort by the val column?
select * from yourtable order by val
will do it.
0
 
coffeeshopConnect With a Mentor Commented:
No, i understand that thekod wants to sort a linked list. It's a kind of recursion needed, because "next" is the entry point for the next "id". This can be done with multiple joins, but only to a specific deep (I use this for a similar parentstructure limited to 3 levels). It can be done easy by a function, but for sql? I don't know.
0
Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

 
thekodAuthor Commented:
Correct, coffeeshop.  This would be simple if I could write a comparison function myself, or if I were doing multiple selects.  I'd just like to do this all in one query.
0
 
ralmadaCommented:
Well if you elaborate a little bit more on what are you trying to accomplish then we can certainly help you to do that in SQL. Please post a more detailed example with expected results.
 
0
 
thekodAuthor Commented:
I have a double linked list in a MySQL table, four columns, all integer values.  The first, `id`, is the primary key.  The second, `val` is an arbitrary value.  The third, `next`, is the id of the row that should be considered next.  The fourth, `prev`, is the id of the row that should be considered previous.  The last row links to the first as next, and the first row links to the last as previous.  I wish to select all fields from the table, and order according to the order of the linked list.  I just realized it can't be circular with this ordering, so we'll say that the last row points to itself as next, and the first row points to itself as prev.
0
 
ralmadaConnect With a Mentor Commented:
Well, I believe you are looking for a recursive query in MySql not MS-SQL. Please take a look at this link:
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html 
0
 
thekodAuthor Commented:
That may work, but it will be overly involved, since that is attempting to design a table for selecting hierarchal data when I'm really just looking for a better comparison for a flat file of data.
0
 
coffeeshopCommented:
To only get the correct sorting order for the id try this:

SELECT tblSortLinked.*, IIf([ID]=1,0,IIf([Next]=1,9999,[Next])) AS SortID
FROM tblSortLinked
ORDER BY IIf([ID]=1,0,IIf([Next]=1,9999,[Next]));

This sets the start at id=1 and I set a maximum of id's to 9999, just for sorting. For setting this start and end you can use a query. In my example I asume that the links are straight forward.
0
 
thekodAuthor Commented:
That looks like it will work -- but I can't figure out how.  ;-)

Can you explain it?
0
 
coffeeshopCommented:
If the previous works for your purpose, you can use the following, because this set start and end automatically:

You need a query for the min and max id, call it "qryLinkedListStart":

SELECT Min(tblSortLinked.ID) AS IDMin, Max(tblSortLinked.ID) AS IDMax
FROM tblSortLinked

Change my first example from above:

SELECT tblSortLinked.*, IIf([ID]=[IDMin],[IDMin]-1,IIf([Next]=[IDMin],[IDMax]+1,[Next])) AS SortID
FROM tblSortLinked, qryLinkedListStart
ORDER BY IIf([ID]=[IDMin],[IDMin]-1,IIf([Next]=[IDMin],[IDMax]+1,[Next]));

It uses the "next" field to sort. Assuming that the linked list is complete and straight forward, next reflects the correct sort order for the list. So it is sufficent to sort with "next".

The only problem is to get the first and last entry. The first is the smallest id (or we define another start somewhere in the list, this is possible to).

The last is where the list links to the first value (if we have no link back, this should be changed to null or something else).
0
 
coffeeshopCommented:
I think my above solution works for what thekod asked for, as he comments "That looks like it will work -- but I can't figure out how". In my next comment I do a little optimation on what I suggested and explained how it works.
0
 
coffeeshopCommented:
I think my above solution works for what thekod asked for, as he comments "That looks like it will work -- but I can't figure out how". In my next comment I do a little optimation on what I suggested and explained how it works.

(Sorry for double-post, I hit the wrong button)
0
 
coffeeshopCommented:
Ahhh, yes - I just checked this with the sample data and so it worked. But - yes, you're right! - if you change the data/links only a recursive function as ralmada and I suggested first will work. Sorry.
0
 
ralmadaCommented:
Then, we did pointed the asker in the right direction. At least with my comment # 24242573, where I suggested recursive queries. (I haven't checked coffeeshop's links).
0
 
ralmadaCommented:
The asker mentioned >> That may work, but it will be overly involved<<
I don't think there's another way to do this. I might be wrong, but being overly involved and create a recursive query as indicated is the best approach. I don't think the asker can reject the only solution possible.
In my opinion, points should be splitted between coffeeshop's and myself. The grading should be "B" or below.
Anyhow, proceed as you deem convenient.
0
 
thekodAuthor Commented:
I was unable to make any of the posted solutions work.  I asked a DBA at my workplace, and he put together the following, which works, using a while loop:

create table #temp (val varchar(1),nextid int)

declare @Rows int
declare @id int
set @id = 1

select @Rows = count(*)
from datatable

while @Rows >0

begin
insert into #temp
select val,nextid
from datatable
where id =@id and outsideref = '42'

select @id = nextid
from datatable
where id =@id

SET @Rows = @Rows -1
end

Select val from #temp
0
All Courses

From novice to tech pro — start learning today.