How to do a recursive LINQ query?

Question

I have a recursive data structure, such as linked list:

class Node
{
    private Node next;
    private int data;

    // (...)
    public Node Next
    {
        get
        {
            return next;
        }
    }

    public int Data
    {
        get
        {
            return data;
        }
    }
}

I'd like to make a LINQ query, which starts from the head of the list and then goes through the elements, collecting data on the fly. How to do that?

Answer 1

Here are two helper classes I us to parse all the nodes in a TreeView control.

You might be inspired by how the yield keyword is used to adapt it for your needs.

internal static IEnumerable<TreeNode> Descendants(this TreeNodeCollection c)
{
    foreach (var node in c.OfType<TreeNode>())
    {
        yield return node;

        foreach (var child in node.Nodes.Descendants())
        {
            yield return child;
        }
    }
}

For example:

var allCheckedNodes = myTreeView.Nodes.Descendants().Where(c => c.Checked);

Answer 2

It's difficult to traverse arbitrary complex data-structures with just simple LINQ queries. At some point, you'll have to 'cut your losses' and write iterator blocks yourself - possibly only for the parts that are hard to express with standard LINQ.

That said, for your linked list example, with moreLinq, you can do:

MoreEnumerable.Generate(head, node => node.Next)
              .TakeWhile(node => node != null)

If you want recursive LINQ tree traversal (or similar), it would be quite different, but here's a sample (depth-first):

private static IEnumerable<Node> GetNodeAndDescendants(Node node)
{
   return new[] { node }.Concat(node.Children.SelectMany(GetNodeAndDescendants));
}