How do I create a Generic Linked List?

Question

I am trying to use a Generic Linked List to hold some WorkFlow steps in my application. Here is how I'm persisting it to my database.

OrderID  WorkFlowStepID  ParentWorkFlowStepID
178373    1                         NULL
178373    2                         1
178373    3                         2

I get this dataset back in a datareader object. I then loop through the datareader and create a WorkFlowStep object that includes a WorkFlowStepID property and a ParentWorkFlowStepID property. I add the first object to my LinkedList by using the .AddFirst() method. My next idea is to create the next object and then insert it after the object in the LinkedList where it's WorkFlowStepID is equal to the new object's ParentWorkFlowStepID. I can't figure out of to find the object in the LinkedList. The find() method is asking for a value, but I don't understand what value it is, or how I can find it.

Answer 1

So do you mean you're using the linked list class in the framework?

If so, the Find method doesn't really do what you want it to. Basically you want a version which takes a predicate. This would be easier if the class exposed an iterator of LinkedListNode<T>. Fortunately it's easy to provide an extension method to do that:

public static IEnumerable<LinkedListNode<T>> GetNodes<T>(this LinkedList<T> list)
{
    LinkedListNode<T> current = list.First;
    while (current != null)
    {
        yield return current;
        current = current.Next;
    }
}

Then you can do (and I stress all of this is untested):

var node = list.GetNodes().FirstOrDefault(x.Value.WorkFlowerStepID = parentWorkFlowStepID);
if (node != null)
{
    list.AddAfter(node, newItem);
}
else
{
    // Whatever. Add to tail?
}

Answer 2

Define a comparison function and then call the list .Sort() method with the comparison function passed in as a delegate. The function should take 2 objects(e.g. X and Y) and return -1 if X is greater than Y, 0 if they are equal or 1 if Y is greater than X.

Answer 3

Isn't it possible to persist your data like so Order Id, Workflow Step Id, Weight

Then the first item has weight 0, the next weight 1, the next weight 2. The heavy items sink to the end of your list.

Finally, when you read the data from the database, you just order it by weight (ascending) and then add each item onto the end of your list as you read it from the result. This means you don't need a custom find method at all.

Representing it this way makes life simpler if you want to remove a step directly from the database, as right now it is possible to break your database schema by deleting WorkFlowStepID 2. Item 3 then has no parent item to attach to.

Answer 4

If the output is a degenerated tree (i.e. there is always 1 child for a node), you could have a linkedlist with a reference to last node and keep adding child to the last node.