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