Cách hiệu quả nhất để xây dựng danh sách được liên kết từ dữ liệu được lưu trữ là gì?

Question

Tôi có dữ liệu được lưu trữ trong tài liệu XML mô tả danh sách được liên kết; tất cả các nút trừ một theo khác, do đó dữ liệu trông giống như sau:

<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> 

... để đưa ra một trật tự của 30, 29, 34, 9, 20, 12. Tôi đang sử dụng lớp LinkedList NET của để xây dựng một danh sách liên kết để phản ánh dữ liệu này, nhưng nó khó xử lý vì các giá trị nằm ngoài chuỗi. Những gì tôi thực sự muốn làm là giả định rằng dữ liệu là hợp lệ - có chính xác một giá trị đầu tiên, và tất cả những người khác có "sau" giá trị theo một nút khác trong danh sách. Mã như thế này sẽ là tốt (FindFirstForwards là một phương pháp mở rộng thông thường tôi đã viết để tìm các mục nhập danh sách đầu tiên liên kết mà lambda trao trả về 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)) 
     }); 
    } 
} 

Vấn đề là, nếu chiếc xe này sau có chưa được thêm vào orderedCars, ngoại lệ được ném vì FindFirstForwards không tìm thấy xe có ID "sau". Những gì tôi thực sự muốn làm là nói "thêm này vào danh sách liên kết, giả sử nó sẽ làm theo một số mục tương lai với một ID nhất định mặc dù mục đó chưa được thêm vào, và tiếp tục." Sau đó, ở cuối, kiểm tra tính toàn vẹn của danh sách liên kết để đảm bảo mỗi nút trỏ đến điểm khác và có một nút đầu.

Có cách nào ngắn gọn để thực hiện việc này không? Nếu không, điều gì sẽ là cách hiệu quả nhất (và tốt hơn là mã hóa ngắn gọn) để chuyển đổi XML này thành một danh sách liên kết trong bộ nhớ?

Answer 1

tôi sẽ làm điều này trong một hai bước thời trang:

1. tải tất cả những chiếc xe thành một cuốn từ điển, keyed bởi id của chiếc xe, mà không xem xét họ ra lệnh cho
2. liên kết lên tất cả những chiếc xe do looping thông qua chúng (theo thứ tự từ điển, không quan trọng), và tìm kiếm chiếc xe sau đây thông qua từ điển mà nên là một hoạt động O(1) vào thời điểm này.

Nếu bạn không thể xây dựng đối tượng ô tô mà không liên kết xe tiếp theo vào nó tại thời điểm đó, ví dụ: phần "sau" (hoặc tất cả) của đối tượng ô tô là không thay đổi, tôi sẽ tạo một lớp tạm thời hoặc thậm chí lưu trữ các nút XML trong từ điển và sau đó xây dựng các đối tượng ô tô sau khi bạn đặt hàng. Ngoài ra, mặc dù bạn chỉ có một liên kết từ một đối tượng này đến một đối tượng khác, bạn cũng có thể xem xét Phân loại Topo cho đối tượng này, nhưng lưu ý rằng việc triển khai nhanh thuật toán này thường sử dụng từ điển.