Week 5: Linear Lists – Linked Representation
1. Write code for the class ChainWithSortMethods. This class is a subclass of Chain and it includes the number method insertionSort, which uses insertion sort to reorder the chain elements into nondecreasing order. Do not create new nodes or delete old ones.
a) What is the worst-case time complexity of your method? How much time does your method need if the elements are already in sorted order?
b) Test the correctness of your method by compiling and then executing the code. Use your own test data (any programs with any data are allowed).