從存儲數據構建鏈表的最有效方法？

我有存儲在描述鏈接列表的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轉換爲內存中鏈表的最有效（最好是代碼簡潔）方式是什麼？

來源

2013-01-08 Jez

我會做這兩步時尚：

加載所有汽車進入字典，由汽車的ID鍵，而不考慮他們的訂貨
鏈接了所有的汽車循環瀏覽它們（按字典順序，無所謂），然後通過字典查找以下汽車，此時該操作應該是O(1)。

如果你不能構建一個汽車物體，而沒有將下一輛汽車連接到它那一點，即。汽車對象的「跟隨」部分（或全部）是不可變的，我會創建一個臨時類，或者甚至將XML節點存儲在字典中，然後在您訂購完畢後構造汽車對象。

而且，即使你只有從一個對象一個鏈接到另一個，你也可以考慮拓撲排序這一點，但要注意這種算法的那麼快實現通常使用的字典爲好。

來源

2013-01-08 11:15:16

+1。幾乎是最好的事情。爲了驗證鏈接，你必須有一個快速的關係查詢，並且一個列表很糟糕 - 一本字典閃耀。將它們加載到字典中，然後從中取出。 – TomTom

從存儲數據構建鏈表的最有效方法？

回答

相關問題