Building a linked list with LINQ

What is the fastest way to order an unordered list of elements by predecessor (or parent) element index using LINQ?

Each element has a unique ID and the ID of that element's predecessor (or parent) element, from which a linked list can be built to represent an ordered state.

Example

ID      | Predecessor's ID
--------|--------------------
20      | 81
81      | NULL
65      | 12
12      | 20
120     | 65

The sorted order is {81, 20, 12, 65, 120}. An (ordered) linked list can easily be assembled iteratively from these elements, but can it be done in fewer LINQ statements?

Edit: I should have specified that IDs are not nec开发者_运维知识库essarily sequential. I chose 1 to 5 for simplicity. See updated element indices which are random.

---

Assuming that "index" has nothing to do with ordering (just an ID), let's say declared this way:

public class Node
{
    public int ID { get; set; }
    public int? PredID { get; set; }
}

Then you could build up a map from predecessor to successor, and then follow the links. This isn't pure LINQ however, but is readable and quite efficient:

public static LinkedList<int> GetLinkedList(IEnumerable<Node> nodes)
{
    if(nodes == null)
       throw new ArgumentNullException("nodes");

    return new LinkedList<int>(GetOrderedNodes(nodes.ToList()));
}

private static IEnumerable<int> GetOrderedNodes(IEnumerable<Node> nodes)
{
    // Build up dictionary from pred to succ.
    var links = nodes.Where(node => node.PredID != null)
                     .ToDictionary(node => node.PredID, node => node.ID);

    // Find the head, throw if there are none or multiple.
    var nextId = nodes.Single(node => node.PredID == null).ID;

    // Follow the links.
    do
    {
        yield return nextId;

    } while (links.TryGetValue(nextId, out nextId));
}

EDIT: Here's a horribly inefficient but functional solution.

The idea is that an element's index must be 1 + its predecessor's index, which is easy to specify recursively. The base, case, of course, is the head - a node whose predecessor's ID is null.

static LinkedList<int> GetLinkedList(IEnumerable<Node> nodes)
{
    return new LinkedList<int>
           (  from node in nodes
              orderby GetIndex(nodes, node)
              select node.ID
           );                                       
}


static int GetIndex(IEnumerable<Node> nodes, Node node)
{
    return node.PredID == null ? 0 :
           1 + GetIndex(nodes, nodes.Single(n => n.ID == node.PredID));
}

It's possible to improve the second solution somewhat by first creating a map from successor to predecessor. It's still nowhere as performant as the imperative solution though.

EDIT: Turned first solution into an iterator block.

---

For ordering the fact that the nodes are linked is irrelevant, just the ids matter. That being the case you can just use OrderBy, which in this case will put the nullable int at the top, then sort ascending.

public class ListNode
{
    public int Id { get; set; }
    public int? Predecessor { get; set; }
}


List<ListNode> myList = new List<ListNode> {
                                new ListNode() { Id = 2, Predecessor = 1},
                                new ListNode() { Id = 1, Predecessor = null},
                                new ListNode() { Id = 5, Predecessor = 4},
                                new ListNode() { Id = 3, Predecessor = 2},
                                new ListNode() { Id = 4, Predecessor = 3}};


var sortedbyPredecessor = myList.OrderBy(n => n.Predecessor).ToList();