Building a linked list with LINQ

Question

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 necessarily sequential. I chose 1 to 5 for simplicity. See updated element indices which are random.

Answer 1

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.