保存されたデータからリンクリストを構築する最も効率的な方法は？

Question

私は、リンクされたリストを記述するXML文書にデータを格納しています。私は.NETのLinkedListクラスを使用してい

<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：1のデータは次のようになりますので、他に従わを除くすべてのノードこのデータを反映するためにリンクされたリストを作成することができますが、値が順不同であるため構築が面倒です。私が本当にやりたいことは、データが有効であることを前提としています。正確に1つの最初の値があり、他のすべての値はリストの他のノードに続く「追従」値を持っています。このようなコードは（FindFirstForwards私は与えられたラムダが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)) 
     }); 
    } 
} 

この1つは、次の車がある場合はトラブルは、ありますorderedCarsにまだ追加されていない場合は、FindFirstForwardsが「フォロー」IDを持つ車を見つけられなかったため例外がスローされます。私が本当にやりたいことは、「リンクされたリストにこれを追加し、そのエントリがまだ追加されていなくても特定のIDを持つ将来のエントリが続くと仮定して実行します」と言います。最後に、リンクされたリストの完全性をチェックして、各ノードが別のノードを指していること、および1つのヘッドノードが存在することを確認します。

これを行う簡潔な方法はありますか？そうでない場合は、このXMLをメモリ内のリンクリストに変換する最も効率的な方法（できればコード簡潔な方法）は何でしょうか？

Answer 1

私は二段階方式でこれを実行します：ですべての車を自分の注文

リンクを考慮せず、辞書に

1. ロードすべての車、車のIDをキー（辞書順では関係ありません）、この時点でO(1)の操作でなければならない辞書を通して次の車を見つけることができます。

車のオブジェクトを、その時点で次の車にリンクさせずに構築することはできません。カーオブジェクトの「後続」部分（またはすべて）は不変です。一時クラスを作成したり、XMLノードを辞書に格納したりして、注文を受けた後に車オブジェクトを構築します。

また、あるオブジェクトから別のオブジェクトへのリンクが1つしかない場合でも、このトピックのTopological Sortを検討することもできますが、このアルゴリズムの高速実装では一般的に辞書も使用されます。