loading a double linked list from a sql database

Question

so this is what I got...

QueueList

{Id,Queue_Instance_ID, Parent_Queue_Instance_ID, Child_Queue_Instance_ID}

what will be the most efficient way to stuff this into a LinkedList<QueueList>? basically do you think I can go lower than o(n^2)?

thanks.

Answer 1

Thinking about this a little bit, you can do it in O(n) time, although it will take some extra stuff that will add some overhead. (Still O(n)).

You could use some sort of universal hashing scheme so that you can build a good hashtable. Essentially, hash by the instance id.

-Take each queue, and throw it into a doubly linked node of some sort. - Insert each node into the hashtable. - When you insert, check if the parent and/or child are in the hashtable and link accordingly. _ when you are done, start at the head (which you should be able to figure out in the first pass), walk the list and add it to your LinkedList or just use the resulting doubly linked list.

This takes one pass that is O(n), and the hashtable takes O(n) to initialize and inserts are O(1).

The problem left for you is choosing a good hashtable implementation that will give you those results.

Also, you have to consider the memory overhead, as I do not know how many results you expect. Hopefully enough to keep in memory.

I don't know of or think there is an SQL query based solution, but my SQL knowledge is very limited.

Hope this helps!

Answer 2

O(n) is better than O(n^2), right? ;)

I assume that the parent and child id are actually the previous and next id in the list.

First put the items in a dictionary so that you easily can look them up on the QueueInstanceId. In this loop you also locate the first item. Then you just add the items to the linked list and use the dictionary to get the next item. Example in C#:

Dictionary<int, QueueList> lookup = new Dictionary<int, QueueList>();
QueueList first = null;
foreach (QueueList item in source) {
 lookup.Add(item.QueueInstanceId, item);
 if (item.ParentQueueInstanceId == -1) {
  first = item;
 }
}
LinkedList<QueueList> list = new LinkedList<QueueList>();
do {
 list.AddLast(first);
} while (lookup.TryGetValue(first.ChildQueueInstanceId, out first));

Adding items to a dictionary and getting them by key are O(1) operations, and each loop is the length of the source list, so it's all an O(n) operation.