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

Question

我将数据存储在描述链表的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>

..。为了给出30，29，34，9，20，12的顺序。我正在使用.NET的LinkedList类来构造一个链表来反映这个数据，但是构造起来很笨拙，因为值的顺序是错的。我真正想做的是假设数据是有效的--只有一个第一个值，并且所有其他的值都有跟在列表中另一个节点后面的"follows“值。这样的代码会很好(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))
        });
    }
}

问题是，如果这辆车跟随的汽车还没有添加到orderedCars中，就会抛出一个异常，因为FindFirstForwards没有找到ID为" follows“的汽车。我真正想做的是说：”将这个添加到链表中，假设它将跟随某个具有特定ID的未来条目，即使该条目还没有被添加，然后继续。“最后，检查链表的完整性，确保每个节点指向另一个节点，并且有一个头节点。

有没有一种简明的方法来做到这一点？如果不是，那么将此XML转换为内存链表的最有效(最好是代码简洁)方法是什么？

Answer 1

我将以两步的方式完成此操作：

1. 将所有汽车加载到字典中，以汽车的id为关键字，而不考虑它们的排序
2. 通过循环遍历所有汽车来链接所有汽车(在字典顺序中，这并不重要)，并通过字典找到下面的汽车，这在这一点上应该是一个O(1)操作。

如果你不能在不链接下一辆汽车的情况下构造一个汽车对象，也就是。car对象的"follows“部分(或全部)是不可变的，我会创建一个临时类，甚至将XML节点存储在字典中，然后在获得car对象的顺序后构造它们。

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