Implement the following List interface using a DLinkedNode<E> to store the data.
public interface List211<E> {
boolean add(E e);
void add(int index, E element);
E get(int index);
E remove(int index);
E set(int index, E element);
int size();
}
Name your class MyLinkedList.
In addition to the List interface implement the following sort methods:
public class MyLinkedList<E> implements List211<E> {
private DLinkedNode<E> head;
private DLinkedNode<E> tail;
private int size;
public void insertionSort(Comparator<? super E> compare);
public void bubbleSort(Comparator<? super E> compare);
public void selectionSort(Comparator<? super E> compare);
Use the Comparator to compare the items in the array. The sort methods should sort the list in ascending order, smallest at the beginning, largest at the end.
Write up a runtime analysis of each of the methods, giving the big-O of each, and explaining how you got your results. Send your analysis to the TA together with your code. This is an important part of the grade on this assignment. Even if your code doesn’t work, you should do this part to the best of your ability.
Please thoroughly test your code and briefly discuss your testing strategy. Make sure that you test the different sorting algorithms. Turn in all your test code.
The assignment is due on Friday at 11:59pm. You may turn it in early. If you haven’t completed the assignment by 11:58, turn in what you have. Getting partial credit is much better then no credit.