Most efficient way to construct a linked list from stored data?

Question

I have data stored in an XML document that describes a linked list; all nodes except one follow another, so the data looks something like this:

<cars>
    <car id="9" follows="34" />
    <car id="12" follows="20" />
    <car id="20" follows="9" />
    <car id="29" follows="30" />
    <car id="30" />
    <car id="34" follows="29" />
</cars>

... to give an ordering of 30, 29, 34, 9, 20, 12. I'm using .NET's LinkedList class to construct a linked list to reflect this data, but it's awkward to construct because the values are out of sequence. What I really want to do is assume that the data is valid - there is exactly one first value, and all others have "follows" values that follow one other node in the list. Code like this would be good (FindFirstForwards is a custom extension method I wrote to find the first linked list entry for which the given lambda returns true):

LinkedList<CarInstance> orderedCars = new LinkedList<CarInstance>();
XPathNodeIterator xmlIterator = _nav.Select("/dflt:cars/dflt:car", _namespaceResolver);
while (xmlIterator.MoveNext()) {
    if (!(xmlIterator.Current.Select("@follows").Count > 0)) {
        orderedCars.AddFirst(new CarInstance {
            CarId = int.Parse(xmlIterator.Current.GetAttribute("id", _defaultNamespace))
        });
    }
    else {
        orderedCars.AddAfter(orderedCars.FindFirstForwards(car => car.CarId == int.Parse(xmlIterator.Current.GetAttribute("follows", _defaultNamespace))), new CarInstance {
            CarId = int.Parse(xmlIterator.Current.GetAttribute("id", _defaultNamespace))
        });
    }
}

The trouble is, if the car that this one follows has not yet been added to orderedCars, an exception is thrown because FindFirstForwards didn't find a car with the "follows" ID. What I really want to do is say "add this to the linked list, assume it will follow some future entry with a certain ID even though that entry hasn't yet been added, and carry on." Then at the end, check the integrity of the linked list to make sure each node points to another, and that there is one head node.

Is there a concise way of doing this? If not, what would be the most efficient (and preferably, code-concise) way of converting this XML into an in-memory linked list?

Answer 1

I would do this in a two-step fashion:

1. Load all the cars into a dictionary, keyed by the id of the car, without considering their ordering
2. Link up all the cars by looping through them (in the dictionary order, doesn't matter), and finding the following car through the dictionary which should be a O(1) operation at this point.

If you cannot construct a car object without linking the next car into it at that point, ie. the "follows" part (or all) of the car object is immutable, I would create a temporary class, or even store the XML nodes in the dictionary, and then construct the car objects once you have their ordering.

Also, even though you only have one link from one object to another, you could also consider a Topological Sort for this, but note that fast implementations of this algorithm typically uses dictionaries as well.