c# - 使用 LINQ 构建链表

Question

使用 LINQ 按前导(或父)元素索引对元素的无序列表进行排序的最快方法是什么？

每个元素都有一个唯一的 ID 和该元素的前任(或父)元素的 ID，可以从中构建一个链表来表示有序状态。

例子

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

排序顺序为{81, 20, 12, 65, 120}。可以很容易地从这些元素迭代组装一个(有序的)链表，但是可以用更少的 LINQ 语句完成吗？

编辑:我应该指定 ID 不一定是连续的。为简单起见，我选择了 1 到 5。查看随机更新的元素索引。

Answer 1

假设“索引”与排序无关(只是一个 ID)，假设这样声明:

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

然后您可以构建从前任到继任者的 map ，然后点击链接。然而，这不是纯 LINQ，但可读性强且非常高效:

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

编辑:这是一个非常低效但实用的解决方案。

思想是一个元素的索引必须是1+它的前导索引，这很容易递归指定。 base，case，当然是 head - 一个节点，其前身的 ID 是 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));
}

通过首先创建从继任者到前任者的映射，可以稍微改进第二个解决方案。不过，它的性能仍然不如命令式解决方案。

编辑:将第一个解决方案变成迭代器 block 。