从存储的数据构建链表最高效的方法是什么？

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没有找到带有“follows”ID的汽车。 我真正想做的是说“将此添加到链表中，假设它将跟随具有某个ID的未来条目，即使该条目尚未添加，然后继续进行。” 然后，在最后，检查链表的完整性，以确保每个节点都指向另一个节点，并且有一个头节点。

是否有一种简洁的方法来做到这一点？ 如果没有，将XML转换为内存链接列表的最有效（并且最好是代码简洁）的方法是什么？

- Jez

Answer 1

我会采用两步法来完成此操作：

1. 将所有汽车加载到字典中，按汽车的id作为键，而不考虑它们的顺序。
2. 通过循环遍历它们（按字典顺序，无所谓），并通过字典找到下一辆车，这应该是一个O(1)操作。

如果在此时不能构建一个汽车对象而不将下一辆车链接到它，即汽车对象的“follows”部分（或全部）是不可变的，我会创建一个临时类，或者甚至将XML节点存储在字典中，然后在确定它们的顺序后再构造汽车对象。

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

- Lasse V. Karlsen

---

+1. 简直是最好的事情。要验证链接，您必须具有快速的关系查找功能，而列表则不太适用 - 字典则非常适合。将它们加载到字典中，然后从那里开始。 - TomTom