How do I convert a recursive object to a Collection in C#?

Question

I have a recursive object, a linked list really:

public class LinkedList 
{
    public string UniqueKey { get; set; }
    public LinkedList LinkedList { get; set; }
}

LinkedList will have some object graph that will eventually end in LinkedList.LinkedList == null.

I would like to take all the objects in the graph and put them into a LinkedList collection so that I can iterate over them. How do I do this in C#? I feel as if there's a really easy way of going about this using yield or Linq voodoo?

Answer 1

Something like this should work. If you have control over the class you can make it IEnumerable directly.

public class LinkedListEnumerable : IEnumerable<string>
{
    LinkedList list;
    public LinkedListEnumerable(LinkedList l)
    {
        this.list = l;
    }

    public IEnumerator<string> GetEnumerator()
    {
        LinkedList l = list;
        while(l != null)
        {
            yield return l.UniqueKey;
            l = l.Next;
        }
    }
}

Then you can iterate over LinkedListEnumerable with a for-each loop.

Answer 2

Is this what you want?

public class LinkedList
{
    public string UniqueKey { get; set; }
    public LinkedList LinkedList { get; set; }

    public IEnumerable<LinkedList> GetAllNodes()
    {
        if (LinkedList != null)
        {
            yield return LinkedList;
            foreach (var node in LinkedList.GetAllNodes())
                yield return node;
        }
    }
}

Answer 3

There are no nice LINQ methods in the standard .NET library to allow some elegant LINQ voodoo, but you can use Generate method from MoreLINQ project and write this:

Enumerable
  .Generate(list, l => l.LinkedList)
  .TakeWhile(l => l != null).Select(l => l.UniqueKey);

It uses Generate to create "infinite" list of all elements - it is not actually infinite, because it is generated lazily and we stop using it as soon as we find null value at the end (using TakeWhile). Then we use Select to return a sequence of values (instead of linked list nodes).

This is essentially a nice declarative way of expressing the while loop solution posted by Matthew (and it should have roughly similar performance).

EDIT The Generate method looks like this:

IEnumerable<T> Generate(T current, Func<T, T> generator) {
  while(true) { 
    yield return current;
    current = generator(current);
  }
}