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

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类来构造链接列表以反映这些数据,但是由于值不按顺序排列,所以构造起来很尴尬.我真正想要做的是假设数据是有效的 - 只有一个第一个值,而所有其他值都跟随列表中另一个节点的"跟随"值.像这样的代码会很好(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的汽车.我真正想要做的是"将其添加到链接列表中,假设它将跟随某个ID的未来条目,即使该条目尚未添加,并继续." 然后在最后,检查链表的完整性,以确保每个节点指向另一个节点,并且有一个头节点.

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

Answer 1

我会分两步进行：

1. 将所有汽车加载到字典中，以汽车 id 为键，而不考虑它们的顺序
2. 通过循环遍历所有汽车（按字典顺序，无关紧要）将所有汽车连接起来，并通过字典找到后面的汽车，O(1)此时这应该是一个操作。

如果您无法在此时不将下一辆车链接到其中来构造汽车对象，即。汽车对象的“跟随”部分（或全部）是不可变的，我会创建一个临时类，甚至将 XML 节点存储在字典中，然后在获得汽车对象的排序后构造它们。

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