Cloning A List

 

The goal of this exercise is to clarify and refine your understanding of the “Linked List Traversal” schema, by implementing several (fairly easy) methods.

             For this exercise, you are required to implement the Clone method, which makes a deep copy of not just the current MyLinkedList object, but of all the nodes in the list.

 Let’s say that your list starts out looking like this:

Clone_Explanation_01

Once your method has finished, not only should the original list still exist, but another, completely separate copy of it also exist.  The following picture attempts to convey that situation:

Clone_Explanation_02

 

 What you need to do for this exercise:  

  1. You need to implement the Clone methods in the provided MyLinkedList class.
    1. This class should be found in the Student_Answers.cs file, in a project named something like 03_PCE_StudentCode.
  2. To start, it is highly recommended that you need to summarize what your method will do, in each of the three major parts of the ‘linked list traversal’ schema, in order to clone the list.  You are not required to write anything down for this step, but it’s recommended that you do so.
  3. public MyLinkedList Clone()

    This method should return a NEW MyLinkedList object, where all the nodes in this new list have values identical to the ones stored in the current list.  You need to create a new set of LinkedListNode objects for this new list (i.e., the new MyLinkedList object must be unconnected to the current one, at the end of this method)
    1. a.    In the second picture, above, this is the second (lower) box that contains the m_first.  Note that you are NOT returning a LinkedListNode object, but instead returning the MyLinkedList object.
    2. You are NOT allowed to do this by simply creating a new MyLinkedList object, and then repeatedly calling AddAt on the new list in order to add all of the existing values to the new list.  Your solution must run in O(N) time.
      1. In a comment, above the clone method, write the running time of the solution that uses AddToList, along with a quick explanation of why this solution takes that long.