Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Though SQL is more affiliated with table like operations and not so much with recursive, say we would like to implement the linked (or double-linked) list concept (like we have for instance in C).
Is there any way to do this efficiently, considering that we can have items moving around from any place into any place on a linked list?
Some solution using CLR?
Or is it really something that should never be brought to SQL Server?

Note that this question evolved also into a linked lists VS trees discussion

Though I pinned SQL Server, this is an academic like question, so a solution in any other is also good, even if we just get to the conclusion that this is something that should never be brought to the database.

share|improve this question
1  
I have to work with a linked list type structure in a database and it prompted this question dba.stackexchange.com/questions/36698/… It can be done in a database but it can be difficult to marry the functionality of a linked list with database constraints which enforce integrity –  kevinsky Jul 12 '13 at 13:07
2  
Write-up on linked list in SQL 2008 paulbradley.org/linked-lists-sql-server –  Shawn Melton Jul 12 '13 at 13:12
    
Can you give us an idea of what you're going to do with this data? Is a linked list really the best structure for it, or is this an attempt to apply programming paradigms to structures in a database? –  Jon Seigel Jul 12 '13 at 13:24
    
@ShawnMelton, thanksfor the article! –  user16484 Jul 12 '13 at 14:04
1  
@ypercube Excuse me! It's all about terms. I should have said a tree structure rather than a linked list. –  kevinsky Jul 12 '13 at 17:25

1 Answer 1

up vote 4 down vote accepted

A linked list is just a very simple directed acyclic graph. There is no reason why this is in any way difficult, or should be avoided for sql server.

Think about it, tree structures are more complex than linked lists. Every implementation of a forum on the internet that stores data in a relational database has implemented the basics of a linked list. On this very page, answers form a linked list. They can be added and deleted. They can be moved in position (aka, ranked by votes).

The particular representation to be used depends only on the trade-offs you wish to make between maintaining the list (insert, update, delete) and retrieval.

--Works great for INS/UPD/DEL, In order retrieval isn't the best.
CREATE TABLE Item (id int identity, next int, prev int) 

--makes in order retrieval fast, deletes are a problem, inserts may require re-numbering.    
CREATE TABLE Item (id int identity, position  int ) 

--Works great for in-order retrieval, and allow cheap insertion/deletion, 
--certain edge cases might be tricky to handle.
CREATE TABLE (id int identity, position Decimal(24,12 )  ) 
--for inserts, use the average of the before and after, for deletes, just delete.

Update: Question is about trees vs linked lists in SQL server

SQL Server has the HierarchyId data type which is designed for easing the implementation and querying of tree like structures.

CREATE TABLE Item (id int identity, NodeId HierarchyId)
share|improve this answer
    
just the answer I was looking for. I felt that the implementation would depend on the situation but here you clarify it very well. Thanks –  user16484 Jul 13 '13 at 9:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.