title: Flattening a doubly linked list with child lists - optimizations, feedback, possible modifications
body: <p>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). </p>
  
  <p>Sorry - edited to add: The condition of the flattening is that a child is inserted directly after the parent.</p>
  
  <pre><code>using System;
  using System.Collections;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  
  namespace FlattenDoublyLinkedChildList
  {
  
      public class DoublyListEntry&lt;T&gt;
      {
          public T Data { get; set; }
          public DoublyListEntry&lt;T&gt; Next { get; set; }
          public DoublyListEntry&lt;T&gt; Prev { get; set; }
          public DoublyListExample&lt;T&gt; Child { get; set; }
          public DoublyListEntry(T data)
          {
              Data = data; 
          }
  
      }
  
      public class DoublyListEnum&lt;T&gt; : IEnumerator&lt;T&gt;
      {
          private DoublyListEntry&lt;T&gt; current { get; set; }
          private DoublyListEntry&lt;T&gt; start { get; set; }
          private bool dirty;
  
          public DoublyListEnum(DoublyListEntry&lt;T&gt; 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&lt;T&gt; : IEnumerable&lt;T&gt;, IEnumerable
      {
          private DoublyListEntry&lt;T&gt; head;
          private DoublyListEntry&lt;T&gt; tail;
          public int length { get; set; }
          public DoublyListEntry&lt;T&gt; Head
          {
              get
              {               
                  return head;               
              }
          }
  
  
          public DoublyListEntry&lt;T&gt; Tail
          {
              get
              {                
                  return tail;                
              }
          }
  
  
  
  
          IEnumerator IEnumerable.GetEnumerator()
          {
              return GetEnumerator();
          }
  
  
          public IEnumerator&lt;T&gt; GetEnumerator()
          {
              if (head != null)
              {
                  return new DoublyListEnum&lt;T&gt;(head);
              }
              else
              {
                  throw new Exception("nothing to enumerate");
              }
  
  
          }
  
  
          public void Add(T data)
          {
              if (head == null)
              {
                  head = new DoublyListEntry&lt;T&gt;(data);
                  tail = head;
                  length++;
              }
              else
              {
                  tail.Next = new DoublyListEntry&lt;T&gt;(data);
                  tail.Next.Prev = tail;
                  tail = tail.Next;
                  length++;
              }
          }
  
          public void InsertAfter(T data, int position)
          {
              if (position &lt; 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 &gt;= length) //we could allow this stuff and padd out the list etc, but for now...no soup.
              {
                  throw new Exception("Position requested is &gt; then the length of the list.");
              }
  
              if (position == length - 1) //just an inswer
              {
                  Add(data);
                  return;
              }
  
  
              DoublyListEntry&lt;T&gt; newElement = new DoublyListEntry&lt;T&gt;(data);
              DoublyListEntry&lt;T&gt; 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&lt;T&gt; GetElementAt(int position)
          {
              DoublyListEntry&lt;T&gt; temp = head;
  
              //pop down N levels until position
              int counter = 0;
              while (counter &lt; position)
              {
                  temp = temp.Next;
                  counter++;
                  if (temp == null &amp;&amp; counter &lt; 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&lt;T&gt; behind;
              DoublyListEntry&lt;T&gt; current;
              current = head;
              behind = head;
              for (int i = 0; i &lt;= 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 &lt; 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 &gt;= length) //we could allow this stuff and padd out the list etc, but for now...no soup.
              {
                  throw new Exception("Position requested is &gt; then the length of the list.");
              }
  
              if (position == 0) //head
              {
                  head = head.Next;
                  length--;
                  return;
              }
  
              DoublyListEntry&lt;T&gt; 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&lt;T&gt;
              Test5(); //nth from last
              Test6(); //prevs
  
              Test7(); //children
  
          }
  
  
          #region simple tests
          public static void Test1()
          {
              DoublyListExample&lt;string&gt; myList = new DoublyListExample&lt;string&gt;();
              myList.Add("joe");
              myList.Add("mike");
              myList.Add("adam");
              if (myList.Head.Data != "joe") throw new Exception("fail");
              if (myList.Tail.Data != "adam") throw new Exception("fail");
              if (myList.GetElement(1) != "mike") throw new Exception("fail");
  
          }
  
          public static void Test2()
          {
              DoublyListExample&lt;string&gt; myList = new DoublyListExample&lt;string&gt;();
              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&lt;string&gt; myList = new DoublyListExample&lt;string&gt;();
              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&lt;string&gt; myList = new DoublyListExample&lt;string&gt;();
              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&lt;string&gt; myList = new DoublyListExample&lt;string&gt;();
              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&lt;string&gt;();
              myList.Add("there can be only one");
              if (myList.GetNthFromLast(3) !=null) throw new Exception("fail");
  
  
  
          }
  
          public static void Test6()
          {
              DoublyListExample&lt;string&gt; myList = new DoublyListExample&lt;string&gt;();
              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&lt;string&gt; myList = new DoublyListExample&lt;string&gt;();
              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&lt;string&gt;();
              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&lt;string&gt;();
              myList.Tail.Child.Add("alsub1");
              myList.Tail.Child.Add("alsub2");
              DoublyListEntry&lt;string&gt; temp = myList.GetElementAt(2);
              temp.Child = new DoublyListExample&lt;string&gt;();
              temp.Child.Add("adam sub1");
              temp.Child.Add("adam sub2");
              temp.Child.Head.Child = new DoublyListExample&lt;string&gt;();
              temp.Child.Head.Child.Add("adam sub 1 sub 1");
              temp.Child.Head.Child.Add("adam sub 1 sub 2");
  
  
              Flatten(myList.Head);
  
              DoublyListEntry&lt;string&gt; 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&lt;string&gt; 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&lt;string&gt; save = current.Next;
                      current.Next = current.Child.Head;
                      current.Child.Head.Prev = current;
  
                      DoublyListEntry&lt;string&gt; 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);               
              }                                                    
          }
      }    
  }
  </code></pre>