linked list in SQL and Trees

Question

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.

Answer 1

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 Item (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)