Linked List in SQL

create a table with two self referencing columns PreviousID and NextID. If the item is the first thing in the list PreviousID will be null, if it is the last, NextID will be null. The SQL will look something like this:

create table tblDummy
{
     PKColumn     int     not null, 
     PreviousID     int     null, 
     DataColumn1     varchar(50)     not null, 
     DataColumn2     varchar(50)     not null,  
     DataColumn3     varchar(50)     not null, 
     DataColumn4     varchar(50)     not null, 
     DataColumn5     varchar(50)     not null, 
     DataColumn6     varchar(50)     not null, 
     DataColumn7     varchar(50)     not null, 
     NextID     int     null
}

Using Adrian's solution, but instead of incrementing by 1, increment by 10 or even 100. Then insertions can be calculated at half of the difference of what you're inserting between without having to update everything below the insertion. Pick a number large enough to handle your average number of insertions - if its too small then you'll have to fall back to updating all rows with a higher position during an insertion.

Store an integer column in your table called 'position'. Record a 0 for the first item in your list, a 1 for the second item, etc. Index that column in your database, and when you want to pull your values out, sort by that column.

 alter table linked_list add column position integer not null default 0;
 alter table linked_list add index position_index (position);
 select * from linked_list order by position;

To insert a value at index 3, modify the positions of rows 3 and above, and then insert:

 update linked_list set position = position + 1 where position >= 3;
 insert into linked_list (my_value, position) values ("new value", 3); 

A linked list can be stored using recursive pointers in the table. This is very much the same hierarchies are stored in Sql and this is using the recursive association pattern.

You can learn more about it here (Wayback Machine link).

I hope this helps.

The simplest option would be creating a table with a row per list item, a column for the item position, and columns for other data in the item. Then you can use ORDER BY on the position column to retrieve in the desired order.

create table linked_list
(   list_id   integer not null
,   position  integer not null 
,   data      varchar(100) not null
);
alter table linked_list add primary key ( list_id, position );

To manipulate the list just update the position and then insert/delete records as needed. So to insert an item into list 1 at index 3:

begin transaction;

update linked_list set position = position + 1 where position >= 3 and list_id = 1;

insert into linked_list (list_id, position, data)
values (1, 3, "some data");

commit;

Since operations on the list can require multiple commands (eg an insert will require an INSERT and an UPDATE), ensure you always perform the commands within a transaction.

A variation of this simple option is to have position incrementing by some factor for each item, say 100, so that when you perform an INSERT you don't always need to renumber the position of the following elements. However, this requires a little more effort to work out when to increment the following elements, so you lose simplicity but gain performance if you will have many inserts.

Depending on your requirements other options might appeal, such as:

• If you want to perform lots of manipulations on the list and not many retrievals you may prefer to have an ID column pointing to the next item in the list, instead of using a position column. Then you need to iterative logic in the retrieval of the list in order to get the items in order. This can be relatively easily implemented in a stored proc.

• If you have many lists, a quick way to serialise and deserialise your list to text/binary, and you only ever want to store and retrieve the entire list, then store the entire list as a single value in a single column. Probably not what you're asking for here though.

There are a few approaches I can think of right off, each with differing levels of complexity and flexibility. I'm assuming your goal is to preserve an order in retrieval, rather than requiring storage as an actual linked list.

The simplest method would be to assign an ordinal value to each record in the table (e.g. 1, 2, 3, ...). Then, when you retrieve the records, specify an order-by on the ordinal column to get them back in order.

This approach also allows you to retrieve the records without regard to membership in a list, but allows for membership in only one list, and may require an additional "list id" column to indicate to which list the record belongs.

An slightly more elaborate, but also more flexible approach would be to store information about membership in a list or lists in a separate table. The table would need 3 columns: The list id, the ordinal value, and a foreign key pointer to the data record. Under this approach, the underlying data knows nothing about its membership in lists, and can easily be included in multiple lists.

A list can be stored by having a column contain the offset (list index position) -- an insert in the middle is then incrementing all above the new parent and then doing an insert.

You could implement it like a double ended queue (deque) to support fast push/pop/delete(if oridnal is known) and retrieval you would have two data structures. One with the actual data and another with the number of elements added over the history of the key. Tradeoff: This method would be slower for any insert into the middle of the linked list O(n).

create table queue (
    primary_key,
    queue_key
    ordinal,
    data
)

You would have an index on queue_key+ordinal

You would also have another table which stores the number of rows EVER added to the queue...

create table queue_addcount (
    primary_key,
    add_count
)

When pushing a new item to either end of the queue (left or right) you would always increment the add_count.

If you push to the back you could set the ordinal...

ordinal = add_count + 1

If you push to the front you could set the ordinal...

ordinal = -(add_count + 1)

update

add_count = add_count + 1

This way you can delete anywhere in the queue/list and it would still return in order and you could also continue to push new items maintaining the order.

You could optionally rewrite the ordinal to avoid overflow if a lot of deletes have occurred.

You could also have an index on the ordinal to support fast ordered retrieval of the list.

If you want to support inserts into the middle you would need to find the ordinal which it needs to be insert at then insert with that ordinal. Then increment every ordinal by one following that insertion point. Also, increment the add_count as usual. If the ordinal is negative you could decrement all of the earlier ordinals to do fewer updates. This would be O(n)