Flattening a doubly linked list with child lists - optimizations, feedback, possible modifications

Attached is a quick program written under interview conditions that is designed to flatten a doubly linked list with child links. I was wondering what folks thought and if there were some optimizations (or possibly another way of doing things) you could point out that I could learn from. Code is below - Test7 is the test of the flattening algo).

Sorry - edited to add: The condition of the flattening is that a child is inserted directly after the parent.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FlattenDoublyLinkedChildList
{

    public class DoublyListEntry<T>
    {
        public T Data { get; set; }
        public DoublyListEntry<T> Next { get; set; }
        public DoublyListEntry<T> Prev { get; set; }
        public DoublyListExample<T> Child { get; set; }
        public DoublyListEntry(T data)
        {
            Data = data; 
        }

    }

    public class DoublyListEnum<T> : IEnumerator<T>
    {
        private DoublyListEntry<T> current { get; set; }
        private DoublyListEntry<T> start { get; set; }
        private bool dirty;

        public DoublyListEnum(DoublyListEntry<T> inStart)
        {
            start = inStart;
            current = start;
            dirty = false;
        }

        public void Dispose()
        {
            current = null;
            start = null;

        }


        object System.Collections.IEnumerator.Current
        {
            get
            {
                return Current;
            }
        }

        public T Current
        {
            get
            {
                if (current != null)
                    return current.Data;
                else
                    return default(T);
            }
        }

        public void Reset()
        {
            current = start;
            dirty = false;
        }

        public bool MoveNext()
        {
            if (current == null)
            {
                return false;
            }
            else if (current.Next != null)
            {
                if (!dirty)
                {
                    dirty = true; //move next is called from the start
                }
                else
                {
                    current = current.Next;
                }
                return true;
            }
            else
            {
                return false;
            }
        }
    }

    public class DoublyListExample<T> : IEnumerable<T>, IEnumerable
    {
        private DoublyListEntry<T> head;
        private DoublyListEntry<T> tail;
        public int length { get; set; }
        public DoublyListEntry<T> Head
        {
            get
            {               
                return head;               
            }
        }


        public DoublyListEntry<T> Tail
        {
            get
            {                
                return tail;                
            }
        }




        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }


        public IEnumerator<T> GetEnumerator()
        {
            if (head != null)
            {
                return new DoublyListEnum<T>(head);
            }
            else
            {
                throw new Exception("nothing to enumerate");
            }


        }


        public void Add(T data)
        {
            if (head == null)
            {
                head = new DoublyListEntry<T>(data);
                tail = head;
                length++;
            }
            else
            {
                tail.Next = new DoublyListEntry<T>(data);
                tail.Next.Prev = tail;
                tail = tail.Next;
                length++;
            }
        }

        public void InsertAfter(T data, int position)
        {
            if (position < 0)
            {
                throw new Exception("no soup for you - position must be 0 or higher");
            }

            if (head == null)
            {
                throw new Exception("sorry, you cannot insert after nothing, the list is empty.");
            }

            if (position >= length) //we could allow this stuff and padd out the list etc, but for now...no soup.
            {
                throw new Exception("Position requested is > then the length of the list.");
            }

            if (position == length - 1) //just an inswer
            {
                Add(data);
                return;
            }


            DoublyListEntry<T> newElement = new DoublyListEntry<T>(data);
            DoublyListEntry<T> temp = GetElementAt(position);
            newElement.Next = temp.Next;
            newElement.Prev = temp;
            temp.Next = newElement;
            length++;
        }

        public T GetElement(int position)
        {
            return GetElementAt(position).Data;
        }

        public DoublyListEntry<T> GetElementAt(int position)
        {
            DoublyListEntry<T> temp = head;

            //pop down N levels until position
            int counter = 0;
            while (counter < position)
            {
                temp = temp.Next;
                counter++;
                if (temp == null && counter < position) //should have been caught
                {
                    throw new Exception(String.Format("{0} elements do not exist", position));
                }
            }

            return temp;
        }

        public T GetNthFromLast(int Nth)
        {
            //use the iterator, keep a Nth away pointer
            //when we get to the last item, return the Nth away cousin
            if (head == null) throw new Exception("Not initialized");
            if (Nth == 0) return tail.Data;

            DoublyListEntry<T> behind;
            DoublyListEntry<T> current;
            current = head;
            behind = head;
            for (int i = 0; i <= Nth; i++)
            {
                if (current != null)
                    current = current.Next;
                else return default(T);
            }

            while (current != null)
            {
                current = current.Next;
                behind = behind.Next;
            }

            return behind.Data;
        }



        public void Remove(int position)
        {
            if (position < 0)
            {
                throw new Exception("no soup for you - position must be 0 or higher");
            }

            if (head == null)
            {
                throw new Exception("sorry, you cannot remove from nothing, the list is empty.");
            }

            if (position >= length) //we could allow this stuff and padd out the list etc, but for now...no soup.
            {
                throw new Exception("Position requested is > then the length of the list.");
            }

            if (position == 0) //head
            {
                head = head.Next;
                length--;
                return;
            }

            DoublyListEntry<T> temp;

            temp = GetElementAt(position - 1);
            if (position == length - 1)
            {
                tail = temp;
                tail.Next = null;
                length--;
                return;
            }

            temp.Next = temp.Next.Next;
            length--;

        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Test1(); //basic head + tail
            Test2(); // Insert After
            Test3(); // Remove
            Test4(); // Enumerator<T>
            Test5(); //nth from last
            Test6(); //prevs

            Test7(); //children

        }


        #region simple tests
        public static void Test1()
        {
            DoublyListExample<string> myList = new DoublyListExample<string>();
            myList.Add("joe");
            myList.Add("mike");
            myList.Add("adam");
            if (myList.Head.Data != "joe") throw new Excepti开发者_StackOverflow社区on("fail");
            if (myList.Tail.Data != "adam") throw new Exception("fail");
            if (myList.GetElement(1) != "mike") throw new Exception("fail");

        }

        public static void Test2()
        {
            DoublyListExample<string> myList = new DoublyListExample<string>();
            myList.Add("joe");
            myList.Add("mike");
            myList.Add("adam");
            myList.InsertAfter("paul", 1);
            myList.InsertAfter("john", 0);
            myList.InsertAfter("nichole", 4);
            if (myList.Tail.Data != "nichole") throw new Exception("fail");
            if (myList.Head.Data != "joe") throw new Exception("fail");

            if (myList.GetElement(0) != "joe") throw new Exception("fail");
            if (myList.GetElement(1) != "john") throw new Exception("fail");
            if (myList.GetElement(2) != "mike") throw new Exception("fail");
            if (myList.GetElement(3) != "paul") throw new Exception("fail");
            if (myList.GetElement(4) != "adam") throw new Exception("fail");
            if (myList.GetElement(5) != "nichole") throw new Exception("fail");

        }


        public static void Test3()
        {
            DoublyListExample<string> myList = new DoublyListExample<string>();
            myList.Add("joe");
            myList.Add("mike");
            myList.Add("adam");
            myList.InsertAfter("paul", 1);
            myList.InsertAfter("john", 0);
            myList.InsertAfter("nichole", 4);

            myList.Remove(0);
            if (myList.Head.Data != "john") throw new Exception("fail");

            myList.Remove(myList.length-1);
            if (myList.Tail.Data != "adam") throw new Exception("fail");

            myList.Remove(1);
            if (myList.Head.Data != "john") throw new Exception("fail");
            if (myList.Tail.Data != "adam") throw new Exception("fail");
            if (myList.GetElement(0) != "john") throw new Exception("fail");
            if (myList.GetElement(1) != "paul") throw new Exception("fail");
            if (myList.GetElement(2) != "adam") throw new Exception("fail");

        }

        public static void Test4()
        {
            DoublyListExample<string> myList = new DoublyListExample<string>();
            myList.Add("joe");
            myList.Add("mike");
            myList.Add("adam");
            myList.Add("paul");
            myList.Add("john");
            myList.Add("nichole");

            int count = 0;
            foreach (string name in myList)
            {
                switch (count)
                { 
                    case 0:
                        if (name != "joe") { throw new Exception("fail"); }
                        break;
                    case 1:
                        if (name != "mike") { throw new Exception("fail"); }
                        break;
                    case 2:
                        if (name != "adam") { throw new Exception("fail"); }
                        break;
                    case 3:
                        if (name != "paul") { throw new Exception("fail"); }
                        break;
                    case 4:
                        if (name != "john") { throw new Exception("fail"); }
                        break;
                    case 5:
                        if (name != "nichole") { throw new Exception("fail"); }
                        break;                
                }

                count++;
            }


        }

        public static void Test5()
        {
            DoublyListExample<string> myList = new DoublyListExample<string>();
            myList.Add("joe");
            myList.Add("mike");
            myList.Add("adam");
            myList.Add("paul");
            myList.Add("john");
            myList.Add("nichole");

            if (myList.GetNthFromLast(0) != "nichole") throw new Exception("fail");
            if (myList.GetNthFromLast(1) != "john") throw new Exception("fail");
            if (myList.GetNthFromLast(2) != "paul") throw new Exception("fail");
            if (myList.GetNthFromLast(3) != "adam") throw new Exception("fail");
            if (myList.GetNthFromLast(4) != "mike") throw new Exception("fail");
            if (myList.GetNthFromLast(5) != "joe") throw new Exception("fail");

            myList = new DoublyListExample<string>();
            myList.Add("there can be only one");
            if (myList.GetNthFromLast(3) !=null) throw new Exception("fail");



        }

        public static void Test6()
        {
            DoublyListExample<string> myList = new DoublyListExample<string>();
            myList.Add("joe");
            myList.Add("mike");
            myList.Add("adam");
            myList.Add("paul");
            myList.Add("john");
            myList.Add("nichole");
            if (myList.Tail.Data != "nichole") throw new Exception("fail");
            if (myList.Tail.Prev.Data != "john") throw new Exception("fail");
            if (myList.Tail.Prev.Prev.Data != "paul") throw new Exception("fail");
            if (myList.Tail.Prev.Prev.Prev.Data != "adam") throw new Exception("fail");
            if (myList.Tail.Prev.Prev.Prev.Prev.Data != "mike") throw new Exception("fail");
            if (myList.Tail.Prev.Prev.Prev.Prev.Prev.Data != "joe") throw new Exception("fail");

            myList.InsertAfter("alyssa", 0);
            if (myList.Head.Next.Data != "alyssa") throw new Exception("fail");
            if (myList.Head.Next.Prev.Data != "joe") throw new Exception("fail");
            if (myList.Tail.Data != "nichole") throw new Exception("fail");
            myList.Add("buddy");
            if (myList.Tail.Data != "buddy") throw new Exception("fail");
            if (myList.Tail.Prev.Data != "nichole") throw new Exception("fail");
        }
        #endregion

        static void Test7()
        { 
            //make child trees
            DoublyListExample<string> myList = new DoublyListExample<string>();
            myList.Add("joe");
            myList.Add("mike");
            myList.Add("adam");
            myList.Add("paul");
            myList.Add("john");
            myList.Add("nichole");
            myList.Add("alyssa");
            myList.Head.Child = new DoublyListExample<string>();
            myList.Head.Child.Add("Joesub1");
            myList.Head.Child.Add("Joesub2");
            myList.Head.Child.Add("Joesub3");
            myList.Head.Child.Add("Joesub4");
            myList.Tail.Child = new DoublyListExample<string>();
            myList.Tail.Child.Add("alsub1");
            myList.Tail.Child.Add("alsub2");
            DoublyListEntry<string> temp = myList.GetElementAt(2);
            temp.Child = new DoublyListExample<string>();
            temp.Child.Add("adam sub1");
            temp.Child.Add("adam sub2");
            temp.Child.Head.Child = new DoublyListExample<string>();
            temp.Child.Head.Child.Add("adam sub 1 sub 1");
            temp.Child.Head.Child.Add("adam sub 1 sub 2");


            Flatten(myList.Head);

            DoublyListEntry<string> current;
            current = myList.Head;
            while (current != null)
            {
                Console.WriteLine(current.Data);
                current = current.Next;
            }

            //test that you can back through all the way

            Console.WriteLine("*********************"); 
            current = myList.Tail;
            while (current != null)
            {
                Console.WriteLine(current.Data);
                current = current.Prev;
            }

            Console.WriteLine("*********************"); 
            current = myList.Head;
            while (current != null)
            {
                Console.WriteLine(current.Data);
                current = current.Next;
            }

        }

        private static void Flatten(DoublyListEntry<string> current)
        {
            if (current == null) return;

            //if I have children
            if (current.Child != null)
            {
                //set my next, to my first child
                if (current.Child.Head != null)
                {
                    DoublyListEntry<string> save = current.Next;
                    current.Next = current.Child.Head;
                    current.Child.Head.Prev = current;

                    DoublyListEntry<string> temp = current.Next;
                    while (temp.Next != null)
                    {
                        temp = temp.Next;
                    }                    
                    temp.Next = save;

                    if (save != null)
                    {
                        save.Prev = temp;
                    }

                    Flatten(current.Next);
                }
                else
                {
                    return;
                }

            }
            else
            {
                Flatten(current.Next);               
            }                                                    
        }
    }    
}

---

Recursion > Iteration

If you use iteration instead of recursion with tree flattening it will perform much better. Check this question and especially it's first answer.