Insert A New Node At An Arbitrary Index

 

The goal of this exercise is to make sure that you can implement the logic needed to add items to the middle of a linked list.

 

What you need to do for this exercise:  

1. For this exercise, you need to implement the InsertAt method 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. The InsertAt method looks like:
   
   void InsertAt(int newData, uint index);
   
   You've already seen (from the lecture) how to build a function which will insert the new integer into a linked list, at the given index, so the overall details will not be explained here, with two exceptions.
   1. a.    Index is a ‘zero-based’ index, meaning that the first item in the list has the index value “0”.  So if the list contains {1,2}, and you call InsertAt(3, 0), the value three should be placed in the list so that 3 is at location zero; the resulting list would look like: {3, 1, 2}
   2. If index is larger than the list, you should insert the new data item at the very end of the list.
3. Annotate this method (put a comment next to this method) describing the running time of that method, using the Big "Oh" notation.