저장된 데이터에서 연결된 목록을 만드는 가장 효율적인 방법은 무엇입니까?

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> 

... 나는 .NET의 LinkedList 클래스를 사용하고, 12 20, 9, 34, 29, 30의 순서를 제공하기 : 데이터를 다음과 같이 보입니다 그래서 하나를 제외한 모든 노드는 다른를 따라 이 데이터를 반영하는 연결 목록을 만들지 만 값이 순서가 틀리기 때문에 구성하기가 어렵습니다. 내가 정말로하고 싶은 것은 데이터가 유효하다고 가정하는 것입니다. 정확하게 첫 번째 값이 있고 다른 모든 값은 목록의 다른 노드를 따르는 "후행"값을가집니다.

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)) 
     }); 
    } 
} 

가 말썽이 하나가 다음 차가,이 경우이 같은 코드 (FindFirstForwards 내가 주어진 람다가 true를 반환하는 최초의 연결리스트 항목을 찾기 위해 쓴 사용자 정의 확장 방법입니다) 좋은 것 orderedCars에 아직 추가되지 않은 경우 FindFirstForwards이 "following"ID가있는 자동차를 찾지 못했기 때문에 예외가 발생합니다. 내가 정말로하고 싶은 것은 "연결된 목록에 이것을 추가하고, 해당 항목이 아직 추가되지 않았더라도 특정 ID로 향후 항목을 따라 가며 계속 진행할 것이라고 가정합니다."라고 말합니다. 그런 다음 링크 된 목록의 무결성을 확인하여 각 노드가 다른 노드를 가리키고 하나의 헤드 노드가 있는지 확인하십시오.

간결한 방법이 있습니까? 그렇지 않다면이 XML을 메모리 내 연결 목록으로 변환하는 가장 효율적인 (그리고 코드 간결한) 방법은 무엇일까요?

Answer 1

내가 두 단계 방식으로이 작업을 수행 할 것입니다 : 모든 차를 자신의 주문

링크를 고려하지 않고, 사전에

1. 로드 모든 자동차, 자동차의 ID로 키가 사전 순으로 반복해도 상관 없습니다.이 시점에서 O(1) 작업이어야하는 사전을 통해 다음 차량을 찾습니다.

그 시점에서 다음 자동차를 연결하지 않고 자동차 개체를 만들 수없는 경우. car 객체의 "following"부분 (또는 모두)은 변경 불가능합니다. 즉, 임시 클래스를 만들거나 사전에 XML 노드를 저장 한 다음 자신의 순서를 지정하면 car 객체를 생성합니다.

또한 하나의 개체에서 다른 개체로 연결되는 링크가 하나 뿐이라고하더라도 토폴로지 정렬을 고려할 수 있지만이 알고리즘의 빠른 구현은 일반적으로 사전도 사용합니다.