使用 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; }
}

然后您可以构建从前一个到后一个的映射，然后单击链接。然而，这不是纯粹的 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 + 其前任元素的索引，这很容易递归指定。当然，基础情况是头 - 一个其前任 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));
}

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

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

Answer 2

对于排序来说，节点链接的事实是无关紧要的，只是 id 很重要。在这种情况下，您可以使用 OrderBy ，在本例中会将可空 int 放在顶部，然后升序排序。

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