从存储数据构建链表的最有效方法？

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:

我将数据存储在描述链表的XML文档中;除了一个节点之外的所有节点都跟随另一个节点

<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):

...给出30,29,34,9,20,12的排序。我使用.NET的LinkedList类来构建链接列表来反映这些数据，但是由于值不按顺序构建起来很尴尬。我真正想要做的是假设数据是有效的 - 只有一个第一个值，而所有其他值都跟随列表中另一个节点的“跟随”值。像这样的代码会很好（FindFirstForwards是我编写的自定义扩展方法，用于查找给定lambda返回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.

麻烦的是，如果此车所遵循的汽车尚未添加到orderedCars，则抛出异常，因为FindFirstForwards未找到具有“跟随”ID的汽车。我真正想要做的是“将它添加到链表中，假设它将跟随某个ID的未来条目，即使该条目尚未添加，并继续。”然后在最后，检查链表的完整性，以确保每个节点指向另一个节点，并且有一个头节点。

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?

这样做有简洁的方法吗？如果不是，那么将这种XML转换为内存链表的最有效（最好是代码简洁）方法是什么？

1 个解决方案

#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. 将所有汽车加载到字典中，按照汽车的ID键入，而不考虑订购
3. 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.
4. 通过循环链接所有汽车（按字典顺序，无所谓），并通过字典找到以下汽车，此时应该是O（1）操作。

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.

如果你不能在没有将下一辆汽车挂在那里的情况下构造一个汽车对象，即。汽车对象的“跟随”部分（或全部）是不可变的，我会创建一个临时类，甚至将XML节点存储在字典中，然后在订购后构建汽车对象。

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.

此外，即使您只有一个从一个对象到另一个对象的链接，您也可以考虑对此进行拓扑排序，但请注意，此算法的快速实现通常也使用字典。