Creating a linked list with LINQ

Question

What is the fastest way to sort an unordered list of items by the index of the predecessor element (or parent) using LINQ?

Each element has a unique identifier and an identifier for the element of the previous element (or parent element) from which a linked list can be created to represent an ordered state.

Example

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

Sorted order {81, 20, 12, 65, 120}. A linked list (ordered) can be easily iterated from these elements, but can this be done with fewer LINQ statements?

Edit: I should have indicated that identifiers are not necessarily sequential. For simplicity, I selected from 1 to 5. See Updated Indexes of Elements that are Random.

Answer 1

Assuming the “index” has nothing to do with ordering (just an identifier), let's say declared in this way:

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

You can then create a map from predecessor to successor, and then follow the links. However, this is not pure LINQ, but readable and efficient enough:

 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 is a terribly inefficient but functional solution.

The idea is that the index of the element should be 1 + its predecessor index, which is easy to specify recursively. The base, the case, of course, is the head - a node, whose predecessor 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 is possible to slightly improve the second solution by first creating a card from a successor to a predecessor. However, it is still not as effective as an imperative decision.

EDIT : turned the first solution into an iterator block.

Answer 2

In order to streamline the fact that the nodes are connected, it does not matter. In this case, you can simply use OrderBy , which in this case will put a nullable int at the top, then sort in ascending order.

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