संग्रहित डेटा से जुड़ी हुई सूची बनाने का सबसे प्रभावी तरीका?

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. मैं नेट के LinkedList वर्ग का उपयोग कर रहा इस डेटा को प्रतिबिंबित करने के लिए एक लिंक्ड सूची बनाने के लिए, लेकिन यह निर्माण करने के लिए अजीब है क्योंकि मान अनुक्रम से बाहर हैं। मैं वास्तव में क्या करना चाहता हूं यह मान लेता है कि डेटा मान्य है - बिल्कुल एक पहला मूल्य है, और अन्य सभी के पास "अनुसरण" मान हैं जो सूची में एक अन्य नोड का पालन करते हैं। इस तरह संहिता अच्छा होगा (FindFirstForwards एक कस्टम विस्तार विधि मैं पहली बार लिंक्ड सूची प्रविष्टि जिसके लिए दिया लैम्ब्डा सच रिटर्न लगाने के लिए लिखा है):

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 को "निम्न" आईडी वाला कार नहीं मिला। मैं वास्तव में क्या करना चाहता हूं, "यह लिंक की गई सूची में जोड़ें, मान लीजिए कि यह एक निश्चित आईडी के साथ कुछ भावी प्रविष्टि का पालन करेगा, भले ही उस प्रविष्टि को अभी तक जोड़ा नहीं गया है, और आगे बढ़ें।" फिर अंत में, यह सुनिश्चित करने के लिए लिंक की गई सूची की अखंडता की जांच करें कि प्रत्येक नोड दूसरे को इंगित करता है, और एक हेड नोड है।

क्या ऐसा करने का एक संक्षिप्त तरीका है? यदि नहीं, तो इस एक्सएमएल को इन-मेमोरी लिंक्ड लिस्ट में परिवर्तित करने का सबसे कुशल (और अधिमानतः, कोड-संक्षिप्त) तरीका क्या होगा?

Answer 1

मैं एक दो कदम फैशन में इस करना होगा: उनके आदेश देने

लिंक द्वारा सभी कारों तक पर विचार किए बिना

1. लोड सभी एक शब्दकोश में कार, कार की आईडी से keyed, उनके माध्यम से लूपिंग (शब्दकोश क्रम में, कोई फर्क नहीं पड़ता), और इस बिंदु पर O(1) ऑपरेशन होना चाहिए जो शब्दकोश के माध्यम से निम्नलिखित कार ढूंढना।

यदि आप उस बिंदु पर अगली कार को जोड़ने के बिना कार ऑब्जेक्ट नहीं बना सकते हैं, यानी। कार ऑब्जेक्ट का "अनुसरण" भाग (या सभी) अपरिवर्तनीय है, मैं एक अस्थायी कक्षा बनाउंगा, या शब्दकोश में एक्सएमएल नोड्स को भी स्टोर करूंगा, और फिर ऑर्डर करने के बाद कार ऑब्जेक्ट्स का निर्माण करूंगा।

इसके अलावा, भले ही आपके पास केवल एक ऑब्जेक्ट से दूसरे ऑब्जेक्ट का एक लिंक हो, फिर भी आप इसके लिए टोपोलॉजिकल सॉर्ट पर विचार कर सकते हैं, लेकिन ध्यान दें कि इस एल्गोरिदम का तेज़ कार्यान्वयन आम तौर पर शब्दकोशों का भी उपयोग करता है।