Создание связанного списка с помощью LINQ

Question

Какой самый быстрый способ упорядочить неупорядоченный список элементов по индексу предшествующего (или родительского) элемента с помощью LINQ?

Каждый элемент имеет уникальный идентификатор и идентификатор элемента предшествующего (или родительского) этого элемента, из которого можно построить связанный список для представления упорядоченного состояния.

Пример

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

Порядок сортировки: {81, 20, 12, 65, 120}.(Упорядоченный) связанный список может быть легко собран итеративно из этих элементов, но можно ли сделать это за меньшее количество операторов LINQ?

Редактировать: Я должен был указать, что идентификаторы не обязательно являются последовательными.Я выбрал от 1 до 5 для простоты.Смотрите обновленные индексы элементов, которые являются случайными.

Answer 1

Предполагая, что «index» не имеет ничего общего с упорядочением (просто ID), скажем, объявлено так:

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

Тогда вы можете построить карту от предшественника к преемнику, а затем перейти по ссылкам. Это не pure 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 + индекс его предшественника, который легко определить рекурсивно. Основой, случаем, конечно же, является голова - узел, чей идентификатор предшественника равен 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));
}

Можно улучшить второе решение до некоторой степени , сначала создав карту от преемника к предшественнику. Тем не менее, это нигде не так эффективно, как императивное решение.

EDIT : Превратило первое решение в блок итератора.

Answer 2

Для упорядочения факта, что узлы связаны, не имеет значения, важны только идентификаторы.В этом случае вы можете просто использовать 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();