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:
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:
What you need to do for
this exercise:
- You need to implement
the Clone methods in the provided MyLinkedList class.
- This class should be
found in the Student_Answers.cs file, in a project named something like
03_PCE_StudentCode.
- 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.
- 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)
- 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.
- 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.
- 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.